[Cryptech Tech] Doc, Markdown, and Wiki

[Bernd Paysan]

Am Freitag, 7. November 2014, 10:16:16 schrieb Joachim Strömbergson:
> Regarding coding style and methods of implementation we clearly have
> widely different views and experiences.

Indeed.

> I'm basing my methods a lot on what I see are best practices, for
> example from Cisco, Ericsson, but also from established experts such as
> Sutherland and Cummings.

Ok, I don't like the word "best practice".  It's usually something you don't 
get fired for, and the common idiom then is "cover your ass" ;-).  In big 
companies, this stuff is often a least common denominator.  I had a very 
unpleasant review of my b16 core, where two people with big-company 
backgrounds only bitched about Verilog syntax they didn't know (and because 
they came from two different big companies, their Verilog subset was wildly 
different).  And they asked things like "please expand the shift left into a 
case statement".  I can see how these rules can result in the repetitive code 
you write.  Please leave all repetitive tasks to the computer, he's much, much 
better at it (both in terms of speed and in terms of correctness).

Verilog isn't such a complex language that you have to restrict yourself to a 
small subset, because it's so hard to learn everything.  If you have a good 
background in HDL design, I recommend the quick reference guide for Verilog 
2k, it's 56 pages.

http://www.sutherland-hdl.com/online_verilog_ref_guide/verilog_2001_ref_guide.pdf

> But there are also conflicting best practices. And if one starts to
> target not only design guidelines from different FPGA vendors, but also
> FPGA as well as possible ASIC designs with big tool chains the design
> style used will become fairly conservative in language features and
> stating hard absolutes in terms of what is the best way doesn't really
> work. It is always a compromise.

I've been through all that, and in the 90s, a number of tools did indeed have 
problems with this or that HDL construct. So you settled down to not doing 
this, because tool A has a bug, and not doing that, because tool B has a bug. 
Fortunately, the 90s are almost 15 years in the past, and the tools are much 
better now.  There are still some bugs here or there, but not nearly as many 
as there used to be.

So to speak: If you use Verilog 2001 constructs (you do, and this is good; 
especially "always @*" is a must-use), you can ignore many of these 
conservative rules of the 90s. All tools which can process Verilog 2001 have 
fixed the bugs from 20 years ago.

> From my experience doing code auditing as well as working on big
> designs, the claim that tersness is always better is not something I
> agree with.

If you want to make big designs, verboseness is great, because the designs get 
a lot bigger quickly just by beeing verbose ;-).  Honestly, you wrote in the 
order of 300 lines for a task which takes 3 lines if done concise.  The three 
lines are more difficult to read, but you are done with that after three 
lines.  And nobody has to check the 300 lines for typos.

> If it was, IOCCC entries would be considered the pinnacle of
> maintainable code.

The main problem with IOCCC entries is that they try hard by using macros to 
change names, so the main obfuscation is to write a new programming language.  
buzzard2.c in IOCCC 1992 took that to an extreme, by writing a small Forth 
system in obfuscated C, so you have several languages to learn to understand 
what this 30 lines do.

The maintainance problem of your style IMHO is redundancy which requires to 
change several parts of the design when you make a single conceptual change. 
And you use several VHDL-related coding styles which do not apply to Verilog 
at all.

Example, take the chacha quarter rounds.  I would write this as follows:

module chacha_qr(
	         input wire [31 : 0] a_in, b_in, c_in, d_in,
	         output reg [31 : 0] a, b, c, d
	         );
   `define rotl32(x, r) {x[31-r : 0], x[31 : 32-r]}

   always @*
      begin: qr
	a = a_in;	b = b_in;	c = c_in;	d = d_in;

	// chacha quarter round, see
	// http://cr.yp.to/chacha/chacha-20080128.pdf page 3
	a = a + b;	d = d ^ a;	d = rotl32(d, 16);
	c = c + d;	b = b ^ c;	b = rotl32(b, 12);
	a = a + b;	d = d ^ a;	d = rotl32(d, 8);
	c = c + d;	b = b ^ c;	b = rotl32(b, 7);
      end
endmodule // chacha_qr

So let's see what you do.  First of all, you double-declare the outputs, 
because you have them first as "wire", and then as "reg", as they are assigned 
in an always @* block (they need to be reg there).  However, in Verilog, you 
can have "output reg".  No Verilog 2001 capable tool has problems with "output 
reg".  So this takes out 8 lines, which don't add any useful information to 
the reader: 4 lines of additional declarations, and 4 lines of assignments.  
The confusing comment "wires" where you then actually declare "reg" not 
included ;-).

The layout is deliberately 3 assignments in one line, not to reduce line 
count, but to visually match the way ChaCha's quarter round is defined in Dan 
Bernstein's paper.  And I used rotl32 to make clear that this is a left 
rotation, using Verilog 2001's macros with parameters. Furthermore, I take 
advantage of blocking assignments, i.e. I can just write the code as in the C-
like language Dan Bernstein is using in his paper, without having to declare 
multiple regs.

I think that way it is easier to check that the Verilog code matches Dan 
Bernstein's paper, because you aren't too much distracted by glue stuff on the 
Verilog side, and the layout of the core function maps to how it is written in 
the paper.  The rotate left macro also makes sure that there's no typo in how 
the rotate left is performed; you only have to check the macro once that it is 
indeed doing a rotate left for a 32 bit value by the specified amount of bits 
(you probably want to put definitions of rotl32, rotr32, rotl64 and rotr64 
into a common file, as rotate is used in many of those crypto cores).

Let's rephrase it: I don't strive for "terse", I strive for "concise".  This 
sort of stuff all makes it more maintainable by reducing the line count *and* 
using features which improve readability, and reduce errors creeping in.  
You'll have a lot of uses for rotl32 in the entire HSM, and with the macro, 
you make it

a) more readable, because the concatenation with four numbers is reduced to a 
named rotl macro with just one number - the number you can look up in the 
corresponding paper
b) less likely that an error slips in, because no hand calculation is 
necessary

Looking through your code, there's ample of opportunity to use macros and 
making the code both more readable and more maintainable.  E.g. the byteswap 
stuff in chacha_core.  Just define one bswap32 macro.  And there are many more 
opportunities to make it more concise (e.g. declare the registers as array, 
and use a loop).

I hope you understand what I think is easily audible code.  Are you 70 lines 
of code really more readable than my 16?  Easier to maintain, easier to 
compare against djb's paper for audit?

A lot of secure free software stuff suffers from lack of audits.  One reason 
for lack of audit is that the code is not fun to audit, but a tedious job.  
When I audit your code, and my instant reaction is that this needs a rewrite 
from scratch, because it is way to verbose to be fun to audit.

Remember: You can audit code for about one hour, and then you stop being 
concentrated enough to find issues.  So it just is that hour you have; be 
concise enough so that the auditor can get through within that productive 
hour.

There's a reason why the modern crypto functions are so small and concise like 
ChaCha: this is stuff that actually *is* audited.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/