david wong

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.

Is Symmetric Security Solved? June 2017

Recently T. Duong, D. Bleichenbacher, Q. Nguyen and B. Przydatek released a crypto library intitled Tink. At its center lied an implementation of AES-GCM somehow different from the rest: it did not take a nonce as one of its input.

A few days ago, at the Crypto SummerSchool in Croatia, Nik Kinkel told me that he would generally recommend against letting developers tweak the nonce value, based on how AES-GCM tended to be heavily mis-used in the wild. For a recap, if a nonce is used twice to encrypt two different messages AES-GCM will leak the authentication key.

I think it's a fair improvement of AES-GCM to remove the nonce argument. By doing so, nonces have to be randomly generated. Now the new danger is that the same nonce is randomly generated twice for the same key. The birthday bound tells us that after \(2^{n/2}\) messages, \(n\) being the bit-size of a nonce, you have great odds of generating a previous nonce.

The optimal rekey point has been studied by Abdalla and Bellare and can computed with the cubic root of the nonce space. If more nonces are generated after that, chances of a nonce collision are too high. For AES-GCM this means that after \(2^{92/3} = 1704458900\) different messages, the key should be rotated.

This is of course assuming that you use 92-bit nonces with 32-bit counters. Some protocol and implementations will actually fix the first 32 bits of these 92-bit nonces reducing the birthday bound even further.

Isn't that a bit low?

Yes it kinda is. An interesting construction by Dan J. Bernstein called XSalsa20 (and that can be extended to XChacha20) allow us to use nonces of 192 bits. This would mean that you should be able to use the same key for up to \(2^{192/3} = 18446744073709551616\) messages. Which is already twice more that what a BIG INT can store in a database

It seems like Sponge-based AEADs should benefit from large nonces as well since their rate can store even more bits. This might be a turning point for these constructions in the last round of the CAESAR competition. There are currently 4 of these: Ascon, Ketje, Keyak and NORX.

With that in mind, is nonce mis-use resistance now fixed?

EDIT: Here is a list of recent papers on the subject:

comment on this story

Implementation of Kangaroo Twelve in Go June 2017

I've released an implementation of KangarooTwelve in Go

It is heavily based on the official Go's x/crypto/sha3 library. But because of minor implementation details the relevant files have been copied and modified there so you do not need Go's SHA-3 implementation to run this package. Hopefully one day Go's SHA-3 library will be more flexible to allow other keccak construction to rely on it.

I have tested this implementation with different test vectors and it works fine. Note that it has not received proper peer review. If you look at the code and find issues (or not) please let me know!

See here why you should use KangarooTwelve instead of SHA-3. But see here first why you should still not skip SHA-3.

This implementation does not yet make use of SIMD to parallelize the implementation. But we can already see improvements due to the smaller number of rounds:

100 bytes1000 bytes10,000 bytes
K12761 ns/op1875 ns/op15399 ns/op
SHA3854 ns/op3962 ns/op34293 ns/op
SHAKE128668 ns/op2853 ns/op29661 ns/op

This was done with a very simple bench script on my 2 year-old macbook pro.

comment on this story

Maybe you shouldn't skip SHA-3 June 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)

Loop unrolling May 2017

Reading cryptographic implementations, you can quickly spot a lot of weirdness and oddities. Unfortunately, this is because very few cryptographic implementations aim for readability (hence the existence of readable implementations). But on the other hand, there are a lot of cool techniques in there which are interesting to learn about.

Bit-slicing is one I've never really talked about, so here is a self-explanatory tweet quoting Thomas Pornin:

But I'm here to talk about loop unrolling. Here's what wikipedia has to say about it:

Loop unrolling, also known as loop unwinding, is a loop transformation technique that attempts to optimize a program's execution speed at the expense of its binary size, which is an approach known as the space-time tradeoff.

Want to see an example? Here's how Keccak was implemented in go

While the θ step could have easily fit in a loop:

for x := 0; x < 5; x++ {
    B[x] = a[x][0] ^ a[x][1] ^ a[x][2] ^ a[x][3] ^ a[x][4]
}

It was unrolled to allow for faster execution, getting rid of loop registers and checks for the end of the loop at every iteration:

// Round 1
bc0 = a[0] ^ a[5] ^ a[10] ^ a[15] ^ a[20]
bc1 = a[1] ^ a[6] ^ a[11] ^ a[16] ^ a[21]
bc2 = a[2] ^ a[7] ^ a[12] ^ a[17] ^ a[22]
bc3 = a[3] ^ a[8] ^ a[13] ^ a[18] ^ a[23]
bc4 = a[4] ^ a[9] ^ a[14] ^ a[19] ^ a[24]
d0 = bc4 ^ (bc1<<1 | bc1>>63)

Here is an implementation of MD5 in go. You can see that the gen.go file is generating a different md5block.go file which will be the unrolled code. Well yeah, sometimes it's just easier than doing it by hand :]

Here is an implementation of SHA-1 in assembly.

It's assembly, I'm not going to try to explain that.

Here's another example with Keccak in C. The unrolling is done in the preprocessing phase via C macros like this one:

#define REPEAT5(e) e e e e e

That's it! If you still haven't got it, you might have the qualities to run for president.

If you know more tricks let me know!

comment on this story

StrobeGo May 2017

I wrote an opinionated and readable implementation of the Strobe Protocol Framework in Go here.

It hasn't been thoroughly tested, and its main goal was to help me understand the specification of Strobe while kicking around ideas to challenge the spec.

It started a discussion on the mailing list if you're interested.

I hope that this implementation can help someone else understand the paper/spec better. The plan is to have a usable implementation by the time Strobe's specification is more stable (not that it isn't, its version is actually 1.0.2 at the moment).

Following is a list of divergence from the current specification:

Operate

The main Operate public function that allows you to interact with STROBE as a developer has a different API. In pseudo code:

Operate(meta bool, operation string, data []byte, length int, more bool) → (data []byte)

I've also written high level functions to call the different known operations like KEY, PRF, send_ENC, etc... One example:

// `meta` is appropriate for checking the integrity of framing data. 
func (s *strobe) send_MAC(meta bool, output_length int) []byte {
  return s.Operate(meta, "send_MAC", []byte{}, output_length, false)
}

The meta boolean variable is used to indicate if the operation is a META operation.

// operation is meta?
if meta {
    flags.add("M")
}

What is a META operation? From the specification:

For any operation, there is a corresponding "meta" variant. The meta operation works exactly the same way as the ordinary operation. The two are distinguished only in an "M" bit that is hashed into the protocol transcript for the meta operations. This is used to prevent ambiguity in protocol transcripts. This specification describes uses for certain meta operations. The others are still legal, but their use is not recommended. The usage of the meta flag is described below in Section 6.3.

Each operation that has a relevant META variant, also contains explanation on it. For example the ENC section:

send_meta_ENC and recv_meta_ENC are used for encrypted framing data.

The operations are called via their strings equivalent instead of their flag value in byte. This could in theory be irrelevant if only the high level functions were made available to the developers.

A length argument is also available for operations like PRF, send_MAC and RATCHET that require a length. A non-zero length will create a zero buffer of the required length, which is not optimal for the RATCHET operation.

// does the operation requires a length?
if operation == "PRF" || operation == "send_MAC" || operation == "RATCHET" {
    if length == 0 {
      panic("A length should be set for this operation.")
    }

    // create an empty data slice of the relevant size
    data = bytes.Repeat([]byte{0}, length)

} else {
    if length != 0 {
      panic("Output length must be zero except for PRF, send_MAC and RATCHET operations.")
    }

    // copy the data not to modify the original data
    data = make([]byte, len(data_))
    copy(data, data_)
}

Verbose

One of my grip with the Strobe's specification is that nothing is truly explained through words: the reader is expected to follow reference snippets of code written in Python. Everything has been optimized and it is quite hard to understand what is really happening (hence why I wrote this implementation in the first place). To remediate this, I wrote a clear path of what is happening for each operation. It is great for other readers who want to understand what is happening, but obviously not the optimal thing to do for an efficient implementation :)

It looks like a bunch of if and else if (Go does not have support for switch):

if operation == "AD" { // A
    // nothing happens
} else if operation == "KEY" { // AC
    cbefore = true
    forceF = true
} else if operation == "PRF" { // IAC
    cbefore = true
    forceF = true
    ...

_Duplex

I have omited any function name starting with _ as Go has a different way of making functions available out of a package: make the first letter upper case.

The _duplex function was written after Golang's official SHA-3 implementation and is not optimal. The reason is that SHA-3 does not need to XOR anything in the state until after either the end of the rate (block size) or the end of the input has been reached. Because of this, Go's SHA-3 implementation waits for these to happen while STROBE often cannot: STROBE often needs the result right away. This led to a few oddities.

pos

I do not use the pos variable as it is easily obtainable from the buffered state. This is another (good) consequence of Go's decision on waiting before running the Keccak function. Some other implementations might want to keep track of it.

cur_flags

The specification states that cur_flags should be initialized to None. Which is annoying to program (see how I did it for I0). This is why I took the decision that a flag cannot be zero, and I'm initializing cur_flags to zero.

I'm later asserting that the flag is valid, according to a list of valid flags

// operation is valid?
var flags flag
var ok bool
if flags, ok = OperationMap[operation]; !ok {
    panic("not a valid operation")
}

R is always R

The specification states that the initialization should be done with R = R + 2. This is to have a match with cSHAKE's padding when using some STROBE instances like Strobe-128/1600 and Strobe-256/1600.

I like having constants and not modifying them. So I initialize with a smaller rate (block_size) and do not conform with cSHAKE's specification. Is it important? I think yes. It does not make sense to use cSHAKE's padding on Strobe-128/800, Strobe-256/800 and Strobe-128/400 as their rate is smaller than cSHAKE's defined rate in its padding.

EDIT: I ended up reverting this change. As I only implemented Strobe-256/1600, it is easy to conform to cSHAKE by just initializing with R + 2 which will not modify the constant R.

comments (3)

Crypto Blogging Award 2016 May 2017

I spent a lot of time reading this blogpost today and thought to myself: this is a great blog post. If there was a blogging award for security/crypto blogposts this would probably be the front runner for 2017.

But I can't really blog about it, because we're still waiting for a lot more good blog posts to come this year.

So what I decided to do instead, is to go through all the blog posts that I liked last year (it's easy, I have a list here) and find out which ones stood out from the rest.

please do not get offended if yours is not in there, I might have just missed it!

How does a blog post make it to the list? It has to be:

  • Interesting. I need to learn something out of it, whatever the topic is. If it's only about results I'm generally not interested.
  • Pedagogical. Don't dump your unfiltered knowledge on me, I'm dumb. Help me with diagrams and explain it to me like I'm 5.
  • Well written. I can't read boring. Bonus point if it's funny :)

So here it is, a list of my favorite Crypto-y/Security blogposts for the year of 2016:

Did I miss one? Make me know in the comments :]

comment on this story

Tamarin looking for sources May 2017

Tamarin will sometimes be unable to find the real source of a premise ([premise]-->[conclusion]) and will end up spinning until the scary words "partial deconstructions" will be flashed at the screen.

loops

Raw sources is Tamarin trying to find the source of each of your rules. That's a bunch of pre-computation to help him prove things afterwards, because Tamarin works like that under the hood (or so I've heard): it searches for things backward.

(This might be a good reason to start designing your protocol from the end!)

Partial deconstructions can happen when for example you happen to have used a linear fact both in the premise and the conclusion of a rule:

rule creation:
  [Fr(~a)]-->[Something(~a)]

rule loop:
  [Something(a)]-->[Something(a), Out(a)]

This is bad, because when looking for the source of the loop rule, Tamarin will find the loop rule as a possible origin. This over and over and over.

Source lemmas are special lemmas that can be used during this pre-computation to get rid of such loops. They basically prove that for such loop rules, there is a beginning: a creation rule. Source lemmas are automatically proven using induction which is the relevant strategy to use when trying to prove such things.

Refined sources are the raw sources helped by the source lemmas. If your wrote the right source lemmas, you will get rid of the partial deconstructions in the refined sources and Tamarin will use the refined sources for its proofs instead of the raw sources.

Persistent Facts is the answer. Anytime we have a linear fact persisting across a rule, there is little reason (I believe) not to use a persistent fact (which also allows to model replays in the protocol). We can now rewrite our previous rules with a bang:

rule creation:
  [Fr(~a)]-->[!Something(~a)]

rule loop:
  [!Something(a)]-->[Out(a)]

This way Tamarin will always correlate this Fact to its very creation.

comment on this story

How to obtain a nice trace in Tamarin May 2017

ugly trace

This is not a nice trace

Learning about the inners of Tamarin, I've came up to the point where I wanted to get a nice clean trace to convince myself that the protocol I wrote made sense.

The way to check for proper functioning is to create exist-trace lemmas.

Unfortunately, using Tamarin to prove such lemma will not always yield the nicest trace.

Here are some tricks I've used to obtain a simple trace. Note that these matter less when you're writing lemmas to "attack" the protocol (as you really don't want to impose too many restrictions that might not hold in practice).

1. Use a fresh "session id". A random session id can be added to different states and messages to identify a trace from another one.

rule client_start_handshake:
    [!Init($client, ~privkey, pubkey), !Init($server, ~priv, pub), Fr(~sid)]
    --[Start(~sid, $client, $server)]->
    [Out(<'1', ~sid, $client, $server, pubkey>)]

2. Use temporals to make sure that everything happens in order.

Ex sid, client, server, sessionkey #i #j.
      Start(sid, client, server) @ #i & 
      Session_Success(sid, 'server', server, client, sessionkey) @ #j &
    #i < #j

3. Make sure your identities are different. Start by defining your lemma by making sure a server cannot communicate with itself.

Ex sid, client, server, sessionkey #i #j.
      not(server = client) & ...

4. Use constraints to force peers to have a unique key per identity. Without that, you cannot force Tamarin to believe that one identity could create multiple keys. Of course you might want your model to allow many-keys per identity, but we're talking about a nice trace here :)

restriction one_key_per_identity: "All X key key2 #i #j. Gen(X, key) @ #i & Gen(X, key2) @ #j ==> #i = #j"

rule generate_identity_and_key:
    let pub = 'g'^~priv
    in
    [ Fr(~priv) ]--[Gen($A, pub)]->[ !Init($A, ~priv, pub) ]

5. Disable the adversary. This might be the most important rule here, and it ended up being the breakthrough that allowed me to find a nice trace. Unfortunately you cannot disable the adversary, but you can force Ins and Outs to happen via facts (which are not seen by the adversary, and remove any possible interaction from the adversary). For this you can replace every In and Out with InSecure and OutSecure and have these rules:

#ifdef not_debug
[OutSecure(a)] -->[Out(a)]
[In(a)] -->[InSecure(a)]
#endif

#ifdef debug
[OutSecure(a)]-->[InSecure(a)]
#endif

You can now call tamarin like this:

tamarin interactive . -Dnot_debug

And we now have a nice trace!

nice trace

Our protocol is an opportunistic Diffie-Hellman. You can see the two generate_identity_and_key rules at the top that creates the two different identities: a client and a server.

The second rule client_start_handshake is used to start the handshake. The client sends the first message 1 with a fresh session id ~sid.

The third rule server_handshake propagates the received session id to the next message and to its action fact (so that the lemma can keep the session id consistent).

The protocol ends in the last rule client_handshake_finish being used.

Voila!

PS: thanks to Katriel Cohn-Gordon for answering ten thousands of my questions about Tamarin.

comment on this story

Bug in KangarooTwelve's reference implementation May 2017

When playing around with KangarooTwelve I noticed that the python implementation's right_encode() function was not consistent with the C version:

python implementation of right_encode

λ python right_encode.py            
right_encode(0): [0]
right_encode(1): [1][3]
right_encode(2): [2][3]
right_encode(255): [255][5]
right_encode(256): [1][0][6]
right_encode(257): [1][1][6]

C implementation of right_encode:

λ ./right_encode        
right_encode(0): 00
right_encode(1): 0101
right_encode(2): 0201
right_encode(255): ff01
right_encode(256): 010002
right_encode(257): 010102

The problem was that the python implementation used the function bytes() to create byte strings, which has breaking behaviors between python2 and python3.

python2:

>>> bytes([1])
'[1]'

python3:

>>> bytes([1])
b'\x01'

The fix was to use bytearray() instead which is consistent across the two versions of Python.

comment on this story

KangarooTwelve May 2017

kangaroo twelve

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.

sponge

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 :)
algorithmratecapacitymode (d)output length (bits)security level (bits)
SHAKE12813442560x1Funlimited128
SHAKE25610885120x1Funlimited256
SHA3-22411524480x06224112
SHA3-25610885120x06256128
SHA3-384832 7680x06384192
SHA3-512576 10240x06512256

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.

tune keccak

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.

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())

input kangarootwelve

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.

short message kangarootwelve

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.

long message kangarootwelve

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

Strobe's padding May 2017

Let me re-introduce STROBE: it's a protocol framework based on the Duplex construction. It's kind of the symmetric part of TLS if you will, where everything depends on what happened previously. Kind of like when Noise uses the hash of the entire transcript to derive new keys.

duplex

You can do different things with different "operations". Encrypt some plaintext, generate some MAC, generate some random numbers, etc... These different operations can be combined to form a protocol, or can be used as stand-alone in your logic. This is one of the beautiful aspect of STROBE (heavily based on the beauty of Keccak): it provides you with numerous primitives with only a few APIs, and thus a very small source code: count 1,046 lines of code for the current reference implementation in C.

But like anything based on Keccak, you need a padding and it has to be complicated :)

Duplex Calls

The initialization of a Strobe object is done with cSHAKE by XOR'ing this data: [1,self.R,1,0,1,12*8, "STROBEv1.0.2"] then permuting the state.

After the initialization, for every duplex call (before a permutation happens) a padding is applied. This successfully allows series of duplex call to be seen as one cSHAKE call. The rest of this article explains how duplex calls work. These duplex calls are made of potentially multiple operations combined with a padding function, which in STROBE is a combination of cSHAKE's padding and STROBE's own padding.

if we just started an operation:

[old_begin, flag, data up until the block size (strobe.R)]

flag is one byte computed from:

  • The direction of the message when sending or receiving data (I_0).
  • The type of operation.

old_begin is the start of the last operation in the current block. It can be seen as the pos_begin of the previous operation. It is computed as:

  • If we're starting an operation in a new block: 0. The older operation happened in a previous block.
  • If we’re starting an operation in the same block as the previous operation: the starting position of the previous operation in the current block.

if we have already started an operation:

[data up until the block size (strobe.R)]

when a permutation is called (forced or because we reached the blocksize) append:

[pos_begin, cSHAKE's padding = 0x04, 0x00 ... 0x00, 0x80]

pos_begin is the start of our operation in the current block, it is computed as:

  • If we're starting the operation on a fresh block: 1. (At index 0 is the value old_begin which can be seend as the padding of the previous operation.)
  • If we've already started the operation and already ran F once: 0, indicating that the operation started in a previous block.
  • if we're starting the operation, and we're in the same block of another operation: the position of the new operation (which starts at the flag, not the old_begin)

Examples

Example 1: the second operation starts on a new block

block1[old_begin=0, flag, data_1, ..., data_R-2, pos_begin=1, padding= 0x04, 0x80] // the first operation takes more than one block
block2[data_R-1, pos_begin=0, padding=0x04, 0, ..., 0, 0x80] // end of the first operation (and forced permutation)
block3[old_begin=0, flag, data_1, ..., data_R-3, pos_begin=1, padding=0x04, 0, 0x80] // start of the second operation

Example 2: the second operation starts on the same block as the previous operation

block1[old_begin=0, flag, data_1, ..., data_R-2, pos_begin=1, padding= 0x04, 0x80] // the first operation takes more than one block
block2[data_R-1, old_begin=1, flag, data2_1, pos_begin=2 , padding=0x04, 0, ..., 0, 0x80] 

Example 3: three operations in the same block

block1[old_begin=0, flag, data_1, ..., data_R-2, pos_begin=1, padding= 0x04, 0x80] // the first operation takes more than one block
block2[data_R-1, old_begin=1, flag, data2_1, pos_begin=2 , old_begin=2, flag, data3_1, pos_begin=5, padding=0x04, 0, ..., 0, 0x80]
comment on this story

Tamarin Prover May 2017

I was at Eurocrypt's workshop in Paris last week. One of the reason is because I really like workshops. It was good. Good because of the Tamarin workshop, less good because it ended up just being like a normal conference, but still good because it was incredibly close to Real World Crypto.

Tamarin is a "protocol" verification tool. You give it a protocol, a set of security properties it should respect and Tamarin gives you a formal proof (using constraints solving) that the security guarantees are indeed provided OR it gives you a counter example (an attack).

By default, the adversary is a Dolev-Yao adversary that controls the network and can delete, inject, modify and intercept messages on the network

The thing is realllyyyy easy to install.

In the morning, Cas Cremers gave us an intro to Tamarin and taught us how to read inputs and outputs of the tool. In the afternoon, Ralf Sasse told us about more complex concepts while forcing us to write some input for Tamarin.

It was a lot of fun. Way more fun than I expected. I have to admit that I came skeptical, and never really considered formal verification as "practical". But this day changed my mind.

In an afternoon I was capable of creating a pretty simple input to model an opportunistic ephemeral Diffie-Hellman key agreement. The input I wrote is available here. (I have made a better one here and Santiago Zanella made one here as well).

You can see a lot of rules describing the possible transitions of the state machine, and a final lemma which is saying "for any created session (where neither a key or a session key has been leaked) a man-in-the-middle attacker cannot influence the protocol to retrieve the session key". Of course this is ugly, and reading it again a week afterwards I see things I want to rewrite, and probably some "pros" are going to cringe... But it worked out! and Tamarin ended up finding the trivial man-in-the-middle attack.

If you want to play with it, check the online manual which is just great. It provides a few examples that quickly get you started. The hardest part, you must have guessed, is to translate your protocol into this Tamarin input language.

comment on this story

Keeping up with TLS 1.3 May 2017

ekr

Ekr kick started the TLS:DIV workshop last Sunday. "The number of changes since draft 13 is too damn high" read one of the slide. Not wrong I said to myself. I did read draft 18 in its entirety when we had to review Cloudflare's TLS 1.3 implementation, and I tried to keep up with the changes ever since but I can honestly say that I completely failed.

So I thought, why not creating a nice diff that would allow me to go through all these changes just by reading the spec one more time. With the magic of git diff --color-words --word-diff=porcelain -U1000000 and some python I created a nice spec that shows up differences between draft 18 and the latest commit on the github spec.

spec

You can find it here

If you want the same thing for a different draft version say something in the comment section!

comments (2)

A hash function does not provide integrity! April 2017

Some of you might have seen the answer of this famous stack overflow question what are the differences between a digital signature, a mac and a hash?:

hash vs mac vs signatures

The above table is from the most upvoted answer --but it is false. A hash function does not provide integrity, a MAC provides integrity.

Instead a cryptographic hash function provides three properties, well defined in the world of cryptography: collision resistance, pre-image resistance and second pre-image resistance. Nothing else.

comments (2)

SHAKE, cSHAKE and some more bit ordering April 2017

cshake

cSHAKE is something to make your own SHAKE! It's defined in this NIST's doc SP 800-185 along other awesome Keccak structures like KMAC (a message authentication code a la hash(key + data) with no length-extension attacks!) and TuppleHash (a hash function to hash structures without ambiguity (fingerprints!)).

And without surprises, it suffers from the same SHA-3 bit ordering problems I talked about in this blogpost and this one as well.

So I thought it would be a good opportunity for me to talk more about SHAKE, cSHAKE and remind you how the bit ordering works!

What is SHAKE?

SHAKE (Secure Hash Algorithm and KECCAK), defined in FIPS 202, is an Extendable-Output Function (or XOF). It's like SHA-3 but with an infinite output. For whatever length you need. You can use that as a KDF, a PRNG, a stream cipher, etc ...

It's based on The Keccak permutation function, and it works pretty much like SHA-3 does. The two differences are that a different domain separator is used (1111 is appended to the input instead of 01 for SHA-3) and you can continue to squeeze the sponge as much as you like (whereas SHA-3 defines how much you should squeeze).

Of course the squeezing will affect the security of your output, if used as a hash you can expect to have 128-bit security against all attacks (including collision resistance) when using an output of 256-bit. If you truncate that down to 128-bit, you will get rid of the collision resistance property but still have (at least) 128-bit security against pre-image attacks. More information is available in the FIPS 202 document where you will find this table in Appendix A:

sha and shake security

cSHAKE

SHA-3 and SHAKE were great constructions, but Keccak has so much to offer that the NIST had to release another document: SP 800-185 (for "special publication"). It covers some other constructions (as I said previously), but this is still not the extent of what is possible with Keccak. If you're interested, check KangarooTwelve (which is to SHA-3 what Blake2 is to Blake, a less secure but more efficient hash function), the duplex construction (use the sponge continuously!), Ketje and Keyak (two authenticated encryption modes), ...

SP 800-185 defines cSHAKE as a customable version SHAKE. It works the same except that you have one new input to play with: a customization string. If you've used HKDF before you will quickly get its purpose: avoid collisions between different usages of the Shake function. Here are two examples given by the NIST special publication:

  • cSHAKE128(input: public_key, output: 256 bits, "key fingerprint"), where "key fingerprint" is the customization string.
  • cSHAKE128(input: email_contents, output: 256 bits, "email signature")

how it works

As with SHAKE, you can choose an output length, here is how the input and the customization string gets fed to the cSHAKE function:

  1. Use an empty N string (this is for NIST use only)
  2. Choose a customization string S
  3. apply encode_string() on the empty string N and on your customization string S
  4. apply the bytepad function to both with the rate of the permutation in bytes (168 in the case of cSHAKE128).
  5. prepend this to your input
  6. append the bits 00 to your input (domain separator)
KECCAK(bytepad(encode_string(N) || encode_string(S), 168) || input || 00)

What are these functions?

encode_string: left_encode(len(input)) || input.

left_encode: a way to encode a length. It encodes the length of the length, then the length :) all of that in an LSB bit numbering.

bytepad: left_encode(block_size) | input | 0000...0000 with enough 0s for the resulting output to be a byte array multiple of the rate.

The above function can be rewritten:

KECCAK(left_encode(block_size) || left_encode(0) || "" || left_encode(len(S)) || S || 0000...0000 || input || 00)

(This input will then get padded inside of Keccak.)

left_encode

These functions are defined in the special publication NIST document, but they are quite different in the reference implementation).

encode

So here is another explanation on this bit re-ordering trick. Imagine that we have this input to the left_encode function:

0001 0000 | 0011 0001 | 0111 1110

As an hex table it would look like this:

0x10 | 0x31 | 0x7e

Now, the left_encode specification tells us to completely reverse this value, then add a reversed length on the left (here 3). It would look like this:

            0111 1110 | 1000 1100 | 0000 1000
1100 0000 | 0111 1110 | 1000 1100 | 0000 1000

This is quite annoying to code. Fortunately, the reference implementation has a trick: it takes the bytes as-is but re-position them following the little endian ordering convention, then add the padding in a natural MSB first bit numbering:

            0111 1110 | 0011 0001 | 0001 0000  
0000 0011 | 0111 1110 | 0011 0001 | 0001 0000

The Sponge code then re-interprets this in little endian convention:

0001 0000 | 0011 0001 | 0111 1110 | 0000 0011

Which is exactly what was expected, except in reversed order :) which is OK because if you remember correctly from my previous blogpost every operation of the spec is implemented in reversed in the reference implementations.

How to use cSHAKE?

The official Keccak Code Package contains all the keccak functions in C. I've written a Golang version of cShake here that you can put in your golang.org/x/crypto/sha3/ directory, as it hasn't been reviewed by anyone yet I would take this with chopsticks.

comment on this story