Pollard's p-1 factorization algorithm posted March 2016

Got my graphic tablet back, needed to do a small video to get back into it so I made something on Pollard's p-1 factorization algorithm:

You can find the records on factoring with p-1 on loria.fr, the biggest prime factor found was of 66 digits (~220bits) using B1=10^8 and B2=10^10. But people have been using bigger parameters like B1=10^10 and B2=10^15. It doesn't really make sense to continue using p-1 after that, and more efficient algorithms that still have a complexity tied to the size of the smallest factor exist. The Elliptic Curve Method (Or Lenzstra factorization method) is one of them, and is carrying the same ideas as p-1 in the elliptic curves.

In the video I also don't talk about B2. This is if you have a factorization of p-1 that is B1-powersmooth, except for a large single prime. You can just set a B2 which would be larger than this last factor and try every factor between B1 and B2. There are some optimizations that exist to do that faster instead of doing it naively but this is it.

To_print posted March 2016

I have this list of papers that is accumulating in a folder. After an idea of @gtank I decided to print the whole (~150 two-sided pages) and go to my local UPS store to bind it for ~8$.

I'm not posting the pdf I printed here, but I made it with pdfjoin --paper letterpaper --rotateoversize false *, could have used pdfbook to make it smaller but after printing a few pages I felt that it would be too small for my weary eyes (now I sound like an old bag).

here's the list of the papers I printed. They all seem like you can print them without going to jail.

• Jos Wetzels - Open Sesame: The Password Hashing Competition and Argon2

• Craig Gentry - Computing Arbitrary Functions of Encrypted Data

• Scott Fluhrer - Scalar Blinding on Elliptic Curves with Special Structure

• Emission Security (it's a chapter in a book)

• Yuval Yarom Katrina Falkner - FLUSH+RELOAD: a High Resolution, Low Noise, L3 Cache Side-Channel Attack

• Joseph H. Silverman and Joe Suzuki - Elliptic Curve Discrete Logarithms and the Index Calculus (sorry for linking to Springer, but that one is for free)

• Phong Q. Nguyen - Lattice Reduction Algorithms: Theory and Practice

• Nadhem J. AlFardan and Kenneth G. Paterson - Lucky Thirteen: Breaking the TLS and DTLS Record Protocols

• Phong Q. Nguyen and Jacques Stern - Lattice Reductions in Cryptology: An Update

• Daniel J. Bernstein and Tanja Lange - Failures in NIST’s ECC standards

• Aanchal Malhotra and Sharon Goldberg - Attacking NTP’s Authenticated Broadcast Mode

• Boaz Barak - Hopes, Fears, and Software Obfuscation

• Tibor Jager and Jörg Schwenk and Juraj Somorovsky - On the Security of TLS 1.3 and QUIC Against Weaknesses in PKCS#1 v1.5 Encryption

• Neal Koblitz and Alfred J. Menezes - Another Look At “Provable Security”

• Neal Koblitz and Alfred J. Menezes - Another Look At “Provable Security” II

• Neal Koblitz - The Uneasy Relationship Between Mathematics and Cryptography

• Carl Pomerance - A Tale of Two Sieves

How are TLS records encrypted? posted March 2016

Once we are done with the handshake, both parties are now holding the same set of keys. Right after the Server sends its ChangeCipherSpec message it starts encrypting. Right after the Client sends his own ChangeCipherSpec he starts encrypting his messages as well.

The encrypted records still start with the type of record, the TLS version and the length of the following bytes in clear. The rest is encrypted.

We won't talk about compression because there are a bunch of vulnerabilities that should make you think twice about using compression. So here it is, null! (more about that)

Let's follow the TLS 1.2 RFC here

struct {
    ContentType type;
    ProtocolVersion version;
    uint16 length;
    select (SecurityParameters.cipher_type) {
        case stream: GenericStreamCipher;
        case block:  GenericBlockCipher;
        case aead:   GenericAEADCipher;
    } fragment;
} TLSCiphertext;

So as I said, we start with the type, the version and the length.

Right after the CipherSpecChange both parties will send an encrypted handshake message (a MAC of the whole transcript to authenticate the handshake), but most of the messages after will be encrypted Application data messages containing the real communications we want to protect.

0x17 is the byte for application data, then we have the TLS version, for TLS 1.2 it is 0x0303 (don't bother), then we have the length of the fragment which is described below for the AES-CBC case.

struct {
    opaque IV[SecurityParameters.record_iv_length];
    block-ciphered struct {
        opaque content[TLSCompressed.length];
        opaque MAC[SecurityParameters.mac_length];
        uint8 padding[GenericBlockCipher.padding_length];
        uint8 padding_length;
    };
} GenericBlockCipher;

So in the case of AES-128, you would have an IV of 16 bytes followed by the encrypted data.

Yup, the MAC is not here because it is encrypted. TLS is a MAC-then-encrypt construction (...), you can do encrypt-then-MAC in practice but through an extension (cf. RFC 7366).

The rest is pretty straight forward, after decryption of the block-ciphered structure you remove the padding, check the MAC, use the content.

Here's how the mac is used:

   MAC(MAC_write_key, seq_num +
                         TLSCompressed.type +
                         TLSCompressed.version +
                         TLSCompressed.length +
                         TLSCompressed.fragment);

where "+" denotes concatenation.

That's it for today!

Distinction between the TLS PRF for the Master Key and for the Keys posted March 2016

Last time I wrote about TLS pre-master keys and master keys.

I just realized one more thing in TLS that doesn't make sense (besides the fact that different versions of TLS have different PRFs). Here's RFC 5246 (the RFC on TLS 1.2) on how to use the PRF transform your pre-master key into a master key:

Here's the same RFC on how to use the PRF to transform your master key into your 4 or 6 keys:

Noticed anything?

Took me some time, the first takes the server random appended to the client random, while the second takes the client random appended to the server random. I'm willing to bet this is not to circumvent any attack but rather to confuse the implementer...

TLS, Pre-Master Secrets and Master Secrets posted March 2016

Everything you want to know about TLS 1.2 is in RFC 5246. But as you may know, if you've read RFCs before, it is not easy to parse (plus they have some sort of double spaces non-sense).

Before we can encrypt/MAC everything with keys to secure our connection, we need to go over a key exchange called the Handshake to safely agree on a set of keys for both parties to use. The handshake can currently use 5 different algorithms to do the key exchange: RSA, Diffie-Hellman, Elliptic Curve Diffie-Hellman and the ephemeral versions of the last two algorithms.

This blogpost is about what happens between this key exchange and the encryption/authentication of data.

The Pre-Master Secret

The pre-master key is the value you directly obtain from the key exchange (e.g. \(g^{ab} \pmod{p}\) if using Diffie-Hellman). Its length varies depending on the algorithm and the parameters used during the key exchange. To make things simpler, we would want a fixed-length value to derive the keys for any cipher suite we would want to use. This is the reason behind a pre master secret. The fixed-length value we'll call master secret. Here the RFC tells us how to compute it from the pre-master secret after having removed the leading zeros bytes.

master_secret = PRF(pre_master_secret, "master secret",
                    ClientHello.random + ServerHello.random)
                    [0..47];

The two random values ClientHello.random and ServerHello.random, sometimes called "nonces", are randomly generated and sent during the ClientHello of each parties. This is to bound the soon-to-be master key to this session. PRF stands for Pseudo-random function, basically some concrete construction that emulates a random oracle: given an input will produce an output computationally indistinguishable from a truly random sequence. But let's move on, and we will see later what exactly is that PRF.

The Master Secret

A master secret is always 48 bytes. So now that we have a fixed length value, we can derive 4 keys from it:

• client_write_MAC_key
• server_write_MAC_key
• client_write_key
• server_write_key

As you can probably guess, MAC keys are for the authentication and integrity with whatever MAC algorithm you chose in the cipher suite, write keys are for the symmetric encryption.

Interestingly, two keys are generated for every purpose: one key per side. This is mostly by respect of good practices. Always segregate the use of your keys.

The symmetric ciphers chosen in the handshake will dictate how long these keys we generate need to be. Note that AEAD ciphers that combine both authentication and encryption will not need MAC keys but will need two other keys instead: client_write_IV and server_write_IV. This is because their MAC keys are directly derived from the encryption keys.

The same PRF we used on the pre-master key will be used on the master-key over and over until enough bytes have been created for the keys. From the section 6.3 of the RFC:

key_block = PRF(SecurityParameters.master_secret,
                "key expansion",
                SecurityParameters.server_random +
                SecurityParameters.client_random);

The key_block value is then cut into enough keys.

That's it! Here's a recap:

Diffie-Hellman -> pre-master key -> 48bytes master key -> 4 variable-length keys.

The PRF

OK. Now that we got a nice global view of the process, let's dig deeper. The PRF used in TLS 1.2 is discussed here. It is quite different from the PRF used in TLS 1.1, see here.

Remember, for example how it was used to transform the pre-master key into a master key:

master_secret = PRF(pre_master_secret, "master secret",
                    ClientHello.random + ServerHello.random)
                    [0..47];

This is how the PRF function is used:

PRF(secret, label, seed) = P_<hash>(secret, label + seed)

If you want to follow along with code, here's the relevant golang code

P_hash(secret, seed) = HMAC_hash(secret, A(1) + seed) +
                       HMAC_hash(secret, A(2) + seed) +
                       HMAC_hash(secret, A(3) + seed) + ...

where + indicates concatenation, A() is defined as:

A(0) = seed
A(i) = HMAC_hash(secret, A(i-1))

This was a copy/paste from the RFC. To make it clearer: We use the label string ("master secret" in our example) concatenated with the two peers' random values as a seed.

We then MAC the seed with our pre-master secret as the key. We use the first output. Iterating the MAC gives us the subsequent values that we can append to our output.

\[ u_0 = label + serverHello.random + clientHello.random \]

\[ u_i = HMAC(secret, u_{i-1}) \]

\[ output = u_1 , u_2 , \cdots \] This goes on and on until the output is long enough to cover the 48 bytes of the master key (or the 4 keys if we're applying to PRF on the master key).

If P_256 is being used, then SHA-256 is being used. This means the output of HMAC will be 256 bits (32 bytes). To get the 48 bytes of the master key, two iterations are enough, and the remaining bytes can be discarded.

Discrete logarithms in Multiplicative prime groups posted March 2016

I'm doing some tests on how Pollard Rho performs. I implemented the thing in Sage here and it doesn't perform that well I found. Pollard Kangaroo is also bad, but that must come from my implementation (I didn't really go further here since I don't really need Kangaroo: I already know the order + the value I'm looking for is not in any particular interval)

old_rho is Pollard rho, rho_lambda is the mislabeled Pollard Kangaroo algorithm, trials is the simple enumeration.

I implemented the algorithm in Go, along some nice functions/variables that make Go's bignumber library a bit easier to tolerate. And guess what? What takes Sage 63 seconds to compute only take Go 5 seconds. The implementation is a copy/paste of what I did in Sage, no optimizations.

DROWN attack on OpenSSL posted March 2016

There is a new attack on OpenSSL. It's called DROWN.

Two problems:

1. in OpenSSL versions prior to January of this year, SSLv2 is by default not disabled. They thought that removing all the SSLv2 cipher suites from the default cipher string (back in 2010) would work but... nope. Even if not advertised in the serverHello, you can still do a handshake with whatever SSLv2 cipher you want. Another way of completely disabling SSLv2 exists, but it's recent and it is not the default option.

2. A padding oracle attack still exists in SSLv2. This is because of the export cipher suites. These weak ciphers and key lengths the USA government was forcing on OpenSSL so that people overseas could use it. So, these export cipher suites, nowadays they are bruteforce-able. It takes a few hours though, and a few hundred dollars, so no easy active MITM. It's a rather passive attack.

This is a cross-protocol attack. This means that you are a MITM, but you leave the client doing his thing on a TLS 1.2 or whatever SSLv3+ protocol. In the mean time though, you use the SSLv2 connection as an Oracle to recover the premaster-key (and thus the session key that is derived from it).

Three things:

1. The attack works on RSA handshakes. In the handshake (precisely in the clientKeyExchange) the client will encrypt his premaster-key with the server's RSA public key, this is what the attack decrypts. The server doesn't support RSA handshakes? You'll have to attack another server.

2. The server doesn't have to work with SSLv2. If another server (could even be a mail server) sharing the same RSA key and supporting SSLv2 exists, then you can use it as your oracle during the attack! Practical much?

3. To use the oracle, you need to first transform the RSA encrypted premaster-key into a valid SSLv2 RSA encrypted master-key. It is quite different, because of protocol differences, and you need to use quite a few tricks (trimmers!). It doesn't work all the time, around 1 out of 1,000 RSA encrypted premaster-key can be decrypted. This is often more than enough to steal the cookies and have consequences. If you're targeting a specific individual it can take time though, so to speed up these 1,000 handshakes just inject some javascript in a non-https webpage!

That's pretty much everything. I'm still going through the paper, trying to understand the math. There is a tool here to test your website. Another way of doing this (especially for internal servers) is to get an openssl version prior to january this year and do that on all of your subdomains/domains: openssl s_client -ssl2 -connect www.cryptologie.net:443

Briefs about crypto posted March 2016

I'm posting a bunch of things all the time on twitter/facebook. There are mostly quotes of things I'm reading and that I find interesting.

If you are a fan of learning by reading snippets of random crypto stuff you should follow me on twitter or/and facebook

here are the last ones:

So yeah. Follow me on twitter