Hey ! I'm David, a security consultant at Cryptography Services, the crypto team of NCC Group . This is my blog about cryptography and security and other related topics that I find interesting.

# Maybe you shouldn't skip SHA-3June 2017

Adam Langley from Google wrote a blogpost yesterday called Maybe Skip SHA-3. It started some discussions both on HN and on r/crypto

Speed drives adoption, Daniel J. Bernstein (djb) probably understand this more than anyone else. And this is what led Adam Langley to decide to either stay on SHA-2 or move to BLAKE2. Is that a good advice? Should we all follow his steps?

I think it is important to remember that Google, as well as the other big players, have an agenda for speed. I'm not saying that they do not care about security, it would be stupid for me to say that, especially seeing all of the improvements we've had in the field thanks to them in the last few years (Project Zero, Android, Chrome, Wycheproof, Tink, BoringSSL, email encryption, Key Transparency, Certificate Transparency, ...)

What I'm saying is that although they care deeply about security, they are also looking for compromises to gain speed. This can be seen with the push for 0-RTT in TLS, but I believe we're seeing it here as well with a push for either KangarooTwelve (K12) or BLAKE2 instead of SHA-3/SHAKE and BLAKE (which are more secure versions of K12 and BLAKE2).

Adam Langley even went as far as to recommend folks to stay on SHA-2.

But how can we keep advising SHA-2 when we know it can be badly misused? Yes I'm talking about length extension attacks. These attacks that prevent you from using SHA-2(key|data) to create a Message Authentication Code (MAC).

We recently cared so much about misuses of AES-GCM (documented misuses!) that Adam Langley's previous blog post to the SHA-3 one is about AES-GCM-SIV. We cared so much about simple APIs, that recently Tink simply removed the nonce argument from AES-GCM's API.

If we cared so much about documented misusage of crypto APIs, how can we not care about this undocumented misuse of SHA-2? Intuitively, if SHA-2 was to behave like a random oracle there would be no problem at all with the SHA-2(key|data) construction. Actually, none of the more secure hash functions like Blake and SHA-3 have this problem.

If we cared so much about simple APIs, why would we advise people to "fix" SHA-2 by truncating 256 bits of SHA-512's output (SHA-512/256)?

The reality is that you should use SHA-3. I'm making this as a broad recommendation for people who do not know much about cryptography. You can't go wrong with the NIST's standard.

Now let's see how we can dilute a good advice.

If you care about speed you should use SHAKE or BLAKE.

If you really care about speed you should use KangarooTwelve or BLAKE2.

If you really really care about speed you should use SHA-512/256. (edit: people are pointing to me that Blake2 is also faster than that)

If you really really really care about speed you should use CRC32 (don't, it's a joke).

How big of a security compromise are you willing to make? We know the big players have decided, but have they decided for you?

Is SHA-3 that slow?

Where is a hash function usually used? One major use is in signing messages. You hash the message before signing it because you can't sign something that is too big.

Here is a number taken from djb's benchmarks on how many cycles it takes to sign with ed25519: 187746

Here is a number taken from djb's benchmarks on how many cycles it takes to hash a byte with keccak512: 15

Keccak has a page with more numbers for software performance

Spoiler Alert: you probably don't care about a few cycles.

Not to say there are no cases where this is relevant, but if you're doing a huge amount of hashing and you're hashing big messages, you should rather switch to a tree-hashing mode. KangarooTwelve, BLAKE2bp and BLAKE2sp all support that.

EDIT: The Keccak team just released a response as well.

comments (8)

# Let's Encrypt OverviewJune 2015

## What is Let's Encrypt?

Basically, it's a way to get a quick x509 certificate for your server without knowing much about what is a x509 certificate:

You have a website. You want people to be able to log in on it from starbucks without the guy sitting at a near table reading the passwords in clear from the packets you're sending everyone around you. So you google a few random keywords like "secure website https" and you end up with a bunch of links and services (which may not be free) and you suddenly have to understand what are certificates, PKI, x509, public-key cryptography, RSA, FQDN, haaa.... Well, worry no more, Let's Encrypt was thought so that you wouldn't have to go through all that trouble and destroy your server on the way.

Oh and yeah. It's for free. But is hasn't been released yet.

## How does it work?

You can learn more reading their technical overview, or some of their videos... or read my tl;dr:

1. You download their program on your server that has the address www.example.com:
sudo apt-get install lets-encrypt
1. You run it as sudo telling it you want to get a certificate for your domain
lets-encrypt example.com

And voila.

Behing the curtains this is what happens:

1. lets-encrypt will generate a pair of RSA private key/public key and contact the CA with your public key.

2. The CA will register your public key

3. The program will then ask the CA to verify your domain.

4. The CA will answer with a set of challenges. These are some tasks you can complete to prove to the CA you own that domain. One of the common one is to upload a certain file at a certain address of that domain.

5. The program you installed will then do that for you and poll the CA for a confirmation

6. The CA will tell you "OK man, all is good".

7. The program will then generate another long term pair of private key/public key, generate a CSR (Certificate Signing Request) with the new public key and send that CSR to the CA.

8. The CA will extract the information, create a beautiful x509 certificate, sign it and send it back to you.

9. lets-encrypt will install the certificate on your server and set certain options (or not) to force https

By the way, the certificate you will get will be a DV certificate, meaning that they only verified that you owned the domain, nothing more. If you want an EV certificate this is what you will have to go through (according to wikipedia):

• Establish the legal identity as well as the operational and physical presence of website owner;
• Establish that the applicant is the domain name owner or has exclusive control over the domain name; and
• Confirm the identity and authority of the individuals acting for the website owner, and that documents pertaining to legal obligations are signed by an authorised officer.

## But how does it really work?

So! The lets-encrypt program you run on your server is open sourced here: https://github.com/letsencrypt/lets-encrypt-preview. It is called lets-encrypt-preview I guess because it isn't done yet. It's written in Python and has to be run in sudo so that it can do most of the work for you. Note that it will install the certificates on your server only if you are using Apache or Nginx. Also, the address of the CA is hardcoded in the program so be sure to use the official lets-encrypt.

The program installed on the CA is also open sourced! So that anyone can publicly review and audit the code. It's called Boulder and it's here: https://github.com/letsencrypt/boulder and written in Go.

Lets-encrypt and Boulder both use the protocol ACME for Automated Certificate Management Environment specified here as a draft: https://letsencrypt.github.io/acme-spec/

## ACME

ACME is written like a RFC. It actually wants to become an RFC eventually! So if you've read RFCs before you should feel like home.

The whole protocol is happening over TLS. As a result the exchanges are encrypted, you know that you are talking to the CA you want to talk to (eventhough you might not use DNSSEC) and replay attacks should be avoided.

The whole thing is actually a RESTful API. The client, you, can do GET or POST queries to certains URI on the CA webserver.

## Registration

The first thing you want to do is register. Registration is actually done by generating a new pair of RSA keys and sending them the public key (along with your info).

ACME specifies that you should use JWS for the transport of data. Json Web Signature. It's basically Json with authentication (so that you can sign your messages). It actually uses a variant of JWS called Jose that doesn't use a normal base64 encoding but that's all you should know for now. If you really want to know more there is an RFC for it.

So here what a request should look like with JWS (your information are sent unencrypted in the payload field (but don't worry, everything is encrypted anyway because the exchange happens over TLS)):

POST /acme/new-registration HTTP/1.1
Host: example.com

{
"payload":"<payload contents>",
"signatures":[
{"protected":"<integrity-protected header 1 contents>",
"header":<non-integrity-protected header 1 contents>,
"signature":"<signature 1 contents>"}
}

Boulder will check the signature with the public key you passed, verify the information you gave and eventually add you to its database.

Once you are registered, you can perform several actions:

• Update your infos
• Get one domain authorized (well actually as many as you'd like)

The server will authenticate you because you will now send your public key along AND you will sign your requests. This all runs on top of TLS by the way. I know I already said that.

## Boulder's guts

Boulder is separated in multiple components, this makes the code clearer and ensure that every piece of code does what it is supposed to do and nothing more.

One of the components is called the Web-Front-End (WFE) and is the only one accepting queries from the Client. It parses them, verifies them and passes them to the Registration Authority (RA) that combines the other authorities together to produce a response. The response is then passed back to the WFE and to the client over the ACME protocol. Are you following?

TWe'll see what other authorities the RA has access to in the next queries the client can do. But just to talk about the previous query, the new registration query, the RA talks to the Storage Authority that deals with the database (Which is currently SQLlite) to register your new account.

All the components can be run from a single machine (for the exception of the CA that runs on another library), but they can also be run seperately from different machines that will communicate on the same network via AMQP.

## New Authorization

Now that you are registered, you have to validate a domain before you can request a certificate.

You make a request to a certain URI.

Well to be exact you make a POST request to /new-authz, and the response will be 201 if it works. It will also give you some information about where you can go next to do stuff (/authz)

Here's the current list of API calls you can do and the relevant answers.

The server will pass the info to the Policy Authority (PA) and ask it if it is willing to accept such a domain. If so, it will then answer with a list of challenges you can complete to prove you own the domain, along with combinations of accepted challenges to complete. For now they only have two challenges and you can complete either one:

• SimpleHTTPS

• DVSNI

If you choose SimpleHTTPS the lets-encrypt client will generate a random value and upload something at the address formed by a random value the CA sent you and the random value you generated.

If you choose DVSNI, the client will create a TLS certificate containing some of the info of the challenge and with the public key associated to his account.

The client then needs to query the CA again and the CA's Validation Authority (VA) will either check that the file has been uploaded or will perform a handshake with the client's server and verify that specific fields of the certificates have been correctly filled. If everything works out the VA will tell the RA that will tell the WFE that will tell you...

After that you are all good, you can now make a Certificate Signing Request :)

## New Certificate

The agent will now generate a new pair of private key/public key. And create a CSR with it. So that your long term key used in your certificate is not the same as your let's encrypt account.

a CSR example, containing the identifier and the public key

After reception of it, the Web-Front-End of Boulder will pass it to the Registration Authority (RA) which will pass it to the Certificate Authority (CA) that will do all the work and will eventually sign it and send it back to the chain.

1: Client ---new-cert--> WFE
2:                       WFE ---NewCertificate--> RA
3:                                                RA ---IssueCertificate--> CA
4:                                                                          CA --> CFSSL
5:                                                                          CA <-- CFSSL
6:                                                RA <------return--------- CA
7:                       WFE <------return------- RA
8: Client <------------- WFE

Oh and also. the CA is talking to a CFSSL server which is CloudFlare's PKI Toolkit, a nice go library that you can use for many things and that is used here to act as the CA. CFSSL has recently pushed code to be compatible with the use of HSM which is a hardware device that you HAVE to use to sign keys when you are a CA.

After reception the lets-encrypt client will install the fresh certificate along with the chain to the root on your server and voila!

You can now revoke a certificate in the same way, but interestingly you won't need to sign the request with your account key, but with the private key associated to your certificate's public key. So that even if you lose your agent's key you can still revoke the certificate.

## Other stuff

There are a bunch of stuff that you will be able to do with the lets-encrypt client but that haven't been implemented yet:

• Renew a certificate
• Read the Terms of Service
• Query OCSP requests (see if a certificate has been revoked) ...

## Moar

This post is a simplification of the protocol. If you want to know more and don't want to dig in the ACME specs right now you can also take a look at Boulder's flow diagrams.

If you've followed the news you should have seen that Let's Encrypt just generated its root certificate along with several other certificates: https://letsencrypt.org/2015/06/04/isrg-ca-certs.html

This is because when you are a CA you are suppose to keep the root certificate offline. So you sign a (few) certificate(s) with that root, you lock that root and you use the signed certificate(s) to sign other certificates. This is all very serious because if something goes wrong with the root certificate, you can't revoke anything and well... the internet goes wrong as a result (until vendors start removing these from their list of trusted roots).
So the keys for the certificate have to be generated during a "ceremony" where everything is filmed and everyone must authenticate oneself at least with two different documents, etc... Check Wikipedia's page on Key Ceremony it's "interesting".

Also, I received a note from Seth David Schoen and I thought that was an interesting anecdote to share :)

the name "Boulder" is a joke from the American children's cartoon Looney Tunes:
https://en.wikipedia.org/wiki/Wile_E._Coyote_and_The_Road_Runner
This is because the protocol that Boulder implements is called ACME, which was also the name of the company that made the products unsuccessfully used by the coyote to attempt to catch the roadrunner. https://en.wikipedia.org/wiki/Acme_Corporation
Two of those products were anvils (the original name of the CA software) and boulders.

comments (19)

# TLS, Pre-Master Secrets and Master SecretsMarch 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.

comments (16)

# What are x509 certificates? RFC? ASN.1? DER?April 2015

## RFC

So, RFC means Request For Comments and they are a bunch of text files that describe different protocols. If you want to understand how SSL, TLS (the new SSL) and x509 certificates (the certificates used for SSL and TLS) all work, for example you want to code your own OpenSSL, then you will have to read the corresponding RFC for TLS: rfc5280 for x509 certificates and rfc5246 for the last version of TLS (1.2).

## x509

x509 is the name for certificates which are defined for:

informal internet electronic mail, IPsec, and WWW applications

There used to be a version 1, and then a version 2. But now we use the version 3. Reading the corresponding RFC you will be able to read such structures:

Certificate  ::=  SEQUENCE  {
tbsCertificate       TBSCertificate,
signatureAlgorithm   AlgorithmIdentifier,
signatureValue       BIT STRING  }

those are ASN.1 structures. This is actually what a certificate should look like, it's a SEQUENCE of objects.

• The first object contains everything of interest that will be signed, that's why we call it a To Be Signed Certificate
• The second object contains the type of signature the CA used to sign this certificate (ex: sha256)
• The last object is not an object, its just some bits that correspond to the signature of the TBSCertificate after it has been encoded with DER

## ASN.1

It looks small, but each object has some depth to it.

The TBSCertificate is the biggest one, containing a bunch of information about the client, the CA, the publickey of the client, etc...

TBSCertificate  ::=  SEQUENCE  {
version         [0]  EXPLICIT Version DEFAULT v1,
serialNumber         CertificateSerialNumber,
signature            AlgorithmIdentifier,
issuer               Name,
validity             Validity,
subject              Name,
subjectPublicKeyInfo SubjectPublicKeyInfo,
issuerUniqueID  [1]  IMPLICIT UniqueIdentifier OPTIONAL,
-- If present, version MUST be v2 or v3
subjectUniqueID [2]  IMPLICIT UniqueIdentifier OPTIONAL,
-- If present, version MUST be v2 or v3
extensions      [3]  EXPLICIT Extensions OPTIONAL
-- If present, version MUST be v3
}

## DER

A certificate is of course not sent like this. We use DER to encode this in a binary format.

Every fieldname is ignored, meaning that if we don't know how the certificate was formed, it will be impossible for us to understand what each value means.

Every value is encoded as a TLV triplet: [TAG, LENGTH, VALUE]

For example you can check the GITHUB certificate here

On the right is the hexdump of the DER encoded certificate, on the left is its translation in ASN.1 format.

As you can see, without the RFC near by we don't really know what each value corresponds to. For completeness here's the same certificate parsed by openssl x509 command tool:

## How to read the DER encoded certificate

So go back and check the hexdump of the GITHUB certificate, here is the beginning:

30 82 05 E0 30 82 04 C8 A0 03 02 01 02

As we saw in the RFC for x509 certificates, we start with a SEQUENCE.

Certificate  ::=  SEQUENCE  {

Microsoft made a documentation that explains pretty well how each ASN.1 TAG is encoded in DER, here's the page on SEQUENCE

30 82 05 E0

So 30 means SEQUENCE. Since we have a huge sequence (more than 127 bytes) we can't code the length on the one byte that follows:

If it is more than 127 bytes, bit 7 of the Length field is set to 1 and bits 6 through 0 specify the number of additional bytes used to identify the content length.

(in their documentation the least significant bit on the far right is bit zero)

So the following byte 82, converted in binary: 1000 0010, tells us that the length of the SEQUENCE will be written in the following 2 bytes 05 E0 (1504 bytes)

We can keep reading:

30 82 04 C8 A0 03 02 01 02

Another Sequence embedded in the first one, the TBSCertificate SEQUENCE

TBSCertificate  ::=  SEQUENCE  {
version         [0]  EXPLICIT Version DEFAULT v1,

The first value should be the version of the certificate:

A0 03

Now this is a different kind of TAG, there are 4 classes of TAGs in ASN.1: UNIVERSAL, APPICATION, PRIVATE, and context-specific. Most of what we use are UNIVERSAL tags, they can be understood by any application that knows ASN.1. The A0 is the [0] (and the following 03 is the length). [0] is a context specific TAG and is used as an index when you have a series of object. The github certificate is a good example of this, because you can see that the next index used is [3] the extensions object:

TBSCertificate  ::=  SEQUENCE  {
version         [0]  EXPLICIT Version DEFAULT v1,
serialNumber         CertificateSerialNumber,
signature            AlgorithmIdentifier,
issuer               Name,
validity             Validity,
subject              Name,
subjectPublicKeyInfo SubjectPublicKeyInfo,
issuerUniqueID  [1]  IMPLICIT UniqueIdentifier OPTIONAL,
-- If present, version MUST be v2 or v3
subjectUniqueID [2]  IMPLICIT UniqueIdentifier OPTIONAL,
-- If present, version MUST be v2 or v3
extensions      [3]  EXPLICIT Extensions OPTIONAL
-- If present, version MUST be v3
}

Since those obects are all optionals, skipping some without properly indexing them would have caused trouble parsing the certificate.

Following next is:

02 01 02

Here's how it reads:

_______ tag:      integer
|   ____ length: 1 byte
|  |   _ value:  2
|  |  |
|  |  |
v  v  v
02 01 02

The rest is pretty straight forward except for IOD: Object Identifier.

## Object Identifiers

They are basically strings of integers that reads from left to right like a tree.

So in our Github's cert example, we can see the first IOD is 1.2.840.113549.1.1.11 and it is supposed to represent the signature algorithm.

So go to http://www.alvestrand.no/objectid/top.html and click on 1, and then 1.2, and then 1.2.840, etc... until you get down to the latest branch of our tree and you will end up on sha256WithRSAEncryption.

Here's a more detailed explanation on IOD and here's the microsoft doc on how to encode IOD in DER.

comments (6)

# Schnorr's Signature and non-interactive ProtocolsDecember 2014

## Interactive Protocols

Interactive Protocols are basically a discussion between a Prover and a Verifier where the Prover has some piece of information he wants to prove, without giving out the information.

It is often illustrated with Peggy and Victor and their super tunnel.

Usualy it takes 3 steps:

1. Prover sends a fixed value.
2. Verifier sends a challenge.
3. Prover answers the challenge.

The Verifier can then verify the answer based on the fixed value. If the answer is correct, the Verifier can assume the Prover knows what he's trying to prove. Sometimes you have to repeat the protocols multiple time to be sure, and not all problems have an Interactive Proof.

Classic examples of such proofs can be found on the Discrete Logarithm problem (we'll talk about that later) and the Hamiltonian Cycle problem.

Interactive Protocols are verified if they are :

1. Complete: a Prover can successfully answer the challenge if he is honest.
2. Sound : a dishonest Prover cannot convince the Verifier he knows the secret.

In the real definitions we use probabilities (an honest prover still has a small chance of making a mistake, a dishonest prover still has a small chance of convincing the Verifier).

We also often want a 3rd condition on our Interactive Protocols: we want it to be Zero-knowledge, no information about our secret should be leaked in this interaction.

Here are how you prove each one of them:

1. Completeness: Can the Prover answer correctly thanks to his secret?
2. Soundness: From the point of view of the Verifier. If the Prover can correctly answer two different challenges for the same fixed value (however he crafted the answers and the fixed value), does it mean that he must know the secret then?
3. Zero-Knowledgeness: If you see a transcript of a recorded instance of this interaction, will you learn anything about the secret? (See if you can create fake transcripts)

There are also notions of weak Zero-knowledge, strong Zero-knowledge, dishonnest verifiers, etc...

But let's talk about something else.

## Non-interactive Protocols

Since we said that a recorded transcript of a past interaction has no value (if it is zero-knowledge), then we could assume that there is no way of proving something by showing an old transcript, or by showing a transcript with yourself.

Don't fool yourself! Yes we can. We do this by using hash functions that we deem random enough.

The idea is that, by replacing the Verifier by a random oracle, we cannot predict the challenges and we thus cannot craft a fake transcript (we like to use random oracles instead of hashes, to prove some scheme is secure).

a random oracle is an oracle (a theoretical black box) that responds to every unique query with a (truly) random response chosen uniformly from its output domain. If a query is repeated it responds the same way every time that query is submitted.

What is interesting is that this protocol was used in a Signature Scheme.

## Interactive Proof of a Discrete Logarithm

The most famous academic example of Interactive Protocol is done using the Discrete Logarithm problem.

we have <g> = G, with g of order q. The Prover wants to show he knows x in g^x = y.

1. the Prover sends t = g^e
2. the Verifier sends a challenge c
3. the Prover sends d = e + cx

The Verifier can then compute y^c * t = g^(e + cx) and see if it equals g^d = g^(e + cx)

A transcript would look like this: (t, c, d)

## Non-Interactive Proof of a Discrete Logarithm

Doing this with a non-interactive protocol, it would look like this:

(t, h(t), d) with h a hash function.

## Schnorr's Signature

This is what Schnorr's Signature is doing:

1. t = g^e
2. c = H(m || t)
3. d = e - x*c

he would then send (c, d) as the signature, along the message m. Which is basically a hash of the message with a proof that he knows the secret x.

To verify the signature you would use the public key y = g^x to compute y^c * g^d = t and then you would compute the hash. It would give you the proof that the signer knows x (authentication, non-repudiation) and that the message hasn't been tampered (integrity).

So this is one way of using Non-interactive proofs!

comments (1)

# 64-bit ciphers attack in 75 hours => AES-GCM attack in 75 hours?August 2016

There is a new attack/paper from the INRIA (Matthew Green has a good explanation on the attack) that continues the trend introduced by rc4nomore of long attacks. The paper is branded as "Sweet32" which is a collision attack playing on the birthday paradox (hence the cake in the logo) to break 64-bit ciphers like 3DES or Blowfish in TLS.

Rc4nomore was showing off with numbers like 52 hours to decrypt a cookie. This new attack needed more queries ($$2^{32}$$, hence the 32 in the name) and so it took longer in practice: 75 hours. And if the numbers are correct, this should answer the question I raised in one of my blogpost a few weeks ago:

the nonce is the part that should be different for every different message you encrypt. Some increment it like a counter, some others generate them at random. This is interesting to us because the birthday paradox tells us that we'll have more than 50% chance of seeing a nonce repeat after $$2^{32}$$ messages. Isn't that pretty low?

The number of queries here are the same for these 64-bit ciphers and AES-GCM. As the AES-GCM attack pointed:

we discovered over 70,000 HTTPS servers using random nonces

Does this means that 70,000 HTTPS servers are vulnerable to a 75 hours BEAST-style attack on AES-GCM?

Fortunately not, As the sweet32 paper points out, Not every server will allow a connection to be kept alive for that long. (It also seems like no browser place a limit on the amount of time a connection can be kept alive.) An interesting project would be to figure out how many of these 70,000 HTTPS servers are allowing long-lived connections.

It's good to note that these two attacks have different results as well. The sweet32 attack targets 64-bit ciphers like 3DES and Blowfish that really nobody use. The attack is completely impractical in that sense. Whereas AES-GCM is THE cipher commonly negociated. On the other hand, while both of them are Beast-style attacks, The sweet32 attack results in decrypting a cookie whereas the AES-GCM attack only allows you to redirect the user to a valid (but tampered) https page of the misbehaving website. In this sense the sweet32 attack has directly heavier consequences.

PS: Both Sean Devlin and Hanno Bock told me that the attacks are quite different in that the 64-bit one needs a collision on the IV or on a previous ciphertext. Whereas AES-GCM needs a collision on the nonce. This means that in the 64-bit case you can request for longer messages instead of querying for more messages, you also get more information with a minimum sized query than in a AES-GCM attack. This should make the AES-GCM even less practical, especially in the case of re-keying happening around the birthday bound.

comments (1)

# Babun, Cmder and TmuxFebruary 2015

I've used Cmder for a while on Windows. Which is a pretty terminal that brings a lot of tools and shortcuts from the linux world. I also have Chocolatey as packet manager. And all in all it works pretty great except Cmder is pretty slow.

I've ran into Babun yesterday, that seems to be kind of the same thing, but with zsh, oh-my-zsh and another packet manager: pact. The first thing I did was downloading tmux and learning how to use it. It works pretty well and I think I have found a replacement for Cmder =)

Here is a video of what is tmux:

comments (6)

# Breaking https' AES-GCM (or a part of it)August 2016

The coolest talk of this year's Blackhat must have been the one of Sean Devlin and Hanno Böck. The talk summarized this early year's paper, in a very cool way: Sean walked on stage and announced that he didn't have his slides. He then said that it didn't matter because he had a good idea on how to retrieve them.

He proceeded to open his browser and navigate to a malicious webpage. Some javascript there seemed to send various requests to a website in his place, until some MITM attacker found what they came for. The page refreshed and the address bar now whoed https://careers.mi5.gov.uk as well as a shiny green lock. But instead of the content we would have expected, the white title of their talk was blazing on a dark background.

What happened is that a MITM attacker tampered with the mi5's website page and injected the slides in a HTML format in there. They then went ahead and gave the whole presentation via the same mi5's webpage.

## How it worked?

The idea is that repeating a nonce in AES-GCM is... BAD. Here's a diagram from Wikipedia. You can't see it, but the counter has a unique nonce prepended to it. It's supposed to change for every different message you're encrypting.

AES-GCM is THE AEAD mode. We've been using it mostly because it's a nice all-in-one function that does encryption and authentication for you. So instead of shooting yourself in the foot trying to MAC then-and-or Encrypt, an AEAD mode does all of that for you securely. We're not too happy with it though, and we're looking for alternatives in the CAESAR's competition (there is also AES-SIV).

The presentation had an interesting slide on some opinions:

"Do not use GCM. Consider using one of the other authenticated encryption modes, such as CWC, OCB, or CCM." (Niels Ferguson)

"We conclude that common implementations of GCM are potentially vulnerable to authentication key recovery via cache timing attacks." (Emilia Käsper, Peter Schwabe, 2009)

"AES-GCM so easily leads to timing side-channels that I'd like to put it into Room 101." (Adam Langley, 2013)

"The fragility of AES-GCM authentication algorithm" (Shay Gueron, Vlad Krasnov, 2013)

"GCM is extremely fragile" (Kenny Paterson, 2015)

One of the bad thing is that if you ever repeat a nonce, and someone malicious sees it, that person will be able to recover the authentication key. It's the H in the AES-GCM diagram, and it is obtained by hashing the encryption key K. If you want to know how, check Antoine Joux' comment on AES-GCM.

Now, with this attack we lose integrity/authentication as soon as a nonce repeats. This means we can modify the ciphertext in the middle and no-one will realize it. But modifying the ciphertext doesn't mean we can modify the plaintext right? Wait for it...

Since AES-GCM is basically counter mode (CTR mode) with a GMac, the attacker can do the same kind of bitflip attacks he can do on CTR mode. This is pretty bad. In the context of TLS, you often (almost always) know what the website will send to a victim, and that's how you can modify the page with anything you want.

Look, this is CTR mode if you don't remember it. If you know the nonce and the plaintext, fundamentally the thing behaves like a stream cipher and you can XOR the keystream out of the ciphertext. After that, you can encrypt something else by XOR'ing the something else with the keystream :)

They found a pretty big number of vulnerable targets by just sending dozen of messages to the whole ipv4 space.

## My thoughts

Now, here's how the TLS 1.2 specification describe the structure of the nonce + counter in AES-GCM: [salt (4) + nonce (8) + counter (4)].

The whole thing is a block size in AES (16 bytes) and the salt is a fixed part of 4 bytes derived from the key exchange happening during TLS' handshake. The only two purposes of the salt I could think of are:

Pick the reason you prefer.

Now if you picked the second reason, let's recap: the nonce is the part that should be different for every different message you encrypt. Some increment it like a counter, some others generate them at random. This is interesting to us because the birthday paradox tells us that we'll have more than 50% chance of seeing a nonce repeat after $$2^{32}$$ messages. Isn't that pretty low?

comments (7)

# KangarooTwelveMay 2017

In late 2008, 64 candidates took part in NIST's hashing competition, fighting to replace the SHA-2 family of hash functions.

Keccak won the SHA-3 competition, and became the FIPS 202 standard on August 5, 2015.

All the other contenders lost. The final round included Skein, JH, Grøstl and BLAKE.

Interestingly in 2012, right in the middle of the competition, BLAKE2 was released. Being too late to take part in the fight to become SHA-3, it just stood on its own awkwardly.

Fast forward to this day, you can now read an impressive list of applications, libraries and standards making use of BLAKE2. Argon2 the winner of the Password Hashing Competition, the Noise protocol framework, libsodium, ...

On their page you can read:

BLAKE2 is a cryptographic hash function faster than MD5, SHA-1, SHA-2, and SHA-3, yet is at least as secure as the latest standard SHA-3. BLAKE2 has been adopted by many projects due to its high speed, security, and simplicity.

And it is indeed for the speed that BLAKE2 is praised. But what exactly is BLAKE2?

BLAKE2 relies on (essentially) the same core algorithm as BLAKE, which has been intensively analyzed since 2008 within the SHA-3 competition, and which was one of the 5 finalists. NIST's final report writes that BLAKE has a "very large security margin", and that the the cryptanalysis performed on it has "a great deal of depth". The best academic attack on BLAKE (and BLAKE2) works on a reduced version with 2.5 rounds, whereas BLAKE2b does 12 rounds, and BLAKE2s does 10 rounds. But even this attack is not practical: it only shows for example that with 2.5 rounds, the preimage security of BLAKE2b is downgraded from 512 bits to 481 bits, or that the collision security of BLAKE2s is downgraded from 128 bits to 112 bits (which is similar to the security of 2048-bit RSA).

And that's where BLAKE2 shines. It's a modern and secure hash function that performs better than SHA-3 in software. SHA-3 is fast in hardware, this is true, but Intel does not have a good track record of quickly implementing cryptography in hardware. It is only in 2013 that SHA-2 joined Intel's set of instructions, along with SHA-1...

What is being done about it?

Some people are recommending SHAKE. Here is what the Go SHA-3 library says on the subject:

If you aren't sure what function you need, use SHAKE256 with at least 64 bytes of output. The SHAKE instances are faster than the SHA3 instances; the latter have to allocate memory to conform to the hash.Hash interface.

But why is SHA-3 slow in software? How can SHAKE be faster?

This is because SHA-3's parameters are weirdly big. It is hard to know exactly why. The NIST provided some vague explanations. Other reasons might include:

• Not to be less secure than SHA-2. SHA-2 had 256-bit security against pre-image attacks so SHA-3 had to provide the same (or at least a minimum of) 256-bit security against these attacks. (Thanks to Krisztián Pintér for pointing this out.)
• To be more secure than SHA-2. Since SHA-2 revealed itself to be more secure than we previously thought, there was no reason to develop a similar replacement.
• To give some credits to the NIST. In view of people's concerns with NIST's ties with the NSA, they could not afford to act lightly around security parameters.

The following table shows the parameters of the SHAKE and SHA-3 constructions. To understand them, you need to understand two of the parameters:

• The rate (r): it is the block size of the hash function. The smaller, the more computation will have to be done to process the whole input (more calls to the permutation (f)).
• The capacity (c): it is the secret part of the hash function. You never reveal this! The bigger the better, but the bigger the smaller is your rate :)
 algorithm rate capacity mode (d) output length (bits) security level (bits) SHAKE128 1344 256 0x1F unlimited 128 SHAKE256 1088 512 0x1F unlimited 256 SHA3-224 1152 448 0x06 224 112 SHA3-256 1088 512 0x06 256 128 SHA3-384 832 768 0x06 384 192 SHA3-512 576 1024 0x06 512 256

The problem here is that SHA-3's capacities is way bigger than it has to be.

512 bits of capacity (secret) for SHA3-256 provides the square root of security against (second pre-image attacks (that is 256-bit security, assuming that the output used is long enough). SHA3-256's output is 256 bits in length, which gives us the square root of security (128-bit) against collision attacks (birthday bound). We end up with the same theoretical security properties of SHA-256, which is questionably large for most applications.

Keccak even has a page to tune its security requirements which doesn't advise such capacities.

Is this really the end?

Of course not. In the end, SHA-3 is a big name, people will use it because they hear about it being the standard. It's a good thing! SHA-3 is a good hash function. People who know what they are doing, and who care about speed, will use BLAKE2 which is equally as good of a choice.

But these are not the last words of the Keccak's team, and not the last one of this blog post either. Keccak is indeed a surprisingly well thought construction relying on a single permutation. Used in the right way it HAS to be fast.

Mid-2016, the Keccak team came back with a new algorithm called KangarooTwelve. And you might have guessed, it is to SHA-3 what BLAKE2 is to BLAKE.

It came with 12 rounds instead of 24 (which is still a huge number compared to current cryptanalysis) and some sane parameters: a capacity of 256 bits like the SHAKE functions.

Tree hashing, a feature allowing you to parallelize hashing of large files, was also added to the mix! Although sc00bz says that they do not provide a "tree hashing" construction but rather a" leaves stapled to a pole" construction.

credit: sc00bz

Alright, how does KangarooTwelve work?

First your input is mixed with a "customization string" (which allows you to get different results in different contexts) and the encoding of the length of the customization string (done with right_encode())

Second if the message is "short" (≤8192bytes), the tree hashing is not used. The previous blob is padded and permuted with the sponge. Here the sponge call is Keccak with its default multi-rate padding 101*. The output can be as long as you want like the SHAKE functions.

Third if the message is "long", it is divided into "chunks" of 8192 bytes. Each chunk (except the first one) is padded and permuted (so effectively hashed). The end result is structured/concatenated/padded and passed through the Sponge again.

This allows each different chunk to be hashed in parallel on different cores or via some SIMD magic.

Before you go, here is a simple python implementation and the reference C implementation.

Daemen gave some performance estimations for KangarooTwelve during the rump session of Crypto 2016:

• Intel Core i5-4570 (Haswell) 4.15 c/b for short input and 1.44 c/b for long input
• Intel Core i5-6500 (Skylake) 3.72 c/b for short input and 1.22 c/b for long input
• Intel Xeon Phi 7250 (Knights Landing) 4.56 c/b for short input and 0.74 c/b for long input

Thank-you for reading!

comment on this story

# Key Compromise Impersonation attacks (KCI)September 2016

You might have heard of KCI attacks on TLS: an attacker gets to install a client certificate on your device and can then impersonate websites to you. I had thought the attack was a highly impractical one, but looking at the video of the attack (done against facebook.com at the time) it seemed to contradict my first instinct.

I skimmed the paper and it answered some of my questions and doubts. So here's a tl;dr of it.

The issue is pretty easy to comprehend once you understand how a Diffie-Hellman key exchange works.

Imagine that you navigate to myCompany.com and you do a key exchange with both of your public keys.

• your public key: $$g^a \pmod{n}$$

• your company's public key: $$g^b \pmod{n}$$

where $$g$$ and $$n$$ are public parameters that you agreed on. Let's ignore $$n$$ from now on: here, both ends can create the shared secret by doing either $$(g^b)^a$$ or $$(g^a)^b$$.

In other words, shared secret = (other dude's public key)(my private key)

If you know either one of them's private key, you can observe the other public key (it's public!) and compute the shared secret. Then you have enough to replace one of the end in the TLS communication.

That's the theory.

If you replace the client's certificate with your own keypair, or know the private key of the certificate, you can break whatever key exchange they try to do with that certificate. What I mean by "break": from a key exchange you can compute the session keys and replace any party during the following communications.

My doubts had originally came from the fact that most implementations rarely use plain Diffie-Hellman, instead they usually offer ephemeral DH or RSA-based key exchanges (which are not vulnerable to this attack). The paper brought me back to reality:

Support for fixed DH client authentication has been very recently added to the OpenSSL 1.0.2 branch.

But then how would you make the client do such a un-used key exchange? The paper washed me from doubts once again:

the attacker, under the hood, interferes with the connection initialization to facebook, and forces the client to use an insecure handshake with client authentication, requesting the previously installed certificate from the system.

Now a couple of questions come to my mind.

How does facebook have these non-ephemeral DH ciphersuites?

→ from the paper, the server doesn't even need to use a static DH ciphersuite. If it has an ECDSA certificate, and didn't specify that it's only to be used to sign then you can use it for the attack (the keyUsage field in the certificate is apparently never used correctly, the few values listed in this RFC tell you how to correctly limit the authorized usages of your public key)

How can you trigger the client to use this ciphersuite?

→ just reply with a serverHello only displaying static ECDH in its ciphersuite list (contrarily to ECDHE, notice the last E for ephemeral). Then show the real ECDSA certificate (the client will interpret that as a ECDH cert because of the fake ciphersuites) and then ask the client for the specific cert you know the private key of.

In addition to the ECDSA → ECDH trumpery, this is all possible because none of these messages are signed at that moment. They are later authenticated via the shared secret, but it is too late =) I don't know if TLS 1.3 is doing a better job in this regard.

It also seems to me that in the attack, instead of installing a client cert you could just install a CA cert and MITM ALL TLS connections (except the pinned ones). But then, this attack is more sneaky, and it's another way of doing exactly this. So I appreciate that.

comments (1)

# Pohlig-Hellman AlgorithmDecember 2014

I'm reading through A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgoup which is a Small subgroup confinement attack.

It deals with stuff I had no knowledge of, like Schnorr's Signature that I talk about in a previous post, or like what I'm going to talk about now:

The Pohlig-Hellman Algorithm is a method to compute a Discrete Logarithm (which is a difficult problem) on a multiplicative group whose order is a smooth number (also called friable). Meaning its order can be factorized into small primes.

y = g^x mod p
ord_p(g) = p - 1
p - 1 = q_1^(i_1) * ... * q_j^(i_j)

Here y is the public key, x is the secret key we're trying to compute.
The order of g, our generator, is p - 1 since p is prime.
p - 1 is smooth so it can be factorized into something like 2^2 * 3 * 7 (extremely convenient example!)

Following is an overview of the method, if you read an equation and feel like it comes from nowhere (and it should feel like that), I posted a very short paper containing the simple proofs of those bellow.

## Overview

The idea that should come to your mind, if you're used to seeing that kind of problem, is that there might be a way to use the Chinese Remainder Theorem (abbreviated CRT) to our advantage. What if we could write x modulo the factors of p - 1 and then reconstruct the real x with the CRT? Well, let's do just that!

To write x modulo a factor q of p - 1 we can write y^((p-1) / q) which we know and can compute, and is also equal to g^(x_q * (p-1) / q)

(If you have a factor that appears multiple times in the prime decomposition of p - 1 (for example p - 1 = 2^5, then there is also a way to ease the computations by finding multiple unknowns (5 unknowns in our example))

We then have a discrete logarithm to compute, but a small one, that we can compute efficiently thanks to Shanks' method (baby-step giant-step) or Pollard's rho algorithm.

Then we have multiple ways of writing our x (modulo the factors of p - 1) and we find out what is x with CRT (I explained this step in my airbus write-up here).

## Proofs + Video

You can read through the Algorithm (or watch the video bellow), but I don't really like to do that since I'm not really good at memorizing something if I don't understand the nut and bolts of it. So here's a really good paper written by D. R. Stinson that demonstrate where the equations of the algorithm come from. And here's an explanation + example of the algorithm:

comment on this story

# ASN.1 vs DER vs PEM vs x509 vs PKCS#7 vs ....April 2015

I was really confused about all those acronyms when I started digging into OpenSSL and RFCs. So here's a no bullshit quick intro to them.

# PKCS#7

Or Public-Key Crypto Standard number 7. It's just a guideline, set of rules, on how to send messages, sign messages, etc... There are a bunch of PKCS that tells you exactly how to do stuff using crypto. PKCS#7 is the one who tells you how to sign and encrypt messages using certificates. If you ever see "pkcs#7 padding", it just refers to the padding explained in pkcs#7.

# X509

In a lot of things in the world (I'm being very vague), we use certificates. For example each person can have a certificate, and each person's certificate can be signed by the government certificate. So if you want to verify that this person is really the person he pretends to be, you can check his certificate and check if the government signature on his certificate is valid.

TLS use x509 certificates to authenticate servers. If you go on https://www.facebook.com, you will first check their certificate, see who signed it, checked the signer's certificate, and on and on until you end up with a certificate you can trust. And then! And only then, you will encrypt your session.

So x509 certificates are just objects with the name of the server, the name of who signed his certificate, the signature, etc...

Example from wikipedia:

Certificate
Version
Serial Number
Algorithm ID
Issuer
Validity
Not Before
Not After
Subject
Subject Public Key Info
Public Key Algorithm
Subject Public Key
Issuer Unique Identifier (optional)
Subject Unique Identifier (optional)
Extensions (optional)
...
Certificate Signature Algorithm
Certificate Signature

# ASN.1

So, how should we write our certificate in a computer format? There are a billion ways of formating a document and if we don't agree on one then we will never be able to ask a computer to parse a x509 certificate.

That's what ASN.1 is for, it tells you exactly how you should write your object/certificate

# DER

ASN.1 defines the abstract syntax of information but does not restrict the way the information is encoded. Various ASN.1 encoding rules provide the transfer syntax (a concrete representation) of the data values whose abstract syntax is described in ASN.1.

Now to encode our ASN.1 object we can use a bunch of different encodings specified in ASN.1, the most common one being used in TLS is DER

DER is a TLV kind of encoding, meaning you first write the Tag (for example, "serial number"), and then the Length of the following value, and then the Value (in our example, the serial number).

DER is also more than that:

DER is intended for situations when a unique encoding is needed, such as in cryptography, and ensures that a data structure that needs to be digitally signed produces a unique serialized representation.

So there is only one way to write a DER document, you can't re-order the elements.

And a made up example for an ASN.1 object:

OPERATION ::= CLASS
{
&operationCode INTEGER UNIQUE,

&InvocationParsType,

&ResponseParsAndResultType,

&ExceptionList ERROR OPTIONAL
}

And its DER encoding:

0110 0111 0010 110...

# Base64

Base64 is just a way of writing binary data in a string, so you can pass it to someone on facebook messenger for exemple

From the openssl Wiki:

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
0000000000111111111122222222223333333333444444444455555555556666
0123456789012345678901234567890123456789012345678901234567890123

And if you see any equal sign =, it's for padding.

So if the first 6 bits of your file is '01' in base 10, then you will write that as B in plaintext. See an example if you still have no idea about what I'm talking about.

# PEM

A pem file is just two comments (that are very important) and the data in base64 in the middle. For example the pem file of an encrypted private key:

-----BEGIN ENCRYPTED PRIVATE KEY-----
MIIFDjBABgkqhkiG9w0BBQ0wMzAbBgkqhkiG9w0BBQwwDgQIS2qgprFqPxECAggA
MBQGCCqGSIb3DQMHBAgD1kGN4ZslJgSCBMi1xk9jhlPxP3FyaMIUq8QmckXCs3Sa
9g73NQbtqZwI+9X5OhpSg/2ALxlCCjbqvzgSu8gfFZ4yo+Xd8VucZDmDSpzZGDod
X0R+meOaudPTBxoSgCCM51poFgaqt4l6VlTN4FRpj+c/WZeoMM/BVXO+nayuIMyH
blK948UAda/bWVmZjXfY4Tztah0CuqlAldOQBzu8TwE7WDwo5S7lo5u0EXEoqCCq
H0ga/iLNvWYexG7FHLRiq5hTj0g9mUPEbeTXuPtOkTEb/0ckVE2iZH9l7g5edmUZ
GEs=
-----END ENCRYPTED PRIVATE KEY-----

And yes the number of - are important

comments (8)

# Fault attacks on RSA's signaturesSeptember 2016

Facebook was organizing a CTF last week and they needed some crypto challenge. I obliged, missed a connecting flight in Phoenix while building it, and eventually provided them with one idea I had wanted to try for quite some time. Unfortunately, as with the last challenge I wrote for a CTF, someone solved it with a tool instead of doing it by hand (like in the good ol' days). You can read the quick write up there, or you can read a more involved one here.

## The challenge

The challenge was just a file named capture.pcap. Opening it with Wireshark would reveal hundreds of TLS handshakes. One clever way to find a clue here would be to filter them with ssl.alert_message.

From that we could observe a fatal alert being sent from the client to the server, right after the server Hello Done.

Mmmm

Several hypothesis exist. One way of guessing what went wrong could be to run these packets to openssl s_client with a -debug option and see why the client decides to terminate the connection at this point of the handshake. Or if you had good intuition, you could have directly verified the signature :)

After realizing the signature was incorrect, and that it was done with RSA, one of the obvious attack here is the RSA-CRT attack! Faults happen in RSA, sometimes because of malicious reasons (lasers!) or just because of random errors that can happen in different parts of the hardware. One random bit shifting and you have a fault. If it happens at the wrong place, at the wrong time, you have a cryptographic failure!

## RSA-CRT

RSA is slow-ish, as in not as fast as symmetric crypto: I can still do 414 signatures per second and verify 15775 signatures per second (according to openssl speed rsa2048).

Let's remember a RSA signature. It's basically the inverse of an encryption with RSA: you decrypt your message and use the decrypted part as a signature.

To verify a signature over a message, you do the same kind of computation on the signature using the public exponent, which gives you back the message:

We remember here that $$N$$ is the public modulus used in both the signing and verifying operations. Let $$N=pq$$ with $$p, q$$ two large primes.

This is the basis of RSA. Its security relies on the hardness to factor $$N$$.

I won't talk more about RSA here, so check Wikipedia) if you need a recap =)

It's also obvious for a lot of you reading this that you do not sign the message directly. You first hash it (this is good especially for large files) and pad it according to some specifications. I will talk about that in the later sections, as this distinction is not immediately important to us. We have now enough background to talk about The Chinese Remainder Theorem (CRT), which is a theorem we use to speed up the above equation.

So what if we could do the calculation mod $$p$$ and $$q$$ instead of this huge number $$N$$ (usually 2048 bits)? Let's stop with the what ifs because this is exactly what we will do:

Here we compute two partial signatures, one mod $$p$$, one mod $$q$$. With $$d_p = d \pmod{p-1}$$ and $$d_q = d \pmod{q-1}$$. After that, we can use CRT to stich these partial signatures together to obtain the complete one.

I won't go further, if you want to know how CRT works you can check an explanation in my latest paper.

## RSA-CRT fault attack

Now imagine that a fault happens in one of the equation mod $$p$$ or $$q$$:

Here, because one of the operation failed ($$\widetilde{s_2}$$) we obtain a faulty signature $$\widetilde{s}$$. What can we do with a faulty signature you may ask? We first observe the following facts on the faulty signature.

See that? $$p$$ divides this value (that we can calculate since we know both the faulty signature, the public exponent $$e$$, and the message). But $$q$$ does not divide this value. This means that $$\widetilde{s}^e - m$$ is of the form $$pk$$ with some integer $$k$$. What follows is naturally that $$gcd(\widetilde{s}^e - m, N)$$ will give out $$p$$! And as I said earlier, if you know the factorization of the public modulus $$N$$ then it is game over.

## Applying the RSA-CRT attack

Now that we got that out of the way, how do we apply the attack on TLS?

TLS has different kind of key exchanges, some basic ones and some ephemeral (forward secure) ones. The basic key exchange we've used a lot in the past is pretty straight forward: the client uses the RSA public key found in the server's certificate to encrypt the shared secret with it. Then both parties derive the session keys out of that shared secret

Now, if the client and the server agree to do a forward-secure key exchange, they will use something like Diffie-Hellman or Elliptic Curve Diffie-Hellman and the server will sign his ephemeral (EC)DH public key with his long term key. In our case, his public key is a RSA key, and the fault happens during that particular signature.

Now what's the message being signed? We need to check TLS 1.2's RFC:

struct {
select (KeyExchangeAlgorithm) {
...
case dhe_rsa:
ServerDHParams params;
digitally-signed struct {
opaque client_random[32];
opaque server_random[32];
ServerDHParams params;
} signed_params;
...
} ServerKeyExchange;
• the client_random can be found in the client hello message
• the server_random in the server hello message
• the ServerDHParams are the different parameters of the server's ephemeral public key, from the same TLS 1.2 RFC:
struct {
opaque dh_p<1..2^16-1>;
opaque dh_g<1..2^16-1>;
opaque dh_Ys<1..2^16-1>;
} ServerDHParams;     /* Ephemeral DH parameters */

dh_p
The prime modulus used for the Diffie-Hellman operation.

dh_g
The generator used for the Diffie-Hellman operation.

dh_Ys
The server's Diffie-Hellman public value (g^X mod p).

TLS is old, they use a non provably secure scheme to sign: PKCS#1 v1.5. Instead they should be using RSA-PSS but it's a whole different story :)

PKCS#1 v1.5's padding is pretty straight forward:

• The ff part shall be long enough to make the bitsize of that padded message as long as the bitsize of $$N$$
• The hash prefix part is a hexstring representing the hash function being used to sign

And here's the sage code!

# hash the signed_params

h = hashlib.sha384()
h.update(client_nonce.decode('hex'))
h.update(server_nonce.decode('hex'))
h.update(server_params.decode('hex'))
hashed_m = h.hexdigest()

# PKCS#1 v1.5 padding
prefix_sha384 = "3041300d060960864801650304020205000430"

modulus_len = (len(bin(modulus)) - 2 + 7) // 8
pad_len = len(hex(modulus))//2 - 3 - len(hashed_m)//2 - len(prefix_sha384)//2

padded_m = "0001" + "ff" * pad_len + "00" + prefix_sha384 + hashed_m

# Attack to recover p
p = gcd(signature^public_exponent - int(padded_m, 16), modulus)

# recover private key
q = modulus // p
phi = (p-1) * (q-1)

privkey = inverse_mod(public_exponent, phi)

## What now?

Now what? You have a private key, but that's not the flag we're looking for... After a bit of inspection you realize that the last handshake made in our capture.pcap file has a different key exchange: a RSA key exchange!!!

What follows is then pretty simple, Wireshark can decrypt conversations for you, you just need a private key file. From the previous section we retrieved the private key, to make a .pem file out of it (see this article to know what a .pem is) you can use rsatool.

Tada! Hope you enjoyed the write up =)

comments (3)

# Bruteforce Apr1 hashes.May 2014

One of my professor organized a Hacking Week this semester but I didn't have time to do it. Since I'm in holidays I thought I would take a look at it and write a bit about how I solved them.

Here's the Crypto Challenge number 2 (out of 5) from this CTF (Capture The Flag):

user0:$apr1$oTsx8NNn$bAjDZHpM7tCvHermlXKfZ0 user1:$apr1$UxOdpNtW$funTxZxL/8y3m8STvonWj0
user2:$apr1$w7YNTrjQ$0/71H7ze5o9/jCnKLt0mj0 user3:$apr1$AIw2h09/$Ti0TRlU9mDpCGm5zg.ZDP. user4:$apr1$048HynE6$io7TkN7FwrBk6PmMzMuyC. user5:$apr1$T2QG6cUw$eIPlGIXG6KZsn4ht/Kpff0 user6:$apr1$2aLkQ0oD$YRb6aFYMkzPoUCj70lsdX0 You have 7 different users with their respective password hashed and you have to find them. It's just the 2nd out of 5 crypto problems, it's pretty basic, but I never brute forced passwords for real before (I remember using John The Ripper when I was in middle school but that's for script kiddies). What's Apr1 ? It's a hash function that uses md5. And md5 is pretty weak, lots of rainbow tables on google. This is how Apr1 looks in PHP according to Wikipedia, also the passwords are supposed to be alpha (a to z) in lowercase. function apr1($mdp, $salt) {$max = strlen($mdp);$context = $mdp.'$apr1$'.$salt;
$binary = pack('H32', md5($mdp.$salt.$mdp));
for($i=$max; $i>0;$i-=16)
$context .= substr($binary, 0, min(16, $i)); for($i=$max;$i>0; $i>>=1)$context .= ($i & 1) ? chr(0) :$mdp{0};
$binary = pack('H32', md5($context));
for($i=0;$i<1000; $i++) {$new = ($i & 1) ?$mdp : $binary; if($i % 3) $new .=$salt;
if($i % 7)$new .= $mdp;$new .= ($i & 1) ?$binary : $mdp;$binary = pack('H32', md5($new)); }$hash = '';
for ($i = 0;$i < 5; $i++) {$k = $i+6;$j = $i+12; if($j == 16) $j = 5;$hash = $binary{$i}.$binary{$k}.$binary{$j}.$hash; }$hash = chr(0).chr(0).$binary{11}.$hash;
$hash = strtr( strrev(substr(base64_encode($hash), 2)),
'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/',
'./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
);
return '$apr1$'.$salt.'$'.$hash; } It seems pretty difficult to reverse. Let's not forget that hashes are one-way functions and that they also lose information. I don't know if they do lose information on a 7-letters-password though, but it seemed quite stupid to go down this road when I could just brute force it. What language offers a good library to hash with Apr1? Well I didn't know, and I felt like maybe Unix could do it well for me. Turns out that OpenSSL has a command line for it: openssl passwd -apr1 -salt SALT PASSWD A quick bash script later: #!/bin/bash test[1]='$apr1$oTsx8NNn$bAjDZHpM7tCvHermlXKfZ0'
salt[1]='oTsx8NNn'

test[2]='$apr1$UxOdpNtW$funTxZxL/8y3m8STvonWj0' salt[2]='UxOdpNtW' test[3]='$apr1$w7YNTrjQ$0/71H7ze5o9/jCnKLt0mj0'
salt[3]='w7YNTrjQ'

test[4]='$apr1$AIw2h09/$Ti0TRlU9mDpCGm5zg.ZDP.' salt[4]='AIw2h09/' test[5]='$apr1$048HynE6$io7TkN7FwrBk6PmMzMuyC.'
salt[5]='048HynE6'

test[6]='$apr1$T2QG6cUw$eIPlGIXG6KZsn4ht/Kpff0' salt[6]='T2QG6cUw' test[7]='$apr1$2aLkQ0oD$YRb6aFYMkzPoUCj70lsdX0'
salt[7]='2aLkQ0oD'

while read line
do
if [ "${#line}" == 7 ] then for num in {1..7} do noob=$(openssl passwd -apr1 -salt $salt[$num] $line) if [ "$noob" == "$test[$num]" ];
then
echo $line; fi done fi done < /usr/share/dict/words I read the /user/share/dict/words that contains a simple dictionary of words on Unix, I try only the 7-letters-words. The test ran in a few minutes and gave me nothing. Well, I guess with a 7 letters password they must have used gibberish words. Let's try a real bruteforce: for a in {a..z} do for b in {a..z} do for c in {a..z} do for d in {a..z} do for e in {a..z} do for f in {a..z} do for g in {a..z} do truc=$a$b$c$d$e$f$g;

for num in {1..7}
do
noob=$(openssl passwd -apr1 -salt$salt[$num]$truc)
if [ "$noob" == "$test[$num]" ]; then echo$truc;
fi
done
done
done
done
done
done
done
done

It ran and ran and... nothing.

Well. Let's not spend too much on this. There is John The Ripper that does this well and even oclHashcat that does this with the GPU.

Let's create a john.conf with the following to limit the password to 7 letters:

[Incremental:Alpha7]
File = \$JOHN/alpha.chr
MinLen = 7
MaxLen = 7
CharCount = 26

Let's launch John:

john -i=Alpha7 hackingweek.txt

(don't forget to put the hashed password in hackingweek.txt).

Wait and wait and wait.. and get the passwords =)

comment on this story

# Hash-Based Signatures Part I: One-Time Signatures (OTS)December 2015

## Lamport

On October 18th 1979, Leslie Lamport published his concept of One Time Signatures.

Most signature schemes rely in part on one-way functions, typically hash functions, for their security proofs. The beauty of Lamport scheme was that this signature was only relying on the security of these one-way functions.

here you have a very simple scheme, where $$x$$ and $$y$$ are both integers, and to sign a single bit:

• if it's $$0$$, publish $$x$$

• if it's $$1$$, publish $$y$$

Pretty simple right? Don't use it to sign twice obviously.

Now what happens if you want to sign multiple bits? What you could do is hash the message you want to sign (so that it has a predictible output length), for example with SHA-256.

Now you need 256 private key pairs:

and if you want to sign $$100110_2 \dots$$,

you would publish $$(y_0,x_1,x_2,y_3,y_4,x_5,\dots)$$

## Winternitz OTS (WOTS)

A few months after Lamport's publication, Robert Winternitz of the Stanford Mathematics Department proposed to publish $$h^w(x)$$ instead of publishing $$h(x)\|h(y)$$.

For example you could choose $$w=16$$ and publish $$h^{16}(x)$$ as your public key, and $$x$$ would still be your secret key. Now imagine you want to sign the binary $$1001_2$$ ($$9_{10}$$), just publish $$h^9(x)$$.

Another problem now is that a malicious person could see this signature and hash it to retrieve $$h^{10}(x)$$ for example and thus forge a valid signature for $$1010_2$$ ($$10_{10}$$).

This can be circumvented by adding a short Checksum after the message (which you would have to sign as well).

## Variant of Winternitz OTS

A long long time after, in 2011, Buchmann et al published an update on Winternitz OTS and introduced a new variant using families of functions parameterized by a key. Think of a MAC.

Now your private key is a list of keys that will be use in the MAC, and the message will dictates how many times we iterate the MAC. It's a particular iteration because the previous output is replacing the key, and we always use the same public input. Let's see an example:

We have a message $$M = 1011_2 (= 11_{10})$$ and let's say our variant of W-OTS works for messages in base 3 (in reality it can work for any base $$w$$). So we'll say $$M = (M_0, M_1, M_2) = (1, 0, 2)$$ represents $$102_3$$.

To sign this we will publish $$(f_{sk_1}(x), sk_2, f^2_{sk_3}(x) = f_{f_{sk_3}(x)}(x))$$

Note that I don't talk about it here, but there is still a checksum applied to our message and that has to be signed. This is why it doesn't matter if the signature of $$M_2 = 2$$ is already known in the public key.

Intuition tells me that a public key with another iteration would provide better security

here's Andreas Hulsing's answer after pointing me to his talk on the subject:

Why? For the 1 bit example: The checksum would be 0. Hence, to sign that message one needs to know a preimage of a public key element. That has to be exponentially hard in the security parameter for the scheme to be secure. Requiring an attacker to be able to invert the hash function on two values or twice on the same value only adds a factor 2 to the attack complexity. That's not making the scheme significantly more secure. In terms of bit security you might gain 1 bit (At the cost of ~doubling the runtime).

## Winternitz OTS+ (WOTS+)

There's not much to say about the W-OTS+ scheme. Two years after the variant, Hulsing alone published an upgrade that shorten the signatures size and increase the security of the previous scheme. It uses a chaining function in addition to the family of keyed functions. This time the key is always the same and it's the input that is fed the previous output. Also a random value (or mask) is XORed before the one-way function is applied.

Some precisions from Hulsing about shortening the signatures size:

WOTS+ reduces the signature size because you can use a hash function with shorter outputs than in the other WOTS variants at the same level of security or longer hash chains. Put differently, using the same hash function with the same output length and the same Winternitz parameter w for all variants of WOTS, WOTS+ achieves higher security than the other schemes. This is important for example if you want to use a 128 bit hash function (remember that the original WOTS requires the hash function to be collision resistant, but our 2011 proposal as well as WOTS+ only require a PRF / a second-preimage resistant hash function, respectively). In this case the original WOTS only achieves 64 bits of security which is considered insecure. Our 2011 proposal and WOTS+ achieve 128 - f(m,w) bits of security. Now the difference between WOTS-2011 and WOTS+ is that f(m,w) for WOTS-2011 is linear in w and for WOTS+ it is logarithmic in w.

## Other OTS

Here ends today's blogpost! There are many more one-time signature schemes, if you are interested here's a list, some of them are even more than one-time signatures because they can be used a few times. So we can call them few-times signatures schemes (FTS):

So far their applications seems to be reduce to be the basis of Hash-based signatures that are the current advised signature scheme for post quantum usage. See PQCrypto initial recommendations that was released a few months ago.

PS: Thanks to Andreas Hulsing for his comments

Part II of this series is here

comment on this story