Monday, November 6, 2017

NaMeCryReNoWriMo, day 6: Reading Signal blog posts

Today's studying started with reading on the Signal Protocol but quickly devolved into reading blog posts

Signal protocol

"The protocol combines the Double Ratchet Algorithm, prekeys, and a triple Diffie–Hellman (3-DH) handshake, and uses Curve25519, AES-256 and HMAC-SHA256 as primitives."

Double Ratchet Algorithm

Key management algorithm.
Manages renewal and maintenance of short-lived session keys while providing forward secrecy.  Based on Off-the-Record Messaging and Silent Circle Instant Messaging Protocol.

Signal blog
TL;DR There is no theoretically secure way to let a user find which of their contacts are using Signal that prevents Signal from being able to see their social graph.  We're just writing the code to not store that info and giving users the choice between trusting us and opting out of contact discovery.
TL;DR In order to let a user find which of their contacts are using Signal without giving Signal a way to store that data, the lookup is done inside a sever-side Intel SGX enclave running verifiable code in a way that ensures the host machine can't get insight into the social graph through memory access patterns. <- Need to read this one again to fully grok all of it.

??? Read

Sunday, November 5, 2017

NaMeCryReNoWriMo, day 5: [redacted]

Today's studying has been playing around with HSMs.  Unfortunately, that means it's a bunch of writing code for the product on which I work, so I need to run it by legal folks before I post it publicly.

Stay tuned for your regularly scheduled meandering crypto refresher notes tomorrow.

Saturday, November 4, 2017

NaMeCryReNoWriMo, day 4: Feistel ciphers and HSMs

Feistel cipher

Class of block cipher.  Encryption/decryption very similar, so less to implement.  Made up of a "round" that gets performed many times.

(For each round)
The input is either the plaintext or the result from the previous round.  Split it into two halves, Li (Left input) and Ri (Right input).
Lo (Left output) is Ri.
Ro (Right output) is Li xored with F(Ri, Kr), where F is the underlying function of the cipher and Kr is the key for that specific round.
And now Lo and Ro are Li and Ri for the next round.

(For each round)
The input is the ciphertext, made up of Lo and Ro.  We want to find Li and Ri.
Ri is just Lo.
Li is Ro xored with F(Ri, Kr) [and because of above, remember that F(Ri, Kr)==F(Lo, Kr)]
And Li and Ri are Lo and Ro from the previous round, so this can be repeated back down to the plaintext.

L and R are not always balanced; Skipjack is moderately unbalanced, while the Thorp Shuffle has L as a single bit.

Most block ciphers are based on either Feistel ciphers or substitution-permutation networks (or potentially a mix of the two?)


Stream cipher.  Functions by performing repeated permutations on a block of 256 bytes and after each permutation outputs a number that's a combination of a couple of them.
Does not use a nonce, only a key.
Exact algorithm is on the wikipedia page.  I don't feel like rewriting it.
Basic weakness is that the first couple bytes of the output leak information about the initial generating key.  Key recovery attacks can be performed with millions or billions of messages (wikipedia calls out 2^26 and 2^34)
"The use of RC4 in TLS is prohibited by RFC 7465 published in February 2015."

PKCS #11

Standardized programming interface for cryptographic operations.  Cryptoki API communicates with crypto stuff via "slots".  Slots map to crypto "tokens", usually hardware devices specifically built for cryptographic operations.  (It's possible to have a software-backed slot for testing, though, such as with the SoftHSM linked above.)  Each token can have a number of data blobs, keys, and certificates, and supports various operations on each depending on data type and configuration settings.

FIPS 140-2

Federal Information Processing Standard 140-2: Security Requirements for Cryptographic Modules
Defines four different levels of security for hardware+software cryptographic modules.  1 is weakest, 4 is strongest.

According to wikipedia:

Level 1: It can do some form of approved crypto.

Level 2: Has physical tamper-evident features and/or pick-resistant locks.

Level 3: Has features that wipe the crypto material in the module if it's tampered with.

Level 4: Like level 3, but to the extreme.  Must either be shown to be unaffected by abnormal environmental conditions or, if it is affected, to wipe crypto material before it's compromised.

I seem to recall there also being software components to FIPS 140-2...
Yep, wikipedia leaves out a lot of the NIST guidelines.  Good job, guys.

Level 1: Basically as shown on wikipedia.

Actually, it appears that whoever wrote the wikipedia article just grabbed the first couple sentences from each of the level summaries in the NIST doc, and as the summaries start with the physical requirements, that completely omits the interesting stuff.

Level 2: Also requires role-based auth to perform crypto operations, and requires that the hardware module be used from a computer meeting Common Criteria Protection Profiles (Annex B) and meeting CC EAL2. (whatever that means)

Level 3: Also requires identity-based auth, not just role-based.  Input or output of plaintext critical security parameters (passwords, keys, etc) must travel through physically or logically isolated ports.  Must meet Annex B plus a Trusted Path (the isolated ports thing), as well as EAL3.

Level 4: Also needs to meet EAL4.

(If it wasn't clear, Level n+1 also needs to meet all of the requirements for Level n.)

New questions/topics:

??? Pseudorandom function?  Pseudorandom permutation?  Pseudorandom generator?
??? Skipjack, key escrow, and general government chicanery
??? Thorp Shuffle?
??? Substitution–permutation network?
??? eSTREAM?
??? Play around with PKCS #11 a bit and get some code up.
??? Identity-based auth vs. just role-based?
??? Common Criteria Protection Profiles, Annex B?  EAL2/3/4?

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

Thursday, November 2, 2017

NaMeCryReNoWriMo, day 2: AES and GCM

AES (Advanced Encryption Standard)

AES is a symmetric block cipher, one of the most widely used and most secure (if used properly).  Although quantum computers would weaken AES (approximately cutting the effective key size in half), it's still feasible to use by simply doubling the key size.  This is distinctly better than, say, RSA, which becomes unusable due to how much faster quantum computers could potentially be at breaking it.

Originally called Rijndael, which they should've stuck with because it's way cooler.

Multiple different versions for different key sizes.

Based on a substitution-permutation network, meaning it's a mix of exchanging bits for other bits (substitution) and shuffling bits into new orders (permutation).  Due to the simplicity of these operations it's extremely fast in both hardware and software.  Most processors these days have specific logical circuits for it (I think?) and you can buy ICs specifically dedicated to performing AES operations.

AES is performed in rounds.  10 for 128-bit, 12 for 192-bit, and 14 for 256-bit.  It's performed on each 128 bits of the message, and it's done with the bits arranged in a 4x4 matrix of bytes.  Upper-left is the first byte, then it counts down and then right, so it's in the order:

00, 04, 08, 12
01, 05, 09, 13
02, 06, 10, 14
03, 07, 11, 15

In total, the algorithm is something vaguely resembling the following:

-Generate the keys for the rounds, using a set formula and the key provided by the user.  In total AES needs n+1 128-bit keys, where n is the number of rounds, so these are generated from the 128/192/256-bit main key.
-xor each byte of the block being encrypted with one of the bytes of the first round key
-Now, do the following n-1 times:
--A lookup table is used to do some non-linear substitution.
--Rotate the lower three rows of the matrix a number of times.
--Perform an (invertible) linear transformation on the columns of the matrix
--XOR in the next round key
-For the last round, don't do the linear transformation:
--Rotate rows
--XOR round key

There are attacks directly against AES that are faster than brute force, but none that appear to approach the level at which they could realistically be implemented.  However, modified versions of AES with a reduced number of rounds are potentially breakable, not than anyone uses AES with a reduced number of rounds and actually expects it to still be secure.

Most meaningful attacks against AES are side-channel attacks that don't attempt to break the cipher directly and instead rely on analyzing other information, such as how long it takes for an encryption to occur, what the resource usage of the machine performing the encryption is, and so on.

Modern intel processors have an AES throughput over 700MB/s

AES is a block cipher, so there are a number of different modes in which it can be used.  Based on glancing around online and talking with cryptographers, it sounds like GCM (Galois/counter mode) is the preferred mode.

??? Need to dive more into the details of the different transformations performed during the encryption process.

GCM (Galois/counter mode)

Mode of operation for symmetric key cryptographic block ciphers
authenticated encryption

Counter mode is just generating the keystream by encrypting successive values from a counter (1, 2, 3, etc).  Allows parallelization of both encryption and decryption and direct access to a specific part of the plaintext without decrypting the rest, because you can just increment the counter to whatever spot the block is at and generate the decryption key.
Although it sounds iffy to generate the keystream just from a basic counter like 1,2,3, as long as the cipher being used is secure, this is totally fine.  If there are security issues with it, that means that you're using a bad cipher, not that you should change the counter.

Galois refers to the authentication that's added on afterwards.
Based on Galois (finite) field multiplication.

Two functions, authenticated encryption and authenticated decryption

??? Need to study more math to understand how it works
??? What are the other modes of encrypting with symmetric block ciphers?

Galois fields (also called finite fields)

Field: A set of elements that has the operations multiplication, addition, division, and subtraction.  These operations must comply with:
-Associativity (addition and multiplication): a+(b+c)=(a+b)+c and a*(b*c)=(a*b)*c
-Commutativity (addition and multiplication): a+b=b+a and a*b=b*a
-Identity (addition and multiplication): There exist two elements 0 and 1 such that a+0=a and a*1=a
-Inverse (addition): For every element a, there exists an element denoted by -a such that a+(-a)=0
-Inverse (multiplication): For every element a apart from 0, there exists an element denoted by a^-1 or 1/a such that a*(1/a)=1
-Distributivity of multiplication over addition: a*(b+c)=(a*b)+(a*c)

Finite fields are (prepare to be shocked) fields that contain a (again, try not to fall off your chair) finite number of elements.  The number of elements is called the order of the field.  All finite fields contain p^k elements, where p is some prime number and k is a positive integer.  A common example is integers mod p, where p is a prime number.  As an example, let's look at integers mod 3: (0,1,2)
-Commutativity, associativity, identity, and distributivity are pretty clear so I'll skip them.
-Additive inverse?  Yep.  Inverses are (0, 2, 1), respectively. 0+0=0 is obvious.  2+1 = 3 = 0 mod 3 is a bit less clear if you aren't familiar with modular math.
-Multiplicative inverse?  Yep.  Inverses are (na, 2, 1), respectively.  0 has no multiplicative inverse, which is fine.  2*2 = 4 = 1 mod 3, and 1*1 = 1

??? Not a question, but wow do I need to refresh my college algebra.

Wednesday, November 1, 2017

National Meandering Crypto Refresher Notes Writing Month (NaMeCryReNoWriMo), day 1: TLS and KRACK

(Doesn't have quite the same ring to it as NaNoWriMo, but I've gotta work with what I have.)  I've been meaning to brush up on crypto for a while, so to help with that I'm going to post the notes I write up while reading stuff.  I'll try to make them vaguely followable but from day to day they'll jump around quite a bit depending on what I feel like reading about.  Also I won't necessarily write up notes for stuff I already know pretty well, so some of the basics will go completely uncovered.  Also also these will mostly be based on just reading a couple pieces about each topic, so it's likely there'll be quite the collection of fatal oversimplifications and straight-up errors.

At the end of every topic will be the list of questions it prompted, which is how I'll pick the next things to read about.

As a result, this is probably useless to everyone except for me, but if you happen to find it beneficial, cool.

TLS (Transport Layer Security) notes

Pages read:

Followup to Secure Sockets Layer (SSL).  SSL is no longer used due to vulnerabilities to POODLE and attacks on RC4.

Allows private, authenticated, integrous communication.
-Privacy: Asymmetric (public-key) cryptography is used to establish a symmetric session key, which provides encryption and makes it apparent if the messages are being altered (they'll likely become gibberish).  This encryption makes it so that anyone who sees the messages traveling over the wire can't see what they actually say.
-Authentication: Almost always, the server (the recipient of the initial connection request, not the initiator) uses an asymmetric certificate to demonstrate its identity.  This allows the caller to trust that it is who it says it is.  In certain cases the server will also require the client to demonstrate its identity in the same way.
-Integrity: Message authentication codes are used to make it clear when the message has changed in transit.

Some implementations of TLS provide forward secrecy, which means that even if the asymmetric keys used for the initial key exchange are exposed, any old communications are still secure.  This requires that the combination of the asymmetric keys and the data that was sent over the network are not sufficient to determine the session key.  If they're used to directly exchange a symmetric key, this doesn't work and old communications can be decrypted.  If they're used to encrypt something like a Diffie-Hellman key exchange, and the key generated during that exchange is deleted when the session is over, then forward secrecy is maintained.

Over time, there have been a couple versions of TLS, 1.0, 1.1, 1.2, and 1.3 (which is still incomplete).  These have fixed or improved aspects related to:
-Attacks on the CBC (cipher-block chaining) mode of symmetric encryption.
-Weaknesses in the MD5-SHA-1 hash function used in pseudorandom number generation.
-Added support for authenticated encryption like Galois/Counter Mode and CCM mode of AES.

What's (probably) changing in TLS 1.3?
-Certain weak elliptic curves are no longer supported.
-Certain weak hash functions (MD5 and SHA-224) are no longer supported.
-Adding support for HKDF.
-Adding support for PSK (pre-shared keys).
-Supporting faster handshakes (1 round-trip and moving towards 0 round-trip)
-Adding support for the ChaCha20 stream cipher with Poly1305 MAC
-Adding support for the Ed25519 and Ed448 digital signature algorithms.
-Adding support for the x25519 and x448 key exchange protocols.

What algorithms are supported in TLS1.3?
Initial key exchange:
-and possibly others.
Notably, the three listed above all offer forward secrecy.
-Camellia GCM

TLS1.2 has a handshake along the lines of the following:
Client: Yo server, I support (x,y,z) ciphers.
Server: Cool, let's use x.  Here's my part of the key exchange
Client: Awesome, here's my part.
Server: Looks legit.  Go on.
Client: (gets to start using the website)

TLS1.3 cuts down on round-trips by (basically) having the client guess what key the server will want to use:
Client: Yo server, I support (x,y,z) ciphers, and here's my part of the key exchange for x because x rocks.
Server: x is cool, so here's my part.
Client: Looks legit. (gets to start using the website)

I assume that if the server doesn't support x, it'll just fall back to the normal 2-round-trip process?  Haven't read through the explicit TLS1.3 spec yet so I'm not positive.

TLS1.3 also allows 0-round-trip session reestablishment by having the client and/or server cache one of the keys from the last time they communicated.

In general, TLS1.3 straight-up bans a lot of dumb stuff that was recommended against but still allowed in certain situations by TLS1.2

Open questions from this:

??? What's POODLE?
??? What's RC4?
??? What does the PKI and CAs look like that support TLS?
??? What exactly is a message authentication code?
??? What's Galois/Counter Mode?
??? What's CCM?
??? How exactly does AES function?
??? What's HKDF?
??? What's TLS-PSK?
??? What's ChaCha20 and Poly1305?
??? What are Ed25519 and Ed448?
??? What are x25519 and x448?
??? What are Camellia and ARIA?

KRACK (Key Reinstallation AttaCKs) notes

Pages read:

At the start of a WPA2 session, the device and the router perform a key handshake.  KRACK interferes with this handshake and performs a replay attack.  One of the messages of the handshake causes the client to set the key and nonce (IV) used to the initial value for the session.  By repeatedly sending this message, the 3rd in the 4-part handshake, the client can be made to send multiple messages encrypted using the same keystream (that is, the messages are encrypted by XORing them against the same stream of bytes) (because apparently WPA2 uses a stream cipher?).  With this, a single known message will let you decrypt all other messages encrypted with the same key.  This could be accomplished by finding a common header, or, if you can predict characteristics of the underlying data (for example, that it's likely ASCII text), this could be accomplished with a couple messages even without one being concretely known in advance.

If the TCP SYN packets are captured, the connection itself can be hijacked.

wpa_supplicant 2.4 and above (a wifi client commonly used on linux, and by extension, android) clears the negotiated key from memory after the first time it's told to install it, as apparently the spec for the protocol says that's something you can consider doing, and as a result the replay in the attack causes the installation of a key that's all 0s (or something like that).  That makes it even easier to eavesdrop.

Doesn't leak the actual WPA2 password.

Open questions from this:

??? How does the TCP hijack work?
??? What exact stream generator is used in WPA2, and what does the full handshake (or handshakes?) look like.
??? 4-way handshake? Fast BSS Transitional (FT) handshake?