Incrementality and deck functions
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 490 | |
| Author | ||
| License | CC Attribution 2.0 Belgium: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/47355 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
FOSDEM 2020450 / 490
4
7
9
10
14
15
16
25
26
29
31
33
34
35
37
40
41
42
43
45
46
47
50
51
52
53
54
58
60
64
65
66
67
70
71
72
74
75
76
77
78
82
83
84
86
89
90
93
94
95
96
98
100
101
105
106
109
110
116
118
123
124
130
135
137
141
142
144
146
151
154
157
159
164
166
167
169
172
174
178
182
184
185
186
187
189
190
191
192
193
194
195
200
202
203
204
205
206
207
208
211
212
214
218
222
225
228
230
232
233
235
236
240
242
244
249
250
251
253
254
258
261
262
266
267
268
271
273
274
275
278
280
281
282
283
284
285
286
288
289
290
291
293
295
296
297
298
301
302
303
305
306
307
310
311
315
317
318
319
328
333
350
353
354
356
359
360
361
370
372
373
374
375
379
380
381
383
385
386
387
388
391
393
394
395
397
398
399
401
409
410
411
414
420
421
422
423
424
425
427
429
430
434
438
439
444
449
450
454
457
458
459
460
461
464
465
466
468
469
470
471
472
480
484
486
487
489
490
00:00
Communications protocolSymmetric matrixCryptographyFunction (mathematics)Value-added networkImplementationInformation securityFunction (mathematics)Presentation of a groupSymmetric-key algorithm
00:42
PermutationHash functionParallel portEncryptionSymmetric matrixAuthenticationDuplex (telecommunications)Limit (category theory)CryptographyFunction (mathematics)Interface (computing)Numbering schemeBitPrimitive (album)String (computer science)Numbering schemeCryptographyEncryptionAsynchronous Transfer ModeBlock (periodic table)AuthenticationPermutationHash functionoutputMultiplication signBuildingInstance (computer science)ImplementationConstructor (object-oriented programming)Interface (computing)Latent heatFunction (mathematics)Key (cryptography)Network topologyOnline chatTerm (mathematics)Descriptive statisticsDuplex (telecommunications)Presentation of a groupComputer animation
03:23
Function (mathematics)Computer fontHill differential equationDuplex (telecommunications)ImplementationCommunications protocolLie groupKey (cryptography)Ratsche <Physik>Data bufferContext awarenessCiphertextSoftware frameworkNoiseCryptographyMechanism designEncryptionAuthenticationNoise (electronics)Function (mathematics)ImplementationCryptographyCommunications protocolDuplex (telecommunications)outputCiphertextMereologyForm (programming)CausalityInstance (computer science)Inheritance (object-oriented programming)CurveDiagramAuthenticationVector potentialCASE <Informatik>Key (cryptography)2 (number)Client (computing)State of matterServer (computing)Computer fileIP addressPublic-key cryptographyBlock (periodic table)Real numberContext awarenessHill differential equationBuildingEncryptionOperator (mathematics)Message passingRatsche <Physik>Different (Kate Ryan album)Multiplication signActive contour modelString (computer science)Hash functionPermutationCodeLine (geometry)Term (mathematics)SequencePulse repetition frequencyEquivalence relationBuffer solutionConstructor (object-oriented programming)Interface (computing)Arithmetic meanObject (grammar)Computer animation
09:49
Hash functionComputer wormNoiseMereologyPoint (geometry)Noise (electronics)Derivation (linguistics)Symmetric matrixPrimitive (album)Function (mathematics)Key (cryptography)EncryptionAuthenticationHash functionProgram flowchart
10:19
NoiseComputer wormSymmetric matrixMereologyNoise (electronics)Constructor (object-oriented programming)State of matterDuplex (telecommunications)System callFunction (mathematics)Multiplication signFigurate numberComplex (psychology)Computer animationXMLProgram flowchart
11:04
Duplex (telecommunications)Computer wormOperator (mathematics)ImplementationFunction (mathematics)System callPermutationString (computer science)XMLProgram flowchart
11:28
Computer data loggingKolmogorov complexityImplementationComputer configurationFigurate numberObject (grammar)Point (geometry)Duplex (telecommunications)Line (geometry)Diagram
12:08
Computer fontFunction (mathematics)outputString (computer science)SequenceRandom numberBitNumberRandomizationFunction (mathematics)outputPositional notationResultantQuicksortPoint (geometry)String (computer science)SequenceView (database)Slide ruleKey (cryptography)Presentation of a groupInfinityComputer animation
13:46
outputFunction (mathematics)Function (mathematics)BitState of matteroutputExtension (kinesiology)ComputabilityLengthString (computer science)Computer animation
15:02
Computer fontFunction (mathematics)Stream cipheroutputCiphertextFunction (mathematics)SequenceStreaming mediaBitEncryptionKey (cryptography)Cartesian coordinate systemResultantNumberCiphertextoutputXMLComputer animation
15:44
outputFunction (mathematics)Function (mathematics)Cartesian coordinate systemAuthenticationMessage passingoutputSequenceContext awarenessBitCASE <Informatik>Computer animation
17:02
Function (mathematics)Message passingMetadataCiphertextAsynchronous Transfer ModeBlockchiffreComputer fontoutputLinear feedback shift registerInformation securityPermutationStreaming mediaEncryptionAdvanced Encryption StandardSymmetric matrixCryptographyCommunications protocolInterface (computing)Operations researchBlock (periodic table)CiphertextEncryptionFunction (mathematics)Multiplication signVector spacePermutationComputing platformAsynchronous Transfer ModeConstructor (object-oriented programming)Computer hardwareImplementationoutputVirtual machineMetadataMessage passingSequenceType theoryThermal expansionLengthDatabase normalizationShape (magazine)Figurate numberParallel portSlide ruleBitRoundness (object)NumberCoprocessorMaxima and minimaQuantumInformation securityState of matterForceInstance (computer science)ArmCommunications protocolKey (cryptography)AuthenticationQuantum computerExtension (kinesiology)Cycle (graph theory)Symmetric matrixCryptographyInterface (computing)Numbering scheme
23:33
Primary biliary cirrhosisPermutationComputer fileConstructor (object-oriented programming)Descriptive statisticsComputer animation
24:05
Function (mathematics)outputConstructor (object-oriented programming)Information securityMechanism designOrder (biology)Point (geometry)Goodness of fitView (database)Condition numberMessage passingEncryptionMultiplication signDenial-of-service attackParallel portCASE <Informatik>Maxima and minimaInstance (computer science)Asynchronous Transfer ModeOperator (mathematics)
25:35
Point cloudFacebookOpen source
Transcript: English(auto-generated)
00:05
Hello everyone, let's welcome our next speaker in security the room is gills and his talk about implement Incrementality and deck functions
00:21
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
00:40
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
01:04
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
01:21
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
01:45
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
02:05
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
02:24
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
02:40
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
03:02
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
03:22
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
03:44
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
04:02
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
04:23
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
04:45
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
05:05
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
05:23
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
05:43
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
06:01
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
06:25
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
06:41
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
07:01
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
07:20
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
07:44
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
08:05
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
08:22
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
08:43
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
09:03
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
09:24
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
09:44
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
10:02
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
10:23
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
10:45
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
11:00
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
11:23
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
11:44
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?
12:00
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?
12:24
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
12:43
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
13:04
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
13:20
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
13:40
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
14:00
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
14:23
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
14:41
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
15:02
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
15:23
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
15:45
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
16:02
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
16:23
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
16:42
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?
17:03
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
17:23
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
17:42
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
18:00
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
18:21
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
18:46
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
19:00
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
19:21
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
19:45
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
20:03
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
20:26
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
20:42
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
21:05
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
21:26
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
21:45
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
22:04
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
22:23
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
22:42
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
23:07
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
23:26
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?
23:59
Okay. Thank you very much for this interesting talk. It was not clear from the your description of the for file construction
24:04
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
24:23
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
24:40
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
25:02
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