Hello everyone, let's welcome our next speaker in security the room is gills and his talk about implement Incrementality and deck functions

Thank you Welcome everyone. Thank you for attending my talk during the lunchtime So indeed in this talk I will talk about symmetric cryptography and I will talk about some some considerations. We've had recently Around the notion of incrementality

So when I say we in this presentation Everything I'm going to say is joint work with the rest of the Kechak team namely Guido Bertone your endowments had offered Miquel Peters and on even care So just a bit of background on what we do So we are interested in permutation based crypto. So permutation based crypto is something

A new kind of crypto in the sense that we instead of having a block cipher we use a keyless permutation The kitchener named Kechak team comes from the designers originally from the designers of Kechak which was selected as chat tree during the chat tree competition

We designed some many stuff based on permutations. So we didn't stop at hashing. We also looked at encryption and authentication We developed some new constructions One instance is key duplex. Another one is farfalle these From from these you can build encryption scheme authentication schemes or authenticate encryption schemes

And we develop of course we design some some specific instances But yeah in this talk this it's not going to be about all these new schemes Instead I would like to to talk about what I call incrementality So incrementality is the notion that if you have some some kind of cryptographic primitives you have some input some output

You can from the input get some output and then you can take your input and you increase you add some more More string to your input and you get another output and you add more string you have another input and so on you you every time get some some output on everything that you have

Constructing your inputs step by step The key thing about incrementality is that every time you do that? You don't have to start all over again. You only pay the price for the additional string that you're adding to your input that's what I mean with incrementality and

We're trying to look around this notion and we think it's an ingredient that can help Simplifying symmetric crypto. So that's what we want to to do something that is simpler in In terms of description in terms of implementation when it comes to authenticate encryption We recently developed something called a deck function

So a deck function is not a new construction on top of all your other constructions that I mentioned It's more an interface something that aims at capturing the notion of incrementality And on top of this this interface we can build modes for authentication encryption and authenticate encryption

Okay, so in this presentation I will talk first about incrementality and For that I will take as an example the disco protocol and then I will talk about deck functions more specifically So why is incrementality useful and in in the sense that it can help us simplify things

So the disco I will explain of course what the disco protocol is but to start I need to go back to the basics And the first let's say incremental construction that we defined was the duplex construction So the duplex if you may know that the ketchak is uses a sponge construction

The duplex construction is just cryptographically equivalent to the sponge construction the only difference is the interface the interface allows us to have Input one input block one input block one input block one input block every time So it uses a permutation the permutation is F here You have some block of input and you can get some block of output

Then you have a second block of input permutation about potential and if you look at maybe this this block of output this block of output is going to depend on all the past input blocks So we have this notion of incrementality, but as such the duplex is not really useful We need to have some layer on top of it to build something concrete and useful in crypto

One thing that We can do is to use the strobe protocol so the strobe protocol was designed by Mike Hamburg and it was presented at real world crypto three years ago and So it's just a layer of duplex but it provides a really nice and simple syntax on that you can use for instance to build secure channels or

to hash the transcript of a protocol and It's simple enough that it allows for a really compact implementation. So in terms of lines of code, it's fairly complex Concretely what can you do with the strobe protocol you can

Have some these are the functions you can have some Associate data that is some data that does not need to be encrypted, but you need to authenticate You can input a secret key. Actually, you would start with inputting the secret key you can get some output PRF and

You can send data in the clear but besides sending the data The data the state of strobe will be affected by by the data So it will authenticate if you when you authenticate it will also authenticate the clear text data Receive clear text is the equivalent from server to client

Send encrypted. I'm going to send some data and but in an encrypted form and My state is going to depend on it Receive is vice-versa. I'm getting some ciphertext and I want to get back to plain text and I want my state to depend on it Send Mac. I need to authenticate myself to server I send a message authentication code depending on everything that that was done so far

Receive Mac I get a Mac from from the server. I need to check that it fits my my key and my context and then finally ratchet is something that Yeah

Ensures forward secrecy, so it raises part of the state in a way that you cannot go back in case the state gets compromised Here is a small example of a protocol on top of strobe So it's a really simple protocol in the sense that we have a client server The client is going to request a file

we want this request to be encrypted so the name of the file is going to be encrypted and We want the server to send back the file in an encrypted form so I start by Putting my secret key here it's either a pre shared key or a key that comes from public key operation like Diffie-Hellman and

Then I have some context X that is going to summarize on what the state depends And I start with an empty X So the next operation is ad so I'm going to add to my context some Associate data in this case the string nonce and the sequence contour I that is going to be incremented every time I use it

Then the string oath data followed by the appeared IP addresses of the client and the server So when I write that X is gets incremented with all these strings It doesn't mean we have a buffer with all these strings It means that these strings are absorbed and the state of the cryptographic object of duplex object underlying strobe

somehow contains a hash of everything that is in X Then I want to send my request get file file is being a fine name I just encrypt this string get file under the key K and That's myself for text that I send to the server and at the same time

I update my context use with this get file string Then I send a message authentication code that depends on the entire context. So from The entire transcript of the protocol so far Then the server sends me back the file in ciphertext. I'm going to decrypt it

And get the plain text. So the fine in the clear I update my context accordingly and then I check the Mac The Mac contains everything and in particular it contains the plain text that I just received So I'm I'm now sure that my file was not tampered with on the way from the server back to me

okay, so In the end, it's fairly nice syntax. We can build many things of this form Then so strobe is only about the symmetric key part. What about the public key? There is another protocol cause the noise protocol former yeah defined by clever parent and presented our hill work crypto two years ago

It's a fairly popular protocol in the sense that it's used for instance in whatsapp and wire guard It does two things first. It enters the public key handshake. So it does typically crypto a VP curve operations to establish a common secret key and then it also handles the

Secret key encryption and authentication aspects In this diagram so you can see what's happening inside noise So I'm focusing on everything. I'm not going to detail this figure. I'm just showing it to Point out that it's fairly

Complicated when it comes to describing what happens in the symmetric part of of noise So you have different primitives you have hash functions key derivation functions Cypher so authenticate encryption and all that gets mixed in a fairly complicated way So the idea was of the idea of disco so disco was presented by David Wong

And black hat three years ago And the idea is just to take noise but replace the symmetric part of noise with something based on strobe and the idea is to make things simpler and if you take the previous figure and now you Look at disco instead of noise itself, then you can see that the symmetric part is much clearer

It's just one call to strobe every time the entire state is maintained by strobe itself There is no need to have different things running in parallel somehow You may say okay, but maybe now the complexity is hidden behind these

Function calls. Well, if you look inside these functions cause it's it really relies on the duplex construction Which as operations only need to Soar some strings into the state and apply the permutation when it's needed So this the kind of operations that lie behind these functions calls are really simple and that makes the

implementation of disco really really nice really simple Here are some figures Provided by David Wong about the size of disco written in C C sharp and go And you can see that disco fits in a few thousand lines if you compare that to open SSL. It's much

smaller I don't think these figures are really fair because open SSL does a lot of more things and have many many options to look at but still I mean my point is that disco can Is really simple and one?

Aspect of it is the use of the duplex object and his incrementality to have to allow for this simplicity Okay okay, so starting from incrementality we decided yeah, let's Let's take a step back and look at how can we define incrementality? How can we maybe refine this notion and try to define things?

On top of a new object and you interface that we call deck function. So what is a deck function? I'm sorry, that's the most technical slide of the presentation That's some notation. But basically a deck function is Up so the random function that takes as input a sequence of strings

So the input is either one string of two strings or three strings and it's a deterministic function So it takes a secret key and the sequence of strings and it's going to produce as many output bits as you wish These output bits depend on secret key They depend on the input if you change just a single bit of your input you get some unrelated outputs

It's deterministic. So if you know the secret key, and of course you have the input you can compute and if you compute it Twice you get the same result It's sort of random in the sense that from the point of view of an adversary who doesn't know the secret key These output bits. They just look like unbiased random bits

They just they cannot and those we cannot predict them for a new a new input string So I said it's it takes It outputs as many bits as you want. Of course You don't need an infinite number of bits and this notation is I'm not going to detail the notation

But it just says that I can take n bits starting from offset Q Okay That's a deck function, but that's not all of it Another requirement of a deck function is to allow for this incrementality Maybe I forgot to mention that deck stands for w-extendable cryptographic key function

So w-extendable is really the feature I'm now describing which is the incrementality I want to have extendable input and extendable output by extendable input. I mean, let's say you first compute FX over some string X and Then later on you want to compute FX over Y after X But you already computed F of X you have maybe kept some state

Then if you do that the computation of FY after X does not cost you Because the cost only depends on the length of Y not another length of X. You don't need to start all over again You don't need to pay for for evaluating F of Y after X if you already evaluated F of Y

So that's incrementality on the input On the in output. It's it's also very simple I mean you can take some some bits of output and if you need more you just pay for these extra bits You don't need to stop all over again Okay, so that's the double the w-extendable feature of the function

Okay, so now assume that we have some some deck function I'm going to of course describe how we can build one concretely, but assume we have one What can we do concretely with the deck function? First application very simple application. I want to just to encrypt some data So I have my deck function. I input the secret key and I input some sequence number

Announce and then the output I use it as a key stream I saw every bit of my plain text with the corresponding bit of the key stream and the result is my ciphertext Decrypt I just do the same. I saw the key stream to the ciphertext and if you saw the same thing twice you They cancel each other and you get back the plain text. So encryption stream encryption very simple

Application to do authentication you input your message to the deck function The output is your authentication tag that you attach to your message Okay Now about incrementality so you can have these this deck function

The output is going to depend on everything that was received so far So if you maintain a deck function and you encrypt different messages that follow each other Then you can have something which we call a session and by session I mean that if you exchange some messages and it's a US in three messages the tag on the third message it the

Third message to the authentication of the third message. It's not just locally authenticating this third message But really a sequence of all the messages received so far. So maybe this last message is just a confirmation It's just a bit Okay with the tag you don't want the adversary to be able to reuse this okay in different contexts

Otherwise you can the adversary could send an okay on something you don't want maybe But in this case because the tag depends on all the past is okay is clearly a refer referring to the context Which is the sequence of previous messages? I think it's really convenient and comes naturally with the notion of incrementality that Is buried in deck functions?

Okay Yeah, I'm going to go quickly over this Slide so we defined a mode called dexane which does this session based encryption? using a nonce and It's really simple. So you initialize it with some some nonce and you can get a tag over the initialization

Let's say you have a first message composed of metadata something you want to authenticate but not encrypt and the plain text You use the deck function to produce some some p-stream you encrypt it as you've done two or three slides before and the tag includes

Everything including the metadata and ciphertext Now because we already processed the nonce this nonce is now great on my slide means we don't need to pay for it We just pay for this side to the metadata and ciphertext and if I if I have a second

Message then I need to pay the price only for this second message Okay All right, so dexane needs a nonce It means that you need to have a sequence number in that maybe it's a packet number But if you repeat that value then then you get into trouble So there are all the deck based modes that we we define one is called

Sensei and the idea is to replace this sequence number by some things tech Synthetic sequence number based only on the plain text. So we don't need to really maintain this the sequence number and The other one is deck WBC wide block cipher. The idea is to achieve authenticate encryption with minimal expansion So if you have plain text that already contains some redundancy, you can just read base yourself on this redundancy to ensure

authenticity and maybe you want to encrypt something into something else without any expansion because of course in Dexane the extent that sensei you have this extra tag that increases the size of your cycle So you have ciphertext and the type that you need to transmit

So we have some expansion with the WBC you can manage if you have enough redundancy You can just have your ciphertext whose length is equal to the plain text full stop So that's really a nice feature Yeah Then a few minutes about how we can build an efficient deck function

So recently we developed a new construction called Farfallee The name Farfallee comes from yeah, maybe it's shape So again, I'm not going to detail everything that's happening inside So it takes a secret key and some input blocks But the key thing to look at on this figure is that the permutation F that is being evaluated in this construction

They get all evaluated they can be evaluated at the same time because they are they can run in So you can parallelize your implementation and maybe you can plug in a vector implementation of this permutation You can compute two permutations at once for eight depending on the size of your vector

assigned the instruction vector instructions So they can really speed up things and the same goes for the output all these F's all these permutations can be computed at the same time So basically we define two instances of ciphers based on Farfallee The first one is called Kravate and Kravate uses a Keshak permutation reduced to six rounds. So that's one F

We claim that it has a security of 128 bits and we claim that it also includes Adversaries we would have access to a quantum computer So Kravate is fairly fast. The only disadvantage is a big block size of 200 bytes

So we define another permutation that was done recently called Zudu that's a 384 bit permutation so 48 bytes and We define Zuf which is Farfallee using Zudu with six rounds there again We claim a security of at least 128 bits This post quantum claim was reduced a little bit because the permutation is smaller

And that's just a consequence of this of this size So Performance figures so that's Kravate on a skylake processor. So skylake processor is a fairly common processor nowadays it has a vx2 instructions vx2 are

256-bit SIMD instructions and using that we can implement Kravate With a speed that is slightly so it's slightly faster than AES encounter mode on that platform Bear in mind that on this platform. There is the AES and I instruction. So basically the AES

implementation Is a hardware implementation? Whereas Kravate uses just the regular the general purpose vector instructions on that machine okay, so Last thing is about Zuf so Zuf as in name suggests is supposed to be fast

But the key message for Zuf is that because we use a smaller permutation this permutation The state can fit in 12 registers of 32 bits so that can fit in a typical arm cortex processor it can also run fast on small processors and because of the

Parallelism it can also run fast on high-end processors So concretely on the cortex and zero processor. That's a fairly small one it's about four to five times faster than the EDS and About the same figures for I mean the same ratio for cortex and three

On skylake, it's slightly slower than the EIS encounter mode But if you have access to the new AVX 512 instructions Then it again becomes faster than the EIS encounter mode again using general purpose instructions So that's all I wanted to say just to conclude in this talk. I tried to To explain to you why we think incrementality in symmetric crypto can make protocols simpler

We've seen that with an example, which is disco We also think that it can make some modes more natural the notion of sessions really directly benefits from from this incrementality And then to capture this incrementality We define the deck function interface and we show that we could make some efficient

schemes based on that Specifically using the fact for the construction and That's it. Thank you for your attention. We've got time for one or two short questions. So is there any other questions?

Okay. Thank you very much for this interesting talk. It was not clear from the your description of the for file construction

You can paralyze The encryption and decryption operations But can you receive messages out of order and validate the max that correspond to it? Because that would be an inch very important use case for things like where God for instance Okay, so if you have out of order messages good

So basically the notion of session doesn't simply doesn't work so you cannot really exploit it the parallelism I was mentioning it was not about this Session mechanism it's independent. It's just that this construction allows you to implement

So the longer the input the more parallelism you can exploit independently of session mechanism if it's out of order or anything Nothing is from the security point of view. We would like to validate makes max as fast as possible to avoid denial-of-service conditions Having two larger messages is not this of course

And that's why in in this mode We have a tag at session started so you have a tag that you can immediately check just based on the nuns So denial of service attacks, I mean they need to have this tag, correct? Otherwise, you can just stop there and you don't need to Thank you, we are out of the time so thank you for your questions and for your talk. Thank you