We should share our secrets
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 |
| |
| Subtitle |
| |
| Title of Series | ||
| Number of Parts | 167 | |
| Author | ||
| License | CC Attribution 4.0 International: 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/34800 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
| |
| Keywords |
34th Chaos Communication Congress154 / 167
1
2
3
4
5
6
7
10
11
12
14
15
25
26
29
30
31
33
34
39
40
42
43
45
46
49
50
53
58
59
61
63
65
68
69
71
73
77
78
79
81
82
83
85
86
87
88
91
92
94
99
100
101
102
108
109
110
113
114
115
116
118
119
122
124
125
126
127
129
130
131
132
133
134
136
138
139
140
141
145
147
148
150
151
152
153
154
157
159
160
161
163
164
165
166
167
00:00
Student's t-testInformation securityCybersexCryptographyKey (cryptography)Forcing (mathematics)Combinational logicCASE <Informatik>Single-precision floating-point formatAssembly languageArithmetic meanPoint (geometry)CryptographyNumbering schemeImplementationSecret sharingInsertion lossMereologyUniverse (mathematics)Multiplication signGraphics tabletConstructor (object-oriented programming)BitComputer scienceAbstractionLibrary (computing)Field (computer science)Elliptic curve10 (number)Information securityForestComputer font1 (number)Service (economics)Data recoveryNumbering schemeSerial portParameter (computer programming)Directed graphRational numberSequenceAlgorithmFlagFlow separationStudent's t-testBefehlsprozessorSystem callExclusive orThresholding (image processing)Computer animationSource codeJSONXML
09:16
Thresholding (image processing)Numbering schemeMathematicsMessage passingDistribution (mathematics)RandomizationLibrary (computing)Thresholding (image processing)Degree (graph theory)PolynomialNumbering schemeImplementationLine (geometry)Point (geometry)Computing platformForcing (mathematics)EncryptionQuantumSpacetimeMultiplication signCoefficientPhysical systemMoore's lawSecret sharingLinear algebraNichtlineares GleichungssystemInformationSet (mathematics)BitWell-formed formulaProcess (computing)MereologyTerm (mathematics)Key (cryptography)Image resolutionPower (physics)CASE <Informatik>CryptographyQuantum computerNetwork topologyLimit (category theory)Numbering schemeVector spaceDifferent (Kate Ryan album)Android (robot)Machine visionMicrocontrollerPositional notationInterpolationComputer animation
18:30
Library (computing)Data integrityComputing platformLibrary (computing)AlgorithmRandomizationSecret sharingPosition operatorOptimization problemPolynomialTerm (mathematics)Multiplication signNumbering schemeIntegerMereologyModulo (jargon)CASE <Informatik>Prime idealNeuroinformatikFunction (mathematics)Category of beingRule of inferenceStatement (computer science)Information securityPoint (geometry)System callState of matterSoftwareMultiplicationHybrid computerEncryptionMessage passingImplementationStructural loadKey (cryptography)StatisticsBefehlsprozessorModule (mathematics)QuicksortElement (mathematics)Data structureWordCodeOrder (biology)WebsiteINTEGRALSemiconductor memoryFitness functionCellular automatonCryptographyForcing (mathematics)High-level programming languageSlide ruleMultilaterationBitSound effectComputing platformCoprocessorDivision (mathematics)Galois-FeldMathematical optimizationMappingMathematical structureHard disk driveMathematicianPower (physics)Side channel attackGoodness of fitVulnerability (computing)Formal languageCodeCache (computing)Loop (music)Latent heatComputer animation
27:43
Rule of inferenceSoftwareComputer hardwareEncryptionImplementationLaptopLoop (music)Keyboard shortcutDivisorParallel portBefehlsprozessorBitMessage passingOperator (mathematics)Program slicingPower (physics)Library (computing)ExistenceProgrammer (hardware)Software testingAlgorithmDemo (music)CodeLogicImplementationSecret sharingINTEGRALMereologyArmStandard deviationNeuroinformatikMultiplication signLeakCASE <Informatik>Physical systemSoftwareVulnerability (computing)EncryptionAuthenticationCryptographyLogical constantStack (abstract data type)Keyboard shortcutComputing platformKey (cryptography)Loop (music)Benchmark2 (number)System callNormal operatorMassInterpolation1 (number)Vector spaceForm (programming)Presentation of a groupCentralizer and normalizerBackdoor (computing)TrailInformation securityNumbering schemeWeightBuffer overflowTwitterSubject indexingCellular automatonDivision (mathematics)Rule of inferenceMultiplicationLie groupCiphertextRight angleDigital electronicsMeasurementDisk read-and-write headCodeNumbering schemeComputer animationProgram flowchart
36:57
Secret sharingThresholding (image processing)Basis <Mathematik>Scripting languageCharge carrierLocal ringComputer animationSource code
38:25
Elliptic curveKey (cryptography)BitSet (mathematics)DivisorReceiver operating characteristicFlagSingle-precision floating-point formatIntegrated development environmentCodeReading (process)WordEncryptionLibrary (computing)Social engineering (security)Thresholding (image processing)ImplementationAlgorithmStructural loadInformation securityPoint (geometry)CASE <Informatik>Scaling (geometry)Unit testingInformationNumbering schemeSlide ruleNetwork topologySummierbarkeitCoefficient of determinationINTEGRALError messageFunctional (mathematics)CryptographyGoodness of fitSpacetimeObject (grammar)Volume (thermodynamics)WebsiteSoftwareHybrid computerCodeExecution unitSoftware testingDemo (music)GodReflektor <Informatik>Online chatImage resolution3 (number)Field (computer science)Computer animationSource code
45:37
Software developerCompilerLevel (video gaming)Computer programmingCASE <Informatik>Library (computing)State of matterCompilation albumTelecommunicationMereologyFehlererkennungCodebuchAssembly languageBitImplementationBlock (periodic table)Mathematical optimizationNumbering schemeCellular automatonProgrammer (hardware)Theory of relativityInformation securityVulnerability (computing)AreaFormal verificationINTEGRALFamilyCartesian coordinate systemPhysical systemInferenceCausalityView (database)EncryptionPoint (geometry)Bit rateDemosceneVorwärtsfehlerkorrekturSource codeReal numberFreewareLow-Density-Parity-Check-CodeAlgorithmField (computer science)Computer configurationCiphertextConnectivity (graph theory)Message passingSecret sharingHybrid computerStreaming mediaSemiconductor memoryExploit (computer security)Line (geometry)Multiplication signRandomizationPattern languageAuthenticationComputer virusPopulation densityParity (mathematics)Numbering schemeInstance (computer science)CryptographyAsynchronous Transfer ModeDiagram
52:29
Galois-FeldKernel (computing)Group actionProduct (business)Information securityProgram slicingCodeOperator (mathematics)Elliptic curveMathematical optimizationVariable (mathematics)Musical ensembleNeuroinformatikNumbering schemeLibrary (computing)Cartesian coordinate systemCASE <Informatik>CoefficientNichtlineares GleichungssystemThresholding (image processing)CryptographySoftwareCodeINTEGRALMultiplication signFamilyReal numberPower (physics)Position operatorBinary multiplierRight angleWebsiteMathematicsImplementationMultiplicationGoodness of fitBit rateAssembly languageVirtual machineBranch (computer science)Statement (computer science)Compilation albumReduction of orderSecret sharingCollisionDifferenz <Mathematik>Buffer overflowClosed setCore dumpInheritance (object-oriented programming)BitModulo (jargon)3 (number)PolynomialLogical constantCondition numberDiagram
59:21
MedianSound effectComputer animationJSONXMLUML
Transcript: English(auto-generated)
00:15
Our next speaker is a master student from the Netherlands. His name is Dan Sprinkles.
00:21
He told me that he's maybe the youngest speaker in this Congress. So if you know anyone, any speaker younger than 23, just let him know so that he loses the contest. And please pull out pen and paper, because this talk is a course Dan holds on his university,
00:43
so this will be graded afterwards. Dan Sprinkles, please, on We Should Share Our Secrets. Thank you, Harold, for introducing me, and thanks for inviting me here on this conference. It's kind of an honor.
01:01
So my name is Dan Sprinkles. I'm from the Radboud University, where I did a resource internship on an algorithm called severe secret sharing. So this talk is kind of a bit about severe secret sharing, but severe secret sharing is not new.
01:20
And it's kind of about crypto implementation, because I would like to make a point to you. So first of all, I'm Dan Sprinkles. I study at Radboud University, where I did my bachelor's in chemistry. And after finishing chemistry, yeah, I just skipped to computing science, because that's obviously better.
01:48
So on a regular day, I'm currently doing implementation of elliptic curve cryptography. And that's kind of a specific field. So I would like to share some of my knowledge with you on how cryptographic implementation
02:04
actually works. So the other people that are involved in this publication, in this research, are Peter Schwabe, which is my supervisor, and Sean Moss. He's the CEO of a company in Taiwan, in Taipei. And they do a Bitcoin while blockchain stuff.
02:27
So first of all, because I don't know really what the mathematical knowledge of you guys are is, I would like to ask you, who've heard of this?
02:44
Okay, that's really good. Second question, who actually knows why we say this all the time? Okay, so that's a pity, because I wanted to explain this.
03:02
Well, actually, I wanted to explain the second one. So rolling your own crypto is a bad idea, because it's not that easy. You can do stuff wrong very easily. You can screw it up very easily. And the second one, you've also got this case. Implementing your own crypto, as we have seen yesterday in Filippo's talk, is really
03:23
hard. And in his case, one carry flag in the CPU can screw up your security, and in his case, have a full private key recovery. So in this talk, I'm going to try to explain to you why is implementing your own
03:42
crypto so very hard, and for this, I use the most easy, most simple crypto scheme, which is Shimmy Secret Sharing. So this is my outline. I'll talk about what Shimmy Secret Sharing is, like theory, how can you do this stuff on paper, and then I'll go into the implementation.
04:03
I think this is a better outline. I'll try to make the first part a little easy to understand, and the second part maybe a bit less easy to understand, but I think that everybody here can easily follow this talk. So, first part, well, we've got this, well, problem.
04:26
Most people don't really consider this a problem, but when you've got a key, and I always use the example of a bitcoin wallet key, because bitcoin is a buzzword, and everybody will go to your talk if you mention bitcoin once or twice in your abstract.
04:44
So you've got your bitcoin key, and you want to keep your bitcoin key secure because it holds, I think, maybe tens of thousands of euros in the worst case, and secure means two things. The first thing is nobody can ever compromise your secret, so your secret has to be secret,
05:08
and the other thing is you don't want to lose your secret, because losing your secret also means losing your money, and the straightforward way to back up your keys is to give one of
05:23
your keys to your bank, and you store it on a piece of paper over there, or you take somebody you really trust, like your spouse or your lawyer, and you give it to them. But then you have this thing called a single point of failure, and a single point of failure is one way that stuff can easily go wrong.
05:44
So instead of giving it to one person, we don't really want to give it to one person, because one entity may break, and this may be like our house burning down, because that piece of paper was stored below our sink, and now it's gone.
06:04
So instead we really want to split up our trust into little pieces, and every piece we want to give to some entity or some person that we trust to keep it secure for us. And Shamir's secret sharing solves this. But first let me take some easy examples to, like, how would we do this in a simple, well,
06:28
straightforward way? And the first idea would just be, okay, we have a key of maybe, say, 30 characters, and we just take the first 10 characters, and then the second 10 and the third 10,
06:42
and we give the first 10 to a single person, and the second 10 we give to another person, et cetera. But in the case of crypto keys, so in the case of Bitcoin wallet keys and stuff, then if you've got the first two, it's quite easy to brute force the key to get the last one.
07:04
So this is not really secure. A more theoretical, more secure approach would be to be, would be to use some kind of one-time pad construction, and a one-time pad construction is where you generate a random
07:21
key, and then this key will actually be used to decrypt a secret, and in our case, we can generate two shares, that's how I'll call them. Our shares A and B, and A and B are randomly generated. And our randomly generated A and B we use to generate another share C, and we generate
07:44
these things by using the actual combination of M, A, and B, where M is the secret. And then to reconstruct the secret, we can compute the XOR combination of A, B, and C, and we can see why this works, because C equaled M, A, and B, and because two XORs
08:05
cancel each other, those As and Bs cancel each other, and then we get M back. But here, we only solved the single point of failure problem in the case of confidentiality. We only know that if we do this, then the secret will remain secure.
08:24
But this does not solve losing one of these shares. And in our case, if backing up your secret, if losing your secret is your problem, then this doesn't solve anything. So, we want something better.
08:42
And we have something better, and we have something better for about 40 years now. So Shamir's secret sharing was published by Shamir almost 40 years ago, and it's called a threshold scheme. And the threshold scheme implies that we can share a number of shares from our secret,
09:03
and in the parameters of our scheme, we can set a number of shares that is required to restore the original secret. So we don't need all the secrets, we don't need all the shares to restore the secret, we can just, we'll say, distribute five shares, and then only three of them will
09:23
restore our original secret, and losing one or two shares isn't really a big problem for us. Also, this scheme is provably secure. Provably secure is often used as a term, I don't really like this term because it doesn't really say anything, so I use the term information theoretically secure,
09:44
which is quite better. Information theoretically secure means that if you don't have enough shares in this case, then you won't be able to restore the secret. And this is not like encryption where the key is unknown, where you can brute force the key, you can try every key, but the key space is so large that it's impossible
10:03
to do this. Now in this case, even with unlimited power, and millions of years of computing power, we still will never be able to reconstruct the secret. And so this implies also that this is resistant against quantum computers, because extra
10:26
computation power does not give us an advantage here. So here's an example. Let's say I've got my secret message, my secret key M, and I want to distribute
10:40
this M among my friends, so that they only have their shares and cannot do anything, but I would still be able to recompute my original secret if any time I lose my secret. So I distribute five of these shares by just computing them.
11:00
And then each of my friends has a share. I might lose my share sometime in the future, then I ask my shares back, and even if some of them, well in our case, one of them, spoils the fun and does not give me my share back because he's evil, then in our case, we can still restore the share, because in
11:21
the beginning, I set the threshold value to four. So in this case, four shares is enough to restore my secret, I use these four shares, I recompute my secret, and I get back my message M.
11:41
So obviously this is easy to understand when you see this, so let's go into the math. And the math is quite fun, and this is like notation, quite difficult to understand, but I'll tell you anyway. So for a threshold scheme of where we want to distribute N shares, and the thresholds
12:08
of recombining to the original secret is K, then we construct a random polynomial of degree K minus one. So A times X to the power K minus one, up till the lowest coefficient.
12:25
But instead of filling in the lowest coefficient as a random value, we fill in the lowest coefficient as our secret message. So this simplifies to just using a number. Then we've got this polynomial P, and we start generating points on this polynomial.
12:43
So for X equals one, X equals two, X equals three, et cetera, up till N. Then we distribute these points as the shares, and we distribute these points so that in the end we can use these points to reconstruct the secret. And in our case, so when we got this polynomial, when we got all the coefficients of this
13:07
polynomial, we also have the lowest coefficient, so we do have M. So we take these points, and we can make a system of equations, just like back in linear algebra.
13:20
And this system of equations we can solve by filling in the X and Y values of these points. And if we've got enough points, then we can actually find the original polynomial, and we will do this. So in practice, we use a set of formulas called Lagrange interpolation, which you can look up on Wikipedia, but this is easier to explain, so I'll explain it by using
13:43
this. So this may be a bit hard to understand, so I've got pictures. First, we take 42 as our secret message, obviously. Then we generate a random polynomial. In our case, our first coefficient is 4, and our second coefficient is minus 25.
14:05
So you've got this nice parabola, and we can construct points on this parabola, so that we, like in our case, 4 points. And we saw here 3 coefficients, so a threshold of 3, important.
14:22
We see that if you only have 2 points to reconstruct a secret with, the only thing you can do is, well, you can generate a line, and they'll get some random value on the lowest coefficient, and, well, this does not give back your secret.
14:41
Only if you take a third point, then you can make this parabola, you can fill in x equals 0, and you get back your secret message. So solving the system of equations is like filling in these x and y values, then you
15:04
can solve this on a piece of paper, you can do this within, I think, 5 minutes, and then you will get your message back, which is 42. So, this is all good. Well, we know this thing is information theoretically secure, so nothing could go wrong.
15:23
Well, yeah, it can. So this thing is information theoretically secure for confidentiality, which means if your secret is secret, it will remain secret, but nobody said you couldn't change the secret.
15:41
So what we'll want to do is to hack this, we just have a share as one of these persons, and we will tamper with this share, we make another share which looks like the original share but actually constructs to a different secret. So how we can do this is, here is a polynomial of degree 2, degree 1, so this is just a line,
16:07
take two points, if I generate another point, and we generate a new line through this point by me giving back a malicious secret or a malicious share, then we get a new point which is not the original point.
16:22
And if I have enough information about the original secret, and if I have enough information about the X values of the other shares, then I can actually choose this point. So how to solve this? Well, there's two things to solving this, and I'll come back to this later.
16:41
The first thing is I knew that the other point that was shared was on X equals 2. So this gives me information about how I can make this specific slope to get a new value. And the other thing is I knew something about the original secret, and Shamir's secret sharing
17:01
assumes that the secret is secret, well, because it's secret sharing, but this may not be the case in every time. So I knew something about the original secret, so a solution would be to randomize this secret. And well, you might say, but then you cannot secret share anything anymore.
17:21
Yeah, I'll get back to this. So here's part two. So this was my introduction, now I'll get to the implementation part.
17:44
And this is where most normal cryptographers stop talking, because they say we've got this beautiful scheme, it works, we know how to use it, and now it's done. Like implementation is magic, implementation is easy. And as a cryptographic engineer, I would like to make the point to you that cryptographic
18:02
engineering is not always the most easy part of this process. So the story is that Bitmark, a company in Taiwan, asked us, hey, we want a library for Shamir's secret sharing, any library. And we asked, how do you want it?
18:21
Yeah, well, we want it secure, and we want to be able to use it anywhere, on any platform like Android, iOS, maybe microcontrollers somewhere in the distant future. So OK, we think, what libraries are out there? So there's SSSS and GFshare, which are the most popular libraries.
18:43
And we looked at the code, and we needed code that was really, really secure, and also secure against side channel resistance. And this code either didn't really port well to other platforms, or it had some cache
19:01
or timing flaws that in our case weren't really acceptable. So this does not mean that these libraries are bad, just good code, good libraries, only for our requirements, this didn't fit.
19:21
So yeah, we're going to implement this thing ourselves. And I'll take four challenges that I have had with my implementation. And these are not the only four challenges that I had, there are a lot more challenges. But I think these are the best to explain cryptographic implementation challenges to you.
19:45
So the first thing is this integrity problem, which we saw on the last slide from the previous part. And how to encode our values, because we were only using just values, and not like
20:01
bytes or integers, and we will have to choose something to compute in, how to prevent side channel attacks, I'll explain how side channel attacks work, and how to make this thing fast in the end, because I like really fast code, and I like really challenging optimization problems.
20:24
So the first part, this integrity problem. We could either randomize these x values, or randomize the secret. And these x values are not really easy to randomize, because we would need to choose really big
20:41
x values, and in our case this really slows down our computation, and the security decreases with the number of shares that we give out. So instead we chose, okay, we just randomize the stuff that goes in the algorithm. And we've got a really random polynomial, and nobody can use anything.
21:02
So we use some term which is called hybrid encryption. So instead of using our message and pulling it directly through the Shamir secret sharing algorithm, we instead we generate a randomized key. This thing we can pull through the Shamir secret sharing algorithm, and then we use this key
21:23
to encrypt our secret message. And so in this case, we don't have to pull text through an algorithm which is actually used for, well, numbers and stuff.
21:41
And more importantly, we can pull this thing through an algorithm which is used for randomized numbers. So this is how it works. We encrypt the secret with a randomized key, and when we want to decrypt it, we just take the key shares, so the shares of the keys, we get the key back by recombining
22:03
the original key, and then we use this key to decrypt the original ciphertext, and this week we will get back the secret. So the second challenge, how to encode our values.
22:20
This may be a little bit hard to understand why this is a problem for people that don't know really the finite fields arithmetic stuff, but it essentially boils down to this. In the beginning we had these numbers, and when we're working in computers, we cannot
22:41
just use any numbers, because we're limited, we're restricted to using integers, assigned integers, or bytes, or et cetera. So in our case, we want to take a structure, a mathematical structure, in which we can
23:02
compute these numbers. And we want to take our original, like this key, and we want to map it to this structure, to this mathematical structure. And the most common thing that we do in cryptography is we take
23:22
a really large prime, and we take this prime, and we compute modulo this prime. And this works really well for spots where we actually have to have a prime order, or a large order. In our case this is not a requirement, so we will map
23:42
to a structure that has exactly 256 elements. So when we have a structure that maps, that has exactly 256 elements, then we can map a byte to one of these numbers. And for the mathematicians
24:03
the bottom thing is what we use. We use a finite field reduced by the rhinal polynomial, and you'll see later on that this allows us to do a really, really powerful optimization trick. And it boils down to the fact that when we have
24:23
every byte separately in our key, then we can just implement our algorithm for one byte, and then we just put a for loop around this. And for each byte, we will secret share. And this allows us to parallelize over these bytes. And then later I'll show
24:43
how we do this. But first, rules of cryptographic implementation in software. So side-channel attacks are attacks that are not attacks on the output of an algorithm. So let's say I put something in the algorithm, I see what kind of output
25:03
it delivers, and then I'll know if the algorithm did something or did not do something. The side-channels are a little bit more subtle. Instead of taking the output, we take a property of the algorithm. And we take a property that we can measure. And the best example is timing. We can measure how long an algorithm takes.
25:23
And if we know that a key contains a one at a certain position, and then it will take a longer time to compute, then we can measure the algorithm's computation, and if it takes a long time, then we'll know, oh, there's the one. And if it takes a shorter time,
25:43
then we'll know, oh, it's probably a zero. And we can do this iteratively, and do this number of times, and we can take our big statistics toolbox and put loads of statistics on this, and then it's sometimes really easy to crack an algorithm. So the first rule
26:02
of side-channel resistance is we may never branch in an algorithm. So branching is you have an execution path and you choose where to go next. So if statements are forbidden, else statements forbidden, logical and logical or are forbidden, switch statements
26:22
are forbidden, etc. So the second one is similar to the first one, but uses a specific trick, and it's called a cache timing attack. So we use the fact that if we take something from memory, the timing may be different when
26:44
a piece of data, when a piece of memory is already in CPU cache, then when it has to be fetched from the main ROM module. And this can be a really big time, and we can have really big, bad vulnerabilities because of this. And the last one is something that's often forgotten.
27:04
We are not allowed to use variable-time instructions from the CPU. And so on Intel processors, for example, the division instruction is often variable-time. But also if you look at the manuals of some maybe older CPUs,
27:25
you also see that some other instructions, for example the multiplication, may actually be in variable-time. So we really have to look out for this. And that kind of brings me to my last point. How do we do this in a high-level language like C?
27:43
And how do we do this fast? And this we do through bit slicing. And bit slicing is a really awesome technique. So we had all these bytes, and we shared these bytes separately. So what we can do
28:04
is we can parallelize over these bytes. And remember that a CPU is made up only of logical instructions, right? So we would be able to multiply and add using only logical instructions, right?
28:24
So what we do is we take these bytes. We take the first bit of every byte, and we put it in a register. And we'll take the second bit of every byte, and we'll put it in another register.
28:40
And for every bit in these bytes, we will put it in a separate register. And in the end we will have used eight different registers. So now we'll implement this algorithm instead of using normal operators like, I don't know, division, multiplication, etc. We will implement this thing using only
29:04
logical bitwise operators. So only really bitwise and, bitwise XOR, and bitwise OR. And remember, this is a full adder for two bits, and this is just a really small part of how a CPU
29:24
adds two numbers. And this is an example of how we could do this. So we'll make this whole thing inside these kind of circuits, and we will have finished this computation. In our case, we were building on a 32-bit platform, so we could easily run on older ARM devices.
29:45
And in this case we have a really large, more bulky computation, but we also have a parallelism factor of 32. And, well, this was a 32-bit platform. If we use a 64-bit platform, we will get
30:03
this 64-bit parallelism. And even on AVX2 and AVX, this works. And even if the CPU wouldn't clock down, this would have worked in AVX512. So, in the end, we've got this overview of how we
30:24
implement such an algorithm. So we take this really random thing. This, by the way, is one of these other challenges that I did not talk about. And we generate a random key. We encrypt with this key our secret message.
30:44
And then we take this key and we bit slice it so that we actually can compute our secret shares
31:00
in parallel. And then when we are done with this computation, we actually have to undo the bit slice operation and we get our shares. And restoring the original secret is just the other way around. We take our shares, we bit slice our share values, we execute the recombination
31:24
algorithm using these Lagrange interpolation formulas. We have to undo the bit slice operation in the end. And we use this key to decrypt and verify the original cipher text. So
31:42
the performance of this thing is quite good, I think. Well, these are kind of bad benchmarks because I did not make them that proper and, well, I made this presentation, did some benchmarks, not really accurate. So
32:01
a tight C loop takes 10 microseconds, etc. The other things also take 10 microseconds. I have no clue why the Rust bindings actually are better than the other ones. If anyone is able to tell me, please do. But in the end, roughly 100,000 calls
32:22
per second. And this is plenty of performance. We don't really need to get more performance. But if we do, well, I noticed that about more than half of the time is in the encryption algorithm and not in the
32:41
better encryption implementation. Because in our case we use Tweetsalt and Tweetsalt is a really secure, really good implementation, which is really portable, but it's not optimized for performance. So in the end, stuff that could have gone
33:03
wrong. And the first thing is that, well, this is something that we as cryptographers often see on, for example, stack overflow, that people think that encrypting a secret will make it secure against integrity. Because if a secret is encrypted,
33:24
people won't know how to change it to get another value. But in the case of cryptography, this is not the case, people. Integrity is only assumed if you have a message authentication code, or in our case, you use an authenticated encryption scheme.
33:45
And the second thing that could have gone wrong is timing attacks. And timing attacks is stuff that actually exists in a lot of implementations. And so this gives me the impression that the amount of cryptography
34:00
engineers in this world may be a little bit too small, because otherwise we would have had constant time crypto implementations, for example in the Go standard library, which I think we may not have. Or we wouldn't have timing leaks in gcrypt,
34:20
which was published recently in the May the 4th be with you paper. So this is kind of a problem. And this last problem that, in this case, it was in Armory. And Armory is a high-security Bitcoin wallet system. And Armory had this German secret sharing
34:42
implemented. And they did not generate the polynomial fully randomly. And I think this actually led to quite bad vulnerabilities in their implementation. So it's kind of dangerous terrain to
35:01
implement this cryptographic code. Okay, here's a sidetrack. This is something that most programmers, so not limited to cryptographers, most programmers do not think about the existence of their code as a tool for everybody to, well, do whatever they want with it.
35:22
And I think it's important to ask ourselves, we have built this software. What does this software, how is this software meant to be used? And in the worst case, can it be used for people with malicious intent, for people who don't actually want to play by the rules?
35:43
And I'm telling you this because I think that most programmers will actually have to think a bit more about this sometime. So in our case, we distribute secrets to the masses.
36:01
And we distribute secrets to trusted people and stuff. So I do not really think that the malicious user is able to use this for many malicious purposes, because power is most of the time
36:21
centralized, and this tool most of the time allows us only to decentralize this power. But the most important thing is that we are responsible for writing our own software, and whether I'm making a cryptographic library, or if I'm making testing code
36:44
for Volkswagen, then we are responsible for stuff that happens with it. So to get back, I'll show you a small demo. This will obviously grow wrong.
37:05
So, I have installed my secret sharing tool. Yeah, I'll try to. So, can we use plus? No, we cannot use plus. Ah, we can use plus.
37:26
Okay, how does this work? Let's make us five secrets, and we have a restoration threshold
37:43
of four. What's my secret? Well, yeah, I don't know.
38:14
So, we've got a couple of secrets here. So here's the third one, and I'll copy-paste this into my
38:23
restoration script. So we start with, so I'll ditch the first one, and I'll take the second one up to the fifth one, so you can actually see what happens when we ditch one of those.
38:54
Yes, demo gods. Okay, so in the beginning of the talk, I said to you, do not implement
39:01
your own crypto. And, well, I hope that you may have seen a couple of reasons, and have, like, I have given you quite a bit of feeling about why implementing crypto is hard.
39:21
And so I'll say to you, please do implement your own crypto. Try to implement crypto, try to understand how the crypto works. But if you're not really sure, if you're not 100% sure about what your implementation does, and if your implementation is secure against every attack factor,
39:43
if it's, I don't know, maybe side-channel resistance, or checking that single carry bit in this single flag register, then put a big warning in boldface letters at the top of your readme saying, hey guys, this is academic code,
40:04
I used this code to learn myself how crypto implementation worked, but I'm not really sure, I've not checked this with any cryptographers, please do not use this for your really high-secure, well, wallet software, or whatever. So,
40:25
that's it. These are some people I want to thank. And my slides can be on my website, can be found on my website, I've got some extra reading for you if you'd like to have some.
40:40
I forgot to register my DECT extension, this one does not work. So, that's it. Do you have any questions? Dan Sprinkles, thank you very much.
41:01
Any questions? Please feel free to assemble behind the microphones, and I will put you through them. Let's start with number three. How do you make sure you didn't make an implementation mistake? Do you have unit tests? Well, so, that's the terrible thing, is that in the cryptographic implementation world,
41:26
well, I do have unit tests. Unit tests do not always fix your problem, because your keyspace is large enough that you won't be able to test everything. And in the case of my elliptic curve implementations,
41:45
the only thing I can try to do is prove every single function, and that's really error-prone and can also be done wrong, but I'm honestly not 100% sure about the fact that my implementation does not contain any errors.
42:05
I checked it, people checked it for me, and I'm, well, quite sure, but I still am not this 100% sure, and I think this is with all code that is security relevant in our field.
42:24
Microphone number four, please. First of all, thank you for the interesting talk. One technical question. I've seen from your demo that the cipher, the actual shares are quite a bit larger than the original text.
42:44
And my question is, how does the number of, or the number of bytes information scale with the number of shares you have and with the number of required shares? Okay, so I'll get back to this slide.
43:04
What we do here is we have this encryption key, and we have this point, this x value. So we have to add one single value for x, so one byte, because we were working bytes, and this is the one, the two, the three,
43:21
and this will be the first byte of our share, so this adds one byte. And then we'll take this key, and this key has to be randomly generated. And this key, in our case, we use salsa20 as an encryption algorithm, which uses a 256-bit key, which is 32 bytes.
43:41
And this adds another 32 bytes. So in the end, we only have 33 bytes, which are actually added to our shares. But the amount of shares that we generate and the threshold will always generate the same amount of bytes in the shares.
44:03
And actually, from the shares alone, you cannot see what the threshold of the algorithm was in the first place. Does this answer your question? And we have a question from our IRC chat. Yes, first of all, Gailis is saying on Twitter, thank you for losing LaTeX, so I just forward this.
44:23
There's a big discussion on the IRC, how to defend against social engineering. What if some of the shareholders evenly plot against you, and are there any ideas to remedy this issue? Yeah, that's a good question. That's a thing that I haven't solved for myself, because I don't have every person's environment.
44:45
So my own recommended stuff in my readme and stuff is generate five shares, and four shares will construct your original secret. But even this, I'm not aware of if this is secure. In your case, you have to choose yourself who you trust with your shares.
45:06
So I cannot really answer this question for you. Okay, microphone number two. A question about the integrity problem. How exactly does your hybrid encryption engine solve this problem,
45:23
and what does your tool if you put in some tampered secret? Ah, yeah, that's a good question. So here, we actually could spoil the secret, because the original secret was some value that we knew.
45:45
And what this does is it randomizes the value that comes out of any tampered secret. So if we tamper with a share, if we change even one bit, then the value that will come out of the secret will be fully random,
46:03
because the original thing was fully random. And what our algorithm will do is in the salsa20-poly1305-authenticated-encryption-decryption step, this will actually fail on the authentication tag of the ciphertext,
46:24
and it will say recombination failed, or otherwise the key or the ciphertext was invalid, and will just say no, this won't work. Mic 1, please. Hello. It's similar to a previous question probably,
46:42
but I mean assuming I'm trying to protect my huge Bitcoin wallet, and in that case I don't want to really fully trust anyone, and would it be an option to, so I would like to avoid that if three of my family components agree with each other,
47:01
they steal my wallet basically. Is it an option to double up the shares and they keep 50% of it? But then you also have the larger problem of losing the shares, actually it may be a risk for you. So that's the trade-off here.
47:20
So let me tell you a small anecdote of which you can use this also, is for example if you've got your Bitcoin wallet, and you want your relatives to be able to inherit your wealth after you die, then you may choose to distribute your shares among your family members and people,
47:41
so that after you die you can actually tell them, yeah okay then you're allowed to reconstruct the secret, and then you can inherit my Bitcoin wealth, and this is also an application for this. But in your case, well if you have a system where you have yourself most of the shares,
48:02
then in this case you always have the fact that if you lose those shares, then you will also maybe lose the secret, which in your case may be what you want. Thanks. IRC please.
48:22
Dotik is asking, if you're separating the message into individual bytes, and then applying SSS for each byte separately, doesn't it suffer from the similar problems as the electronic codebook mode in stream ciphers, namely that data patterns are not hidden? Yes. So that's also why we use this hybrid encryption scheme.
48:46
So this hybrid encryption scheme, this encryption works on the whole block, on the whole message, and the Shamiya secret sharing works on the individual bytes, and there's no pattern in there, because we generated this secret key fully randomly.
49:03
Okay, microphone 3 please. Well, I come from a field which is quite similar in a way to the problems that you have considered here, which are error correction codes. And, well, in my field there are a lot of error correction codes,
49:22
and for instance there is the low density parity check code, which can be, from my point of view of course, in a way hacked to make a similar implementation. But have you considered other codes? So, I did, and the reason that we actually used this was not because of real security stuff,
49:48
but because the Salsa20 poly1305 implementation was already there. If I would do this in a more sophisticated way,
50:02
Shamiya secret sharing is not the only threshold scheme that exists there, so we also got Feldman verifiable secret sharing, and we also have Peterson verifiable secret sharing, and this is actually secret sharing that solves the integrity problem, but they are a little bit more complex,
50:22
so that's probably what I would have used. Number 2 please. Hi, great talk, and back to implementations. Could you go a bit into the relationship between optimizations, both from compilers and just what we as programmers tend to do ourselves,
50:44
and vulnerabilities in general? Basically what I'm asking is, do you hate compiler developers? Well, so yeah, compilers sometimes make assumptions that are correct in normal code,
51:01
but when I do something in my C code, then I mean it, yes. No, I do not hate C compiler developers. I choose to program in C, and the really, really low level stuff I actually program in assembly,
51:21
so yeah, well, they do not have this obligation to cater to us as cryptography engineers, so yeah, what can I say? Maybe it's nice to have an option where you can say to the compiler, yes, I really, really want to use these things, and please do not assume that because this stuff in memory is not read after this line,
51:48
that you do not have to re-initialize it to zero, because I really want to set this key value to zero in the end. So yeah, well, there are tricks in compilers that you can exploit,
52:01
and this is mostly the way we do it when we actually need to really tell the compiler, yes, we want to do this this way, and most of the time, Peter and I, we look at the assembly code that rolls out of it, and we think, okay, well, they did it, and yeah, no, it's just okay,
52:20
and if it's really, really critical, then we implement it in assembly. What would be your advice to, you basically told people to implement their own crypto, and since we have not enough cryptographic engineers, that's a good advice, but what would you tell them to check for, how to see if there is going to be a timing problem?
52:42
So yeah, you can always look at the assembly code and see if there's stuff. Well, so the first two items that I showed you,
53:00
this do not branch and this do not lookup, well, compilers won't do this wrong. If you don't put an if statement there, they won't actually introduce a branch, and also, most of the time, they won't change an instruction, well, like a bitwise instruction, they won't change it to a multiplication either. So if you have these kinds of really simple instructions,
53:21
then it's actually, well, not that big a deal. And another thing is, this is maybe not really good for me to say, but well, there are a lot of not really good implementations out there,
53:43
and as long as your one is better than the others, then it's good, right? Microphone number four, please. Hi, so you said we don't have the threshold in the shares.
54:00
What happens if we give the reassembly application more or less shares than it expects? Does it try to solve the polynomial of the wrong degree, or? So if we have less than the required amount of shares, then it will reconstruct the bad polynomial,
54:23
and it will try to use the lowest coefficient of this bad polynomial to decrypt our secret, and this will fail. If we have too many shares, then the solving of the equations will actually just work.
54:41
So more shares will not be a bad thing. There's only one problem, which is if you add duplicate shares, then it will fail with the first error, and that's one thing that I did not solve yet in a good manner.
55:02
Okay, number three. Hi, thank you for the talk. How close is your code to be used in production? So, do you mean? I mean how much review it got, and stuff, this thing, and whatever is needed.
55:21
How safe it is to use it in production. So that's a really dangerous question, because if I say it's super safe, then people will use it, and it may turn out that it was not safe, and then I'll like, it's my fault. Well, no. So the efforts I did was I made it, and I checked it by putting it,
55:44
so by like having it checked by other cryptography engineers, and having my methods checked by other cryptography engineers, and in the core C code, I expect there won't be any problems, because also the way we do this in this bit slice operations,
56:04
using only bitwise operations, it's quite easy to do this correctly. Thank you. And go ahead. Thank you. You were talking about optimizations, and I was thinking that instead of picking one very large prime
56:22
to use as a modulo for a finite field, pick a prime which is just slightly bigger than your secret. Is this implementable? Can you use a variable prime? Yes, but modulo reductions are tricky in how constant time implementations are done.
56:50
So when we do modulo reductions in elliptic curve cryptography, we most of the time we do this kind of conditional subtraction,
57:02
and this conditional subtraction will be done only when a number is larger than a prime, or if a number overflows or underflows during a subtraction, and this can be quite easily done in software,
57:22
because we can just do this in constant time, but this becomes a lot harder not only when our prime is not chosen at the time when we built the software, but also when this prime is not really regular.
57:42
So that's why there's this prime which is called 2 to the power 255 minus 19, which is a really popular prime to implement crypto with, because it's really easy to reduce, because any number above that, we can carry it to the lowest limb and multiply it by 19.
58:03
But if we do not have a really regular prime, then this problem becomes actually really hard, and we would have to use a multi-precision library, which are often not side-channel resistant. Right, thank you. Number 2, please. The way I understand this, right, the security of the whole thing
58:23
depends on the integrity and security of the machine it's being computed on. Is there any way to distribute the computation of a Shamir secret sharing? Oh, Shamir secret sharing? No, there ain't. I think that there are threshold schemes, yes, where you can compute these things separately on separate computers.
58:45
But in the Shamir secret sharing case, we assume that the dealer's computer, so the person who gives out the shares, is actually trusted, because it also holds the secret. So if we trust the computer to hold the secret, then we'll also trust it to compute these shares, yes.
59:03
Any further questions? No. So then please, a warm applause for Dan Sprankles.