Friday, November 3, 2017

NaMeCryReNoWriMo, day 3: Salsa20/ChaCha20 and Poly1305

Not as much today as I'd like because I actually had work to do, but I may add more later tonight if I have nothing else to do.


Stream cipher.  Uses a 256bit key, 64bit nonce, and 64bit stream index, and generates a 512-bit block.  Has the unusual (for a stream cipher; block ciphers in counter mode also have this) property that any given block in the keystream can be generated in constant time.

Basic bit operations are xor, 32-bit addition mod 2^32, and left-rotation.

Each 512-bit stream block is made by performing those on a 512-bit block consisting of the key (256), the stream position (64), the nonce (64), and a constant value (128).  These blocks are a total of 16 "words" (which means 32 bytes when talking about binary data) arranged in a 4x4 matrix.  Each word w0 is mutated by combining it with two other words from the block and one of the numbers 7, 9, 13, or 18, depending on its placement.  I'm still having trouble figuring out exactly how the  matrix is constructed.

20 rounds of this operation are performed for standard Salsa20, although weaker (and faster) versions use fewer rounds.


Variant of Salsa20 with a different combination of bit operations used in each round.

Google (and others, I assume?) uses it, along with Poly1305, as a replacement for RC4 in TLS.

For ChaCha20, the 16-word matrix is constructed from 4 constant words, the 8 words of the key, one word of a position counter (as that's enough for 256GB of data), and 3 words of nonce, in that order.


Message authentication code. 16-bytes for any-sized message.  Uses two 128-bit keys r and s.

The basic algorithm is as follows:
-Break the message into 16-byte blocks.  For each block:
--Append one more bit 1.  If it's a 16-byte block this is equivalent to the block plus 2^128, but if it's the last block it may be smaller and so be equivalent to some other number 2^(8k) (where k is a positive integer)
--Pad the block with 0s to 17 bytes.
--Add this to the result from the previous message block (add 0 if it's the first block)
--Multiply this by r (first key). (this makes it a polynomial function, hence the first half of the name)
--take this mod p, where p = (2^130)-5 (this is where the second half of the name comes from)
-Once you've done this for every block, add s, and then the 128 LSBs form the MAC.
(Random note: all the byte stuff above is done little-endian)


As far as I can tell, it's pretty similar to AES until you dive down into the specific details of the substitutions/permutations involved.


Feistel cipher like AES.  Uses 2 S-boxes.  One is the same as AES, the other is taken from the binary representation of pi.





New topics:

??? RC4
??? Feistel cipher

No comments: