Keccak, More Than Just SHA3SUM
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 | 90 | |
| 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/40301 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
FOSDEM 201340 / 90
2
5
8
10
12
13
14
15
17
19
21
24
25
28
29
31
32
34
36
39
40
43
44
46
50
51
52
54
55
57
58
62
65
66
67
78
79
87
88
00:00
Discrete element methodHash functionFunction (mathematics)Open sourceWater vaporWebsiteBitHash functionMessage passingMultiplication signLengthQuicksortTrailDigitizingElectronic signatureoutputMiniDiscRevision controlView (database)Level (video gaming)Slide ruleGreatest elementComputer fontWordLecture/Conference
03:02
CryptographyMiniDiscCryptographyComputerCollisionArithmetic meanControl flowMultiplication signEncryptionHomomorphismusBlock (periodic table)BitSystem callHash functionProcess (computing)Letterpress printingNumberElectronic mailing listDigital photographyMetropolitan area networkComputer animationLecture/Conference
05:51
BitHash functionQuicksortSystem callFunctional (mathematics)Sheaf (mathematics)Lecture/Conference
06:28
Broadcast programmingSheaf (mathematics)Electronic mailing listProcess (computing)Functional (mathematics)Message passingLengthDifferent (Kate Ryan album)TrailHash functionLecture/Conference
07:10
Function (mathematics)outputRegular graphHash functionParameter (computer programming)Variable (mathematics)Bit rateClique-widthCategory of beingBitHash functionProcess (computing)State of matterParameter (computer programming)Information securityLevel (video gaming)Channel capacityBit rateFunctional (mathematics)Constructor (object-oriented programming)PermutationXMLUMLLecture/Conference
07:50
Function (mathematics)Regular graphHash functionParameter (computer programming)Variable (mathematics)outputBit rateChannel capacityBlock (periodic table)PermutationClique-widthBitPermutationPhysical systemWaveCartesian coordinate systemAlgebraState of matterCoefficient of determinationComputerData structureXMLUMLLecture/Conference
08:56
Function (mathematics)Block (periodic table)PermutationBit rateChannel capacityBlock (periodic table)Flow separationBitEncryptionKey (cryptography)ComputerPermutationProcess (computing)Channel capacityBit rateInformation securityClique-widthForcing (mathematics)Different (Kate Ryan album)Axiom of choiceLevel (video gaming)Cartesian coordinate systemOperator (mathematics)Condition numberMathematicsTunisHash functionXMLLecture/Conference
10:28
PermutationBit rateInformation securityAdvanced Encryption StandardStandard deviationRegular graphMessage passingSample (statistics)SimulationBlock (periodic table)Function (mathematics)Electronic mailing listCartesian coordinate systemBitTransport Layer SecurityHash functionCryptographySymmetric matrixZustandsgrößeOperator (mathematics)Functional (mathematics)Sound effectFreewareCombinational logicEncryptionSlide ruleMessage passingAuthenticationKey (cryptography)XMLLecture/Conference
11:20
Message passingBlock (periodic table)Standard deviationFunction (mathematics)Block (periodic table)Asynchronous Transfer ModeEncryptionChannel capacityBit rateInformation securitySign (mathematics)PermutationInstance (computer science)CryptographyConfidence intervalLecture/ConferenceXML
12:08
Block (periodic table)AdditionLengthDifferent (Kate Ryan album)Group actionCartesian coordinate systemStandard deviationInstance (computer science)Computer fileBuildingBasis <Mathematik>Function (mathematics)BitInformation securitySet (mathematics)Hash functionCombinational logicLecture/Conference
13:19
Message passingPublic-key cryptographyMultiplication signMessage passingOperator (mathematics)Hash functionComputerElliptic curveSign (mathematics)Electronic signatureCurveConnected spacePasswordCategory of beingIdentifiabilityoutputData integrityRevision controlSound effectCartesian coordinate systemData storage devicePhysical systemInformation privacyPublic key certificateDigital rights managementFunctional (mathematics)Standard deviationPoint (geometry)CollisionElectric generatorFunction (mathematics)Antivirus softwareType theoryPeer-to-peerLecture/Conference
15:21
PasswordoutputHash functionFunction (mathematics)Computer fileMatching (graph theory)Data storage devicePasswordWordTable (information)Instance (computer science)Right angleXMLUMLLecture/Conference
16:54
Hash functionPasswordData storage deviceIdeal (ethics)Series (mathematics)Message passingHash functionFunctional (mathematics)CASE <Informatik>Cartesian coordinate systemPublic key certificateKey (cryptography)Constructor (object-oriented programming)Instance (computer science)BitPhysical systemDerivation (linguistics)Electronic signatureLoginPublic-key cryptographyMultiplication signElectric generatorComputerAuditory maskingGenerating functionZustandsgrößeXMLUMLLecture/Conference
18:54
CodeMessage passingAuthenticationEncryptionHash functionKey (cryptography)Block (periodic table)Message passingElectronic signatureCodeCodePhysical systemMacro (computer science)XMLUML
19:33
Vulnerability (computing)National Institute of Standards and TechnologyElectric generatorLecture/Conference
20:10
Streaming mediaComputerEncryptionKey (cryptography)Cartesian coordinate systemBitStreaming mediaINTEGRALAuthenticationMessage passingConstructor (object-oriented programming)Slide ruleMultiplication signInstant MessagingCASE <Informatik>Cellular automatonCommunications protocolFunction (mathematics)UMLProgram flowchart
21:36
Single-precision floating-point formatAsynchronous Transfer ModeRandom numberMessage passingStreaming mediaPhase transitionDuplex (telecommunications)Streaming mediaMultiplication signConstructor (object-oriented programming)Personal digital assistantRandomizationoutputView (database)Point (geometry)Random number generationEquivalence relationChannel capacityInformation securityCartesian coordinate systemFunctional (mathematics)ComputerData recoveryDeterminismWebsiteInstance (computer science)ZustandsgrößeUMLLecture/Conference
22:28
Information securityPower (physics)CollisionInformation securityoutputChannel capacityFunction (mathematics)PasswordParameter (computer programming)LengthStandard deviationEncryptionKey (cryptography)Level (video gaming)Instance (computer science)BitBlock codeHash functionCASE <Informatik>Block (periodic table)XMLLecture/ConferenceMeeting/Interview
24:04
Information securityCycle (graph theory)Power (physics)System callBitChannel capacityBit rateNumberOperator (mathematics)Core dumpMessage passingInformation securityPermutationLogic gatePunched cardSound effectInstance (computer science)XML
25:19
Level (video gaming)Slide rulePower (physics)Information securityFunctional (mathematics)Complex (psychology)Operator (mathematics)Lecture/ConferenceMeeting/Interview
26:03
Information securityPerformance appraisalPower (physics)PermutationComputerDivisorUniverse (mathematics)Information securityLevel (video gaming)Multiplication signBuildingXML
26:51
Power (physics)ComputerMaxima and minimaFood energyTotal S.A.Function (mathematics)Universe (mathematics)SupercomputerBitSpecial unitary groupInterior (topology)Information securityRoundness (object)WebsitePunched cardPermutationFunctional (mathematics)Computer-assisted translationDescriptive statisticsLecture/ConferenceXML
27:55
RippingSoftwareHill differential equationMiniDiscComputing platformTerm (mathematics)WordPermutationBitSoftwareMultiplication signDescriptive statisticsMereologyNonlinear systemCASE <Informatik>Set (mathematics)State of matterFunctional (mathematics)Polar coordinate systemRoundness (object)RotationOpen sourceKey (cryptography)RoundingOperator (mathematics)Point (geometry)Linear mapArray data structureUniform resource locatorSoftware testingLogical constantException handlingRow (database)Computer animation
30:16
BefehlsprozessorShared memoryNumberVirtual machineMultiplication signInstance (computer science)TrailComputer-assisted translationAsynchronous Transfer ModeParallel portCASE <Informatik>Network topologyLecture/Conference
31:11
MiniDiscComputing platformSoftwareComputer hardwareField programmable gate arraySicTerm (mathematics)ImplementationComputer hardwareComputerCoprocessorBefehlsprozessorRotationBitStress (mechanics)Network topologyForcing (mathematics)Computer animationLecture/Conference
32:05
ArchitectureBefehlsprozessorImplementationRotationBitWordBefehlsprozessorPosition operatorTerm (mathematics)Operator (mathematics)Key (cryptography)AdditionComputing platform32-bitXMLLecture/Conference
33:44
BefehlsprozessorWordInformation securityFunctional (mathematics)Level (video gaming)Computing platform32-bitSound effectXMLLecture/Conference
34:32
Open setCodeOpen sourceMathematical analysisCryptographyPerspective (visual)AlgorithmNational Institute of Standards and TechnologyWordCryptanalysisOpen setInstance (computer science)BenchmarkImplementationCategory of beingCoroutineInformation securityDifferential (mechanical device)Linear cryptanalysisOpen sourceTerm (mathematics)Point (geometry)XMLLecture/Conference
35:54
Open setCodeOpen sourceBenchmarkCryptographyCryptanalysisPoint (geometry)Computer-assisted translationCategory of beingDifferential (mechanical device)ComputerCodeCryptanalysisTerm (mathematics)Axiom of choiceXML
36:40
CryptanalysisTerm (mathematics)Point (geometry)ResultantWordAxiom of choiceMathematical analysisFitness functionCryptanalysisLecture/ConferenceXML
37:20
CryptographyOcean currentRevision controlCryptanalysisMedical imagingTerm (mathematics)Roundness (object)ProteinCollisionImplementationInstance (computer science)XMLComputer animationLecture/Conference
38:07
Graphics processing unitSoftware developerComputing platformArmReduction of orderRead-only memoryMathematical optimizationCodeImplementationComputer iconImplementationComputing platformInstance (computer science)Different (Kate Ryan album)CoprocessorSet (mathematics)Befehlsprozessor32-bitCodeInterior (topology)WebsiteBitArmBeat (acoustics)Lecture/Conference
39:35
Mathematical optimizationVirtual machineDynamical systemImplementationFluid staticsLibrary (computing)Formal languageCodeCartesian coordinate systemConsistencyCryptographySoftware developerRight angleMultiplication signLecture/Conference
40:35
Interface (computing)Electric currentFormal languageImplementationAsynchronous Transfer ModeLevel (video gaming)Bit rateInterface (computing)Proof theorySubsetDuplex (telecommunications)AbstractionImplementationDifferent (Kate Ryan album)Mathematical optimizationOvalStandard deviationNational Institute of Standards and Technology
41:47
Library (computing)Information securitySlide ruleDerivation (linguistics)Multiplication signPrimitive (album)Numbering schemeTwitterInstance (computer science)Mathematical analysisMarginal distributionNumberQuicksortCryptographySemiconductor memoryAlgorithmImplementationScripting languageRight angleINTEGRALMathematicsQuantumOcean currentComputer-assisted translationQuantum computerSoftware developerOpen setAsynchronous Transfer ModeRootCryptanalysisFactory (trading post)Square numberParameter (computer programming)Cartesian coordinate systemSet (mathematics)Roundness (object)Capability Maturity ModelMessage passingFood energyStandard deviationOnline helpPoint (geometry)Lecture/Conference
Transcript: English(auto-generated)
00:00
Good luck. Thanks. So first of all, thanks to the, we would like to thank the FOSM team to invite it for the talk. And to give a bit of a word on Kitchak. So, I have a problem with the,
00:23
so that's a work that we did since the five last year with Johan, Guido, Gilles, and myself. So Guido is not here because he's Italian. He just got a baby, so. This talk will be about Kitchak, so more than just chat we should sum, so Kitchak is hash functions.
00:43
So what is it about? Oh, sorry. It's my mouse which is jumping around. Okay. Ah, come on. I'm going to drop this.
01:00
Sorry. So the outline was a bit of story to explain what is it, or we come there. Then some high level of view on Kitchak. Then Johan will go more deeply into the, or you can use Kitchak for your own purpose, or you, the open source community could use it.
01:21
Then Gilles will go to the inside of Kitchak explaining what's really, or you can implement it, and then what Kitchak has an impact on the community, what the community can do for Kitchak. So first, what is a hash function? So probably you've already heard of hash of some sort. So probably the one on the left you know already.
01:41
Huh? I guess there's not too much of that to make the slide. I don't know. If you like to burn things, maybe you know the one at the bottom. If you are a French speaker, you will know, also know the disk hash, or that one on the top. That's a X in English. But that's not a hash function.
02:02
What we're speaking about actually is this. So if you have an input message, you have a hash function, so you can then transform this input message into some digest, which is a fixed length value, like typically 128 bits.
02:21
And this is used widely. For some of the most known today, hash functions are called MD5, so probably you know MD5 sum, SHA-1, SHA-1 sum, and so on. So that's quite technical, so the question is, why should you care about that?
02:40
And the main thing is that actually, you probably use them several times a day, even without knowing it. So if you go to the website and you authenticate, if you do digital signature, home banking, if you are using Git to do version control, and so on, you use hash functions.
03:02
And recently, there have been some breaking news in crypto and breaking news really is bad for crypto. And indeed, in 2005 and even starting before, we had bad news about MD5, which has been broken and then broken particularly, meaning that we can really produce collisions
03:20
with maybe an expensive computer. And we have the same with SHA-1, where today we only have a theoretical break, so it's not really particularly broken, but we might think that in the future, it will be broken particularly. And the problem is that SHA-2, so the next variant of SHA-1, is very similar to SHA-1 and to MD5,
03:42
and so this, which is the American standardization body, they were afraid that maybe a break would come for SHA-2 as well. So in 2007, they said, okay, let's make a same competition as we had for AES, so the block cipher, and they make a call to say to the community saying, okay, please design for us a new hash function.
04:02
So the question is, who answered the call? Well, we did. So that's the kick chat team, huh? So we have Johan, Gilles, Guido, and myself, and I would like to spend a bit of time with this picture because this picture explains why we won, actually, the competition.
04:20
The first thing, and probably you see that, the Soviets, we are very cute. I guess that's a very good reason why we have been selected. Second reason that we have here, Johan, who already won the previous competition. So of course, that's a good reason to be selected, and also I think the future probably needs
04:41
won't do any competition. They will ask immediately to Johan, Guido, and me. Then next, we have Guido, me, and Italian. And why is it important? That's because Italians, long time before, they invented the Roman numbers, and Roman numbers, actually, crypto, that's important because it's like homomorphic encryption,
05:02
and homomorphic encryption is the process where we tell you how to do the computation, but in the end, you don't know what you have. So, Roman numbers, personally, I don't understand. I cannot read them. And the last reason also is that, actually, to make this picture, we use GIMP. I guess you know GIMP,
05:22
so that's the competitor of Photoshop. And the Photoshop guys, they said that GIMP is very difficult to use. So if it's so difficult, and we manage to make such a nice picture, it means that you are really smart, isn't it?
05:41
The phone is lost? Okay, sorry. Yeah, yeah. Maybe this is better? Okay, of course, we were not the only one to answer this call, and there were many of them, actually, 64. So this is a bit the picture. So there were many known names,
06:01
like Ron Hrivast, which is the designer of MD5. We also saw people from Bushnell, they designed the sky, the hash function. So there were many of them. IBM also participated, they designed Foo. So actually, in the end, we were 64.
06:21
And the design is like this. So the first competition started in 2007, the first conference in 2009. So there was actually a section process. And after three conferences, the list selected then first 14, second one candidate, then finally, third one candidate,
06:42
and then recently, they selected in October 2012, they selected Kechak. Okay, so what is it really, then, this Kechak thing? Kechak, actually, is more than just a hash function.
07:01
It's what we call a sponge function. And the main difference is that you can take any message from any length and produce another message of any length. And there are some technical properties that we just mentioned here. But mainly, the main thing is that it's much more flexible than hash functions.
07:21
And you have two parameters. So you can see here, actually, in the process, you see that we have initial state. And then you have some bit going through, and you can select the width of this data path. And there are two names for the rate, which basically defines the speed of the function, and then the capacity, which defines the level
07:42
of security you can achieve with the function. And the F, that's actually a permutation that we call Kechak F. So what is it? Actually, we have, in Kechak, we have seven permutations.
08:00
And these permutations, they have different widths, so we start from a small toy variant, which is only 25 bit wide, up to 1,600 bit wide. So basically, the smaller one is more for toy to play with, to analyze it, where the biggest one is free to get the most speed from the small structure.
08:24
And you can use middle one, for instance, for lightweight application, for instance, for embedded system, and so on. So basically, these permutations, they apply to some three-dimensional state that you can see more or less on the left. And the thing is that you have more or less
08:41
25, what we call, layers, and each of these layers is 64 bit wide for the biggest variant. For the smallest variant, we have one bit layer, then two bit layer, four bit layer, and so on. So typically, if you have a 64 bit computer, you would use a 64 bit world of the computer to map on the lane.
09:03
So basically, that's a bit like a block cipher, but you don't have a key. And how do you use that? First, you have to choose one of the seven permutations. For instance, you pick the biggest one, the 1,600, and then you have to choose the value of the rate and the capacity.
09:20
Of course, the requirements is that the rate plus the capacity needs to be equal to 1,600, so the width of the permutation. And depending on your choice, here you see you have a different trade-off of speed and security. For instance, if you have chosen a capacity of 256, that gives you more or less a security of,
09:40
what we call, 128, so you require, in some condition, up to the 128 operations to break the hash function. And this is the speed that you get compared to what we call the reference, which is this one. But if you are not happy with that level of security,
10:00
you can choose a biggest rate, for instance, this one, and then you get a better security, but you lose a bit of the speed. And this is different from Chateau, for instance, because Chateau, they always give you a fixed width, and you cannot change it. You cannot tune it really easily to your applications. For here, the trade-off, you can make it very easily.
10:25
So if you are, for instance, you have less requirements and security, you can reduce the capacity and have a bit of both speeds. So now Johan is going to tell you how you can use this list for your application.
10:42
Can you hear me? Okay, so. So, it was, so Kcheck was in the SHAD3 contest as a hash function, but it's in fact more than hashing, as Mika already said, it's a point function. And in fact, with this function,
11:02
you can do all symmetric crypto operations that you need. So it's hashing, but also key derivation, message authentication, encryption, the combination of message authentication and encryption in one primitive also. So I will show that on the next slides. And all these things can also be done,
11:21
of course, by a block cipher. But then a block cipher becomes reasonably complex to define all these modes. For instance, authenticated encryption modes are not trivial to specify while for this Kcheck, for the permutation, it's more simple and straightforward. And it allows you to also give you more flexibility
11:42
because you can choose the rate and the capacity. It's also easy to understand the security claim. So in general, in cryptography, it is, you cannot prove that something is secure. What you can do is you can claim that something is secure and then wait for people to attack. And if there are no attacks and it takes years,
12:01
then people can gain confidence in the cryptography. But for that, you need to specify a clear security claim. So you can say, okay, you will do everything with one primitive, that's a kind of monoculture. So that's reasonably dangerous because if this single thing is then broken, then everything is broken. But in fact, it's quite the opposite.
12:22
If you look at the big picture, if you look at, for instance, the existing standards, SHA-1 and SHA-2, they are built using completely different building blocks than Kcheck. They are based on things like addition and the combination of addition and exhaust while Kcheck does not use addition.
12:40
Another set of standards is based on the block size AES and that's still another thing. So if you look at this big picture of standards, this will enrich the existing standards and introduce, in fact, a new basis for security. Okay, so the first application, of course, is hashing because it was submission to the hash contest.
13:03
And what you then do is you just truncate the output to some length. So if you want a 160-bit hash like SHA-1, you just truncate to 160 bits. If you want something of length, 256 bits, yeah, you just truncate to 256 bits. So Mikkel already gave some examples
13:22
of where hash functions are used. So here are some more examples. So for instance, in electronic signatures, they are used. So if you do an electronic signature, you do a public key operation like RSA or elliptic curve on a message. But if you would have to do that on a very long message, like, say, a document of one megabyte,
13:43
that would take a long time. So for that reason, this message is compressed to a hash and it's, in fact, the hash that is signed. So some standards, X.509, that's the standard for certificates. There is the GPG, so what is it? Canoe, pre, canoe.
14:01
Privacy, yeah. PGP, yeah, the more commercial version. And in these applications, it's important that it's difficult to generate two different inputs with the same output, so with the same digest. So we call that the property of a hash function collision resistance. Then also for data integrity, yeah, so SHA-some,
14:23
as Mikkel already said, so SHA-3-some or SHA-2-some or whatever, MD5-some. And then in many systems, hash functions are used to generate identifiers, like in version control systems like Git or Material. Also online antivirus programs use it, peer-to-peer systems all use hashes as identifiers.
14:44
So also there, it's important that each identifier is unique per input. Now, of course, because the output is shorter than the input, there will be collisions, but it's very hard to generate collisions, so that's the point of hash functions. It's hard to generate collisions.
15:01
Another application of hash functions is the storage of passwords. So if you have your system where you log on, you type in a password, so the password must be somewhere present on the system to verify whether your password that you typed in is correct, and they don't store the password in the clear, they store it, in fact, as a hashed version of the passwords.
15:23
In this application, it's important that a hash function is one way, or we call it pre-image resistant. That's more the official term, but you can see it as one way. So it should be hard to, given the output, compute the input. So if you have a hash of a password, it should be hard to generate the input.
15:41
So even if you get hold of this file with the password, the hashed password, it should be hard to get the password from it. But of course, what you can do, if you have a file with hashed passwords, you can just try a different password and see if the hash matches. You can always do this attack. So if you have a file with one password,
16:02
then you have to try passwords until you get the right one. If you have a file of a million passwords, then you just try, and it's very likely that you will have some good hits. If you try the word password, for instance, it could be that in a million people, there will always be some people stupid enough to choose the password, password. So for that reason, they add salt to the input.
16:23
So they don't store the hash of the password alone. They also store a salt, which is a random value. And in that way, that makes such attacks more difficult because the salt will be different from one password to the other. There are other methods to attack this, so-called rainbow tables, and the salt also helps against that.
16:42
Okay, so another method is to protect against these exhaustive password searches is to make the hash function very slow. And you can make, I didn't even explain how you add the salt. So in fact, a salted hash function, to build it with k-check is very easy.
17:01
You just prepend the salt to the message. So another method is to make the function very slow. In that case, you just append to the message a long series of zeros. This makes the function very slow, which is, in fact, a bad thing for the attacker because he has to do a lot of these hash function computations. For a normal user, well, if he logs in,
17:22
the login will take maybe 100 milliseconds more time. So it will just be a little bit slower, but it's, many systems slow anyway, so you will not notice. So a hash function generates, from a long message, a short imprint.
17:40
But in many applications, this is not enough. So if you have, for instance, SHA-1, you generate 160 bits, but in many systems, you need more than that. So what is typically done in all these systems is that you compute the hash, and then you expand the hash again with a dedicated construction called mask generating function.
18:02
With k-check, those point functions in general, you don't have to expand it. You just apply the function as it is, and it comes all by itself. So this is, for instance, used in SSL and TLS for key derivation. So in the beginning of, when you do an SSL session, in the beginning, there is a key setup, and during the key setup, there is a session key generated,
18:20
and in that generation of the session keys, you use a key derivation function, so this mask generating function. It's also used in public key cryptography for electronic signatures, encryption, key establishment, which is defined in a lot of standards, and it's applied all the time. So for instance, in your SSL sessions, you also have an exchange of certificates,
18:41
and in these certificates, these are based on these kind of standards. Okay, so if you want to send a message to another party, and you want to authenticate the message so that the other party knows that the message comes from you and has not been modified in between, you can generate a MAC, a message authentication code, and a message authentication code is like
19:02
a kind of signature computed over a message and a key. So if you want to use Ketchak for that purpose, you just have to concatenate the key and the valid message in the input, and what comes out is the MAC. There are systems, most MACs nowadays
19:21
are computed with block ciphers or hash functions. For block ciphers, you really have to take care in defining this MAC mode, otherwise it's not secure. For hash functions, there is an established way to do it. It's called HMAC, it's a NIST standard, and basically, you have to do some complicated stuff at the end.
19:42
The Ketchak is no longer needed, so why do you have to do this complicated stuff at the end? Well, there is in fact a weakness in SHA-1 and SHA-2, which is well known, which has been well known for, I think, 15 years, and this HMAC is there to plug this security hole in SHA-1 and SHA-2. So in Ketchak, this security hole has been removed.
20:01
In fact, in all SHA-3 finalists, there was no, the security hole was removed. So this makes MAC generation more simple. So you can generate a long output, as I said, so you can also use Ketchak for stream encryption. So basically, what you do is you feed, instead of a key, you feed a key and a nonce,
20:23
a value that should be unique, and out comes a long stream of bits, and you can add this stream of bits bitwise to your message, and that does the encryption. So I've shown you on the previous slide how to compute a MAC, how to do encryption, and in many cases, people want both.
20:42
They want encryption and MAC, so they want to protect the confidentiality of a message, but also the integrity of the message. You can, of course, do these two things independently, but then the cost is doubled, it doubles the cost. So you have to do, in fact, two computations of Ketchak of this thing. So in fact, we took a close look,
21:01
and we found out that you can do this and still be secure. So you can, at the same time, generate a key stream and generate a MAC with just one execution of Ketchak. These are things that are used in also SSL and TLS, SSH, Ipsak, so in many cases,
21:20
in many protocols, this is what you need, encryption and authentication at the same time. Now, this is not a straightforward application of the sponge construction. In fact, according to the sponge construction, you cannot do this because we absorb data, so the padded message is absorbed, and the key stream is squeezed at the same time, and normally, there's first an absorb phase
21:41
and then a squeeze phase. But we defined a kind of assistive construction to the sponge called duplex, which can be shown from security point of view equivalent to the sponge. We can also use this, for instance, for random generator, the deterministic random generator that allows receding, so that allows to input new randomness
22:02
while it is running. Okay, so now the security claim. What is the secure, Mikkel already said, said the security of a getchug or a sponge function in general is defined by its capacity. We have made an application,
22:21
a colleague of us has made an application that is available on our site, so you get the URL there, where you can, in fact, give your security requirements with respect to two criteria and see what then the requirement is on the capacity. So we first have the required collision resistance,
22:42
so the problem to generate two inputs that give the same output is expressed as two to the power x, where this two to the power x stands for two to the power x calls to getchug. If you want that security level two to the power x, then you fill in there this value x in the top,
23:00
in the top case. There's a second criterion which we allow you to fill in is the pre-image resistance. So the effort to generate, given an output, to generate a matching input. So for instance, if you have the hash of a password, define the password. So you can fill something in. So for instance, here we fill in 128.
23:21
So what is so special about 128? 128, that's nowadays considered to be the standard security level of encryption. So the AES, the shortest block length, the shortest key length of AES is 128 bit. So let's say we want a collision resistance of two to the power 128
23:42
and also the pre-image resistance of two to the power 128. Then this allows you to choose a parameter, the parameters that are shown below, so you get a capacity of 256 bits is sufficient.
24:01
So you see it's the double of 128. So for speed, this gives you on Intel Core Duo, 9.6 cycles per byte. So if you fill in another required resistance, so if you say, okay, we want for pre-image resistance,
24:20
we want 256 bit of security. So we want to find a pre-image to cost about two to the power 256 calls to KJAC. Then in fact, the capacity becomes 512. So with the capacity growing, the rate becomes less and the amount, so the rate is a number of bits that you can process per call
24:40
to the KJAC at permutation. So the speed goes down. So now a message, hashing a message, applying KJAC to a message costs 12 cycles per byte. So it's slightly less fast. Okay, so in fact, we have defined a security claim
25:01
called a flat-punch claim for a given capacity. So if the capacity is, for instance, 256, then we claim that the KJAC resists any attack up to two to the power 128 operations. So in fact, for a given capacity is two to the power C
25:20
divided by two operations. Below that complexity, an attack should have a negligible success probability. Unless, unless you can also do it in general, so for any function. So let's say you would have KJAC truncated to one byte. Well, finding a pre-image of one byte,
25:41
you just try enough values until you hit the right byte. And there are only 256 different bytes, so you cannot have a better security level than one over 256. So two to the power 128, what does that represent? So we put something on the slide to give you an idea.
26:02
If you have one billion computers, and these computers can each perform one billion evaluations of KJAC-F, so that's the permutation in KJAC, it would take you 10 to the power of 13 years to evaluate this permutation, two to the power 128 times.
26:22
So that's about 700 times the age of the universe. It was until recently claimed security level of two to the power of 256 was considered quite normal. Well, let's see what it gives
26:40
when you have that kind of claim. Then, in fact, this one billion computers, that will take, well, a factor of 10 to the power of 41 times the estimated age of the universe, but you can say, okay, we can build more efficient computers, so let's assume we can build the ideal computer, an irreversible computer. It takes a minimum amount of energy to compute one bit.
27:03
Then, in fact, to compute from one to two to the power of 256, we take the total energy output of the sun during 10 to the power of 20 years. So, yeah, it's a bit ridiculous security claim. So now Gilles will continue about the inner workings of KJAC.
27:25
Okay, so far we spoke a lot about sponge functions, how to use it, and if you take a look at the pictures of sponge functions, there is this f function, the permutation, and the bulk of the work of KJAC is really done inside this f function,
27:42
so I'm going to, say, dive into KJAC-S. So if you take a look at our website, we have this description of KJAC-F in pseudocode. So KJAC-F is just the repetition of 24 rounds for the case of the largest permutation. So 24 times the same kind of operation is performed.
28:04
That's the top part here. And, oops, I didn't click on anything. So 24 times the same kind of operation, except that there is a round constant, so something that changes from round to round. On the bottom part of the pseudocode,
28:22
you have the description of what's inside the round function. And we like to put Greek names on the operations we do. So first, the theta step. It's really a linear mapping. I should first say that, okay, the A, B, C, and Ds are arrays of, say, for instance, 64-bit values.
28:44
So Mikhail was speaking about a 3D state. So here we have two coordinates, X and Y, and the Z coordinate is the set of bits inside one word. So A of X, Y is, for instance, 64 bits, and the Z coordinate is the location of the bits inside the word.
29:03
So in the theta step, you have a bunch of source, one rotation by one bit over 64 bits, and that's it. In the row and B steps, we just move things around and add some rotations to change the bits within each of these lanes of these 64-bit words.
29:24
Then the key step, so that's the non-linear part of KechaKev, so in any good symmetric cryptographic function, you need some non-linearity, so that's the purpose of the key step. So you have a bunch of source, not and ends.
29:41
And then finally, one of these words, we just solved the round constant. So it's just, it's quite easy to describe, I think, and the operations that are involved are just source, end, not, and rotations. So what does it give in terms of software speed?
30:03
Okay, for the finalists, the five SHA-3 finalists, KechaK was not the fastest in software, yet on the modern PCs, we can see that actually KechaK is faster than SHA-2. We show this example, which is honestly
30:23
quite favorable to KechaK, but it's on AMD Bulldozer, but if you take a look at the numbers, for instance, on Intel Sandy Bridge, you can get similar numbers. So what you can see is that KechaK is faster
30:40
than SHA-2 on these kind of machines. But also, if you allow KechaK to be used in a mode where you can exploit parallelism by computing two KechaKs at the same time using a tree hashing mode, then you can actually be even faster, and in this case, be faster than MD5. Okay, so on another CPU, for instance, the Sandy Bridge,
31:03
MD5 is going to be slightly faster than the KechaK tree, but MD5 is broken, and so far, as far as we know, KechaK is not yet broken, so still, it's pretty fast, I think. During the competition, KechaK was really impressive
31:21
in terms of speed for hardware implementations. So it's really, really much faster than any of the other finalists, and much faster than SHA-2. So for the future, it's interesting, because nowadays, we have this AES instruction in CPUs.
31:40
Maybe later, hardware vendors will integrate some kind of coprocessor for SHA-3, hopefully, or an instruction in the CPUs. We'll see what goes on, but the speed in hardware is really an advantage for KechaK.
32:01
Okay, so I was mentioning in this pseudocode that we have 64-bit rotations. Now, assume that you have a 32-bit CPU, and you want to implement KechaK, and you're gonna have to put a lane, so 64 bits, on two 32-bit words,
32:21
and then the 64-bit rotations, they will be hard to implement, because one word by rotation will spill the bits to the next word, and the next word will spill bit to the first word. So that's kind of tricky and inefficient. Now, there's a trick that is actually quite specific
32:41
to KechaK, is that instead of coding the first 32 bits in one word, and the last 32 bits in the other word, you just put all the bits that are at even positions in one word, and all the bits that are in odd positions in the next word. Then the 64-bit rotation really becomes two rotations
33:01
over 32 bits each. So we can really re-express everything in KechaK in terms of 32-bit operations. Instead of applying 64-bit operations on 25 64-bit words, we can do something else on 50 32-bit words, including the rotations. So that makes the implementation of KechaK
33:22
also efficient on 32-bit platforms, something that is quite unique to KechaK, because as soon as you have a modular addition, you cannot use this trick, because you have the carries that you have to take care about, and that's not possible anymore. Of course, it can be generalized to other word sizes and so on.
33:43
And why is it also interesting? If you take SHA-256 and SHA-512, and you compare them, you can realize that actually it's almost the same function, except that one is applied on 32-bit words, and the other one on 64-bit words. So if you have to choose a security level, and you have to choose between SHA-256 and SHA-512,
34:03
you're also choosing the platform on which it will run best. And it might turn into a kind of mismatch situation where you want SHA-512, but you have a 32-bit platform, or vice versa. And in KechaK, you don't have this effect. You choose the security level independently of the, okay, thank you, of the target platform.
34:23
So I'm going to hurry up. And so, okay, so what KechaK can bring to the community, and what can the community bring to KechaK? So first let me give you some words about the Chatory Contest in itself. So the Chatory Contest in itself was really something open.
34:41
It was required by NIST that every submission should be public. All the details of the algorithm should be public. And this allowed the cryptanalysis. Everyone could try to break and find flaws in the competitors, for instance. So that was really open from that perspective,
35:02
from crypto research perspective. Also, all the optimized and reference implementations had to be open source. So this allowed open benchmarks. So for instance, eBash and XBX are really nice examples of benchmarks of all the candidates. And for KechaK, we tried to do something a little extra,
35:24
which is KechaK tools. So for our purposes, we also wanted to, of course, to look at the security of KechaK. And doing cryptanalysis, we needed tools to analyze the properties in terms of linear and differential cryptanalysis.
35:41
And at some point, we decided to publish the routines that we used for the analysis, and this created KechaK tools, which is, of course, open source. So the idea is to encourage cryptanalysis, not only for us, of course, but also for the others, and also to allow people to verify our claims.
36:01
If we say that, okay, KechaK has this property in terms of differential cryptanalysis, but we also published the associated code that helps verify these claims. And as a byproduct, KechaK tools can also generate some optimized code for KechaK. I will mention this again later.
36:22
Then at some point during the competition, there was not so many attacks on KechaK. So for us, it was good news. It meant, okay, KechaK is not so easy to break, hopefully. But on the other hand, some people would say, okay, maybe not so many people looked at it. It's too new, so maybe it's not a safe choice.
36:42
So we really wanted to encourage cryptanalysis, and at some point, we decided to give some little awards, not something so big in terms of money, to the best cryptanalysis results every six months or so. And so we gave some Belgian Trappist beer,
37:00
including Wes Vleterin to Jean-Philippe Omasan and Maitreyi Koratovich. Guido bought a very nice Italian coffee machine, and we gave also to Jean-Philippe and Willie Meyer. Then again, some beers to French girls, and then some chocolates to then lunch team.
37:20
Nowadays, we changed our mind in terms of how to encourage cryptanalysis of KechaK. Instead, we set up fixed and, yeah, we published challenges that have to be broken on some weekend versions of KechaK, so versions of KechaK with less rounds. So far, we have three images for one and two rounds,
37:44
on some instances, and collision on one to four rounds. And this contest is still open, so if you wish, you can take a look and try to break some of these challenges. So you won't get rich either with this contest, but I think it's nice, it sets really
38:01
concrete targets for cryptanalysis. Moving towards implementations, we also wanted to encourage implementations of KechaK on some exotic platforms, and it turned out that the two best, most original implementations were two implementations on a GPU, on a graphics processor,
38:23
two different instances of KechaK. Okay, so let's talk about implementations. If you go on our website, you will find two kinds of implementations. One set of implementations are reference implementations. There, the goal is to have readable code,
38:42
something that can be checked, and you are sure it's correct. You have some in C, in C++, in Python. And then another set of implementations are all the optimized implementations, and we wrote some, we and one of our colleagues,
39:01
Honi, wrote some code for 8-bit, 32-bit CPUs to set that included, that includes the bit interleaving technique I mentioned earlier, 64-bit platforms, and even using SSC and variants. Some of these implementations are in C,
39:20
some in assembly, especially ARM and AVR. For x86, I don't think we managed to beat GCC, actually. You can try. Please do so. Some of the implementations are in place so as to reduce the RAM usage, and I mentioned it, so we have some optimization techniques that are implemented
39:42
in KechaK tools to help you generate code that really fits for KechaK. So all these implementations are available, but I guess we are more cryptographers than developers, and the consequence of that is that we don't have a consistent library
40:01
that you could compile on your machine and that will select the right, the best optimized implementation for the machine it's been compiled on. So if you want, if you have time, you can help and try to take this implementation and try to make a consistent library, dynamic or static library.
40:21
You can also try to optimize these implementations. Probably you can do better than we did, or you can even write your own application in your own implementation in your favorite language. We have this document, the KechaK implementation overview that gives some implementation and optimization techniques
40:42
that you might want to read before diving into such a work. We just wish to say two things about the interface. So first, the chat-free standard is not out yet. Of course, KechaK has been selected as chat-free, but we don't know exactly what NIST is going to do. So we don't expect them to change KechaK in any way,
41:01
but there might be little details here and there that will make chat-free different from KechaK. At least chat-free might be a subset of KechaK, like AS is a subset of trying that. And I think that the best way to be future-proof is try to stick to the definition of sponge and duplex
41:21
to have a consistent API, I mean, consistent with the definition we put on sponge and duplex, because I don't think that NIST will try to change that level of abstraction. So if you have time, please go ahead. And that's about it. I had to say some credit for the pictures
41:41
we used in the presentation. And if you have any questions, please raise your hands. Thank you.
42:04
Hello, thank you for your great work on this talk. I would like to ask you, you were referring, some of you, I don't know which one of you was, to make the key derivation slow, right? There's a new trend. People also want to make it big, right, in memory.
42:22
How does KechaK fare in memory? Can you make it really, really memory hard? I didn't get the answer, the question. You mean that these implementations should take a lot of memory? Yes, that's the point. Yeah, KechaK by itself doesn't use a lot of memory,
42:41
but you could define a mode on top of KechaK that would use a lot of memory. So you mean like things like your S script, I guess. Yeah, I'm referring to script and design. Yes, yes. So no, KechaK is not, then you have to define a mode on top. So what I showed there on the slide was just to make it slow, but not to make it big.
43:11
Thank you again for the wonderful talk. My question is, so a lot of developers, a lot of us are developers, we don't often jump to crypto primitives,
43:21
like libraries, when we're coding our applications, we tend to stick to, you know, existing libraries that use the primitives for us. I'm thinking of like OpenSSL and other libraries where we're not actually, you know, we're not crotched deep up in the crypto primitives. So my question is, oh, here we go, I'm sorry.
43:40
My question is, how is sort of like KechaK progressing when it comes to adoption by existing libraries, like DJB's library, OpenSSL? Are you guys doing any sort of pushing into the community to get that integrated into stuff that us developers actually use? We're not pushing, we're not putting energy
44:00
in trying to push, but of course we hope that the adoption of KechaK as a chat-free standard will help people to, of course, to jump in and try to integrate KechaK in OpenSSL, for instance. Maybe some people fear that because it's not, the chat-free is not fixed yet, they also might want to wait.
44:22
We don't know exactly. For example, Python are recently. On this respect, our message is that we don't expect this to change KechaK in any way. Just maybe reduce the set of parameters that are allowed or something like that. Anyway, for example, Python has already recently implemented the KechaK version, so yeah.
44:55
Future in the press, it is stated that in the future there will be quantum computers
45:01
and quantum computers will break the crypto as we know it. How will this brand new primitive withstand such claims? Okay, thank you for asking the question. Actually, quantum computers are good at factoring numbers
45:21
and that's really applicable, for instance, to the RSA scheme. For the symmetric crypto, there are some quantum algorithms that can speed up, for instance, the search of pre-images. But basically what it does is a square root kind of thing and actually we would be back to the usual
45:41
security claim to the C divided by two. So for quantum computers on KechaK with the current security claim we have, it wouldn't change the security claim, so no problem. Hopefully no problem. Any other question?
46:12
Hello, my question is about the duration and the maturation of the algorithm.
46:24
You showed on one of the first slides that the algorithm was proposed in 2007 and since the last five years, don't you find improvements in it?
46:42
Okay, so the question was, we submitted the algorithm in 2008 actually and did we find improvements to make? Okay, we didn't want to change anything in the algorithm because it would invalidate the crypt analysis done so far.
47:01
So we tried to not change anything. What we did change is increase the number of rounds to increase the safety margin because of some attacks or pseudo attacks were given, but that's about it. We didn't change anything for the purpose of not invalidating the crypt analysis.
47:25
Okay, I am very sorry but the time is running out so if you probably can interrupt the day just after this talk. And we have something like two minutes before the next talk so thank you very much.