Merken
We should share our secrets
Automatisierte Medienanalyse
Diese automatischen Videoanalysen setzt das TIBAVPortal ein:
Szenenerkennung — Shot Boundary Detection segmentiert das Video anhand von Bildmerkmalen. Ein daraus erzeugtes visuelles Inhaltsverzeichnis gibt einen schnellen Überblick über den Inhalt des Videos und bietet einen zielgenauen Zugriff.
Texterkennung – Intelligent Character Recognition erfasst, indexiert und macht geschriebene Sprache (zum Beispiel Text auf Folien) durchsuchbar.
Spracherkennung – Speech to Text notiert die gesprochene Sprache im Video in Form eines Transkripts, das durchsuchbar ist.
Bilderkennung – Visual Concept Detection indexiert das Bewegtbild mit fachspezifischen und fächerübergreifenden visuellen Konzepten (zum Beispiel Landschaft, Fassadendetail, technische Zeichnung, Computeranimation oder Vorlesung).
Verschlagwortung – Named Entity Recognition beschreibt die einzelnen Videosegmente mit semantisch verknüpften Sachbegriffen. Synonyme oder Unterbegriffe von eingegebenen Suchbegriffen können dadurch automatisch mitgesucht werden, was die Treffermenge erweitert.
Erkannte Entitäten
Sprachtranskript
00:01
2 and a half
00:08
I
00:14
think on its because uh misery Moses through from the movements is made was done sprinkles uh you told me that he's maybe the youngest speaker on this road when this Congress so if you know anyone any speaker younger than 23 just let him know so that he loses the contest and pull out pen and paper because this talk is a of Don also on his university so this will be graded afterwards the done sprinkles please on we should share sequence thank you Harold for introducing me and thanks very much like me here on this conference is kind of a lot so my name is Don sprinkles and I'm from the Robert University where I data reasons into ship on the algorithm culture a secret sharing so this talk is about kind a bit about service secret sharing this be secret is not new and it's kind of ballots have implementation because I would like to make a point to you so 1st of all
01:30
and that's bangles I associate Robert University where that my Bachelor's in Chemistry and after finishing chemistry yeah I just skip to computer science because that's obviously better the part of it yeah so the on a regular day I am currently doing implementation of elliptic curve cryptography and that's kind of a specific fields so I would like to share some of my knowledge with you on how cryptographic implementation actually works of to the other people as that are involved in this publication in this research on British mother which is my supervisor and sure loss this company of of the the CEO of a company in Taiwan and that they and they do but much but that's going well blockchain stuff the that so 1st of
02:28
all because I don't know really Lee what the method that that goal and knowledge of you guys are is I would like to ask you that we have heard of this the again that's good 2nd question who actually means why but who actually knows why we say this all the time OK so that's a pity because I want to explain this the well actually I would this be the 2nd 1 so rolling around crypto is a bad idea because it's not that easy you can do stuff but wrong very easy you can screw it up very easily the 2nd 1 you've also got this case implementing Eurocrypt 0 as we have seen yesterday Philip talking is really hard to and in this case 1 carry flag in the CPU can screw up this security and the in his case have a full key uh fullprice cure recovery so it is not going to try to explain to you why is implementing urine crypto so very hot and for this I used in most he's the most simple crypto scheme which assume a secret sharing so this allowed I'll talk about so I
03:56
want to make a secret sharing is like Teri how can you do this stuff on paper and I got into the implementation and I think this is a better
04:04
outline I'll try to make the 1st part the little like easy to understand and the 2nd part maybe a bit less to understand but I think that everybody here would eat can easily follows stock the so the 1st part the well and we've got this while problems that most people don't really consider this problem that's so when you've got a key and I'll always use the example of the bits going Wallace keys this bitcoin is a buzzword and everybody will go diastolic if you mentioned that's kind 1 of 1 of the ones are twice in your abstracts the so you've got your bits going key want is give your bit bitcoins he secure because holes I think maybe tens of thousands of euros in the worst case the and secure means 2 things are the 1st thing is the nobody can ever like compromise your secrets so your secret has to be secrets and the other thing is you don't want to lose your secret because losing a secret also means losing your money and this straightforward way to back up your keys is to give 1 or a few keys to your bank and you start on a piece of paper over there or do you take somebody you really trust like is possibly allows a lawyer you give to that but then you have this single a single point of failure and a single point of serial killer is 1 way that stuff can easily go wrong so instead of giving it to 1 person we don't really want to give to 1 person because 1 entity may break and is maybe like our house burning down because that's the piece of paper will start at the lower sinking and now it's gone through to so instead we really ones do split up I our trust into little pieces and every piece you want to give to some entity or some person that we trust to keep it secure forest item secret sharing solstice but 1st let me take some easy examples to the like how would we do it is in a simple realm straightforward way the and a 1st idea was just to be OK we have a King of maybe say 30 characters are and we just take the 1st n characters and then the 2nd don't than at the 10th and we get the 1st down to a single person and the 2nd 10 we give to another person etc. the have but in the case of cryptographic keys so in the case of Bitcoin wall of keys and stuff then if you've got the 1st 2 it's quite easy to brute force the key to get the last 1 so this is not really secure a more theoretical more secure approach would be to be the that would be to use some kind of a 1 time pad construction the the onetime pad construction is where you generate a random key and then this key will actually be used to be creates a secret and in our case we can take it generates do shares this all columns I shares a and B and a and B are randomly generated and our enemy jet it's a and B we use to generate another share C and we generate 2 things by using the actual combination of M a and b where n is the secret and then to reconstruct the secrets the we can uh computes the x or a combination of a b and c and we can see what is works because the equals M a and B and because 2 x forces cancel each other those assemblies can switch over and and we get em back the material we only sold this single point of failure problem in the case of confidentiality we only know that if we do this then the secret will remain secure that's this not does not solve losing 1 of the shares and in our case if it is backing up uh your secret of losing your secrets and is still problem then this not doesn't solve anything so we want something better and we have something better and we have something better for about 40 years now so secret sharing was published by Shimea almost 40 years ago and it's college rational scheme and a tertial scheme implies that and we can share a number of shares from a secrets and in the parameters of our scheme we can set the number of shares that is required to restore the original secrets so we don't need all the secrets of the we don't need all the shares to restore a secret we can just will say distributed vise chairs and then only 3 of them will restore original secrets and losing 1 0 2 shares isn't really a big problem for us also this scheme is provably secure of will be secure is often used as a term up I don't really like the stomach is good you say anything so I use the term informationtheoretically secure which is quite better the informationtheoretically secure means that if you don't have enough shares in this case then you won't be able to restore the secrets the and this is not like where the key is a node awaken brute force a key you can try every key but the key space is so large it is impossible to do this so in this case the even with a limited power and millions of years of computing power we still will never be able to reconstruct then the secrets the the anything so this implies also business resistant against quantum computers because extra computation power does not and give us an advantage there so here is an
10:32
example let's say I've got my secret message the my secret key uh m and I want to distribute this EM among my friends so that's the only after she hasn't cannot do anything but I would still be able to recomputes my original secrets if at any time I lose my secret so I distributes final PCs like by just computing that and on each of my friends as a share I might look to my share sometime in the future the ions questions back and even even if some of them while in our case 1 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 the beginning the I sets the treshold value to 4 so in this case for has enough to restore my secrets I use is for us as I recompute my secrets I get back to my message and the so obviously it is easy to
11:44
understand when you see this so that's going to the matter and matters quite fun and this is the like notation quite difficult to understand that's I'll tell you anyway so for a f a treshold scheme of what we want to would've the but like distributed and shares and the thresholds of recombining to the original secrets escaped the then we construct a random polynomial of degree k minus 1 so a times x to the power k minus 1 up till the lows coefficients but instead of filling in the lowest coefficients as a random value we fill in the lowest coefficient is a secret message so this simplifies to just using a number of then they've got this polynomial p and we start generating points of this polynomial so for x equals 1 x equals to x equal free et seq track till and the now we distribute these points as the shares and redistributors points up so that In the end we can use is poised to reconstruct the secrets and in our case so when we got this polynomial when we get all the go visions of this polynomial we also have the lowest coefficients so we do have an so we take these points and we can make a system of equations just like back in linear algebra 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 that we can actually find original polynomial I will do this so in practice we use a set of all Haskell Lagrange interpolation which you can the go all about Wikipedia that's this is easier to explain so all expected by using this so this may be a bit hard to understand talk at pictures we 1st we take
13:53
what you do is a secret message obviously then we generate a random polynomial in our case Our 1st coefficients is for and our 2nd coefficient is minus 25 so you've got this Nice parable we can construct points on this part about now the so that's really that like in our case for points and we sigh here um tree coefficients so treshold free important the at we see that if you only have 2 points and to reconstruct the secret the only can think the thing you can do it's all you can generate a align they'll they'll get some random value on the lowest coefficients and well this does not give vectors secret only if you take it to that point they can make this parable laughter you can then x equals 0 acre back your secret message the the so solving the system of equations we
14:59
is like filling in these x and y values it then you can consult is on a piece of paper and it is within I think 5 minutes and then you will get your message back which is 42 that so this is all good well we know this thing is the informationtheoretic secure so nothing could go wrong well but well yet again so this thing is the informationtheoretically secure for confidentiality which means if a secret its secrets it will remain secrets but nobody said you couldn't change the secrets so what we all want to do is to hack is we just but can share as part of his presence I will tamper with the shaft which we make another share which looks like the originals yeah but actually and constructs to a different secrets
15:58
lookingglasses here is a polynomial of degree 2 degree 1 and so this is just lines take 2 points if I generate another points the the the now we generate a new line to this point by me giving back a malicious secrets or malicious share then we get a new points which is not original points and if I have enough information about the original secrets revival of an information about the x values of the of shares that I can actually choose this point the so how to solve this well does 2 things to solving this and I'll come back to this later the 1st thing is I knew that the other points that was shared was on x equals to so this gives me information about how I can make this specific slope to get a new value and
16:56
the other thing is I knew something about the original secrets as his secret sharing assumes that the secret the secret well because it secret sharing but does not may not be the case in every dive of so I knew something about the original secrets so a solution would be to randomize this secrets and that well you might say but then you can secret share anything anymore the I'll get back to this so as part due is but and you can the the the the the so this was my introduction now get to the implementation part and this is where most normal cryptographers stop talking because they say we've got this beautiful schemes it works we know how to use it and now it's done like implementations magic implementation is easy and as a cryptographic engineer I would like to make the point to you don't cryptographic engineering is not always the most easy part of this process so of the the story is a bit marketing company in Taiwan ask those hey we want library for some secret sharing any library and then we ask how do you want jelly 1 secure and we want to be able to use it anywhere on any platform like androids Iowa's maybe microcontroller somewhere in the distant future and so OK we think 1 libraries are dead sort of as as as and gesture which are the most popular libraries and ends we looked at the codes and we needed to go that was really really secure and also secure again site a resistance and this codes I I didn't really portable well to other platforms or it had some guess your timing at the false that in our case wasn't rentfree exact acceptable so does that does not mean that these libraries of bats just good good good libraries only for our requirements this did didn't fit for so you yeah we're going to implement
19:23
this thing cells and I'll take 4 challenges that I've had with my implementation to and these are not the only 4 challenges that I had so there are a lot more challenges let's I think these are the best of still explain cryptographic implementation challenges to so the 1st thing is this integrity problem which we saw on the last slide from there from the previous part and how to encode our values because we were only using just values and like bytes or integers and will have to choose something to compute and other prevents Eichel attacks all explain how society an altered work and how to make this thing fast In the end because I like really fast go the the and I'd like really challenging optimization problems of an so the 1st part this
20:27
integrity problem we could either randomized these x values or the secrets is x values are not really easy to randomize because we we we would need to choose a really big x values and are cases really slows down a computation any it's that the security decreases with the number of shares that we give out so instead we chose a which is randomized the stuff that goes in the algorithm they've got a really random polynomial and nobody can use anything so we use the term which we which is call hybrid encryption so instead of using our message and willing it's directly true this should a secret sharing algorithms we instead we generate a randomized key this thing we can pull through hedonistic assuring algorithm and we used a ski to credits are secret message the end so in this case we don't have to bold texts do drew an algorithm which is actually used for well numbers and stuff and more more the weekend pull this thing through an algorithm which is used for randomized members so and this is how it works regret the secret but remember ski and we wanted the decrepit it's we just take the key shares and so the shares of the keys we get a key back by recombining the original key and now we used this key to D crypts the original side effects the this way we will get back the secrets the so the 2nd challenge how to
22:19
encode our values this may be a little bit hard to understand why this is a problem for people that I don't know really dead dead there the finite field arithmetic stuff but it essentially boils down to this In the beginning we had his numbers and when we're working in computers we cannot use to use any numbers because where limited to a restricted to using like integers assigned integers or bytes or etc. so in our case we want to take a the a and I structure a mathematical structure in which we can compute these numbers and we want to take our original like this key and we want to map its a disk structure to the mathematical structure and the most common thing that we do in if we take a really large private and we take his prime and we computed modulo dis primes and his words really well for spot so we actually have to have a prime order or a large water and in our case is not a requirements so we will map to a structure that's that has exactly 256 elements so when we have a structure maps let that has exactly 256 elements then we can map at bytes do 1 of these numbers and for the mathematicians the following things is what we use the we use a Finite Fields reduced but the rhinal polynomial M. and we'll see later on that this this allows us to do a really really powerful optimization trick and it boils down to the fact that's what we have every bytes separately key there we can just implements our algorithm for 1 bites and then we just but a force you parameters and for each bytes will secret sharing and this allows us to paralyze over these bytes and the later I'll show how we do it is at 1st 1st thing rules of cryptographic implementation in software so sigh texts are attacks that are not um attacks on the output of an algorithm so let's say I put something in the algorithm I see what kind of output it delivers and then I'll know if the our and that's something I did not something something i jails are met little that muscle 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 and if we note that a key contains a 1 at a certain position and then it will take a longer time to compute that we can measure the algorithms the computation and if it takes a long time the was no as 1 the and it takes a shorter time there will of elod it is probably 0 I We Canada's a eta iteratively and it is number of times and we can like take out just a big Statistics Toolbox a loads of statistics on this and it's sometimes really easy to pyknogram so the 1st rule offsite gel resistance is we may never branch In algorithms so branching is have execution path you choose where to go next so if statements are forbidden the L. statements forbidden logical and logical or are forbidden switch statement are forbidden etc. the to so the 2nd 1 it's is similar to the first one but uses sect userspecific trick and its call the catch timing attack so we use the fact that's if we take something for memory the timing may be different when it's when a speeds of dates act but a piece of memory is already in 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 a really big that's part of it is because of this and the last 1 is something that's often forgotten we're not allowed to use of arrival time instructions from the CPU and so on Intel processors for example the divisions instructions is often variable time the but also if you look at the manuals of SOM may be older uh CPU's in new also see that some of the instructions for example the multiplication may actually be at invertible 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 highlevel language like C Y any how do we do it is fast and this we do true bit slicing a bit
27:52
slicing is a really awesome technique the so we have all these bytes and we share by separately of so what we can do is we can paralyze of these bytes the and remember it's a CPU a CPU is made up only of logical instructions right so we would be able to smoke to multiply and add using only see logical instruction tracks so what we do is we take these bytes the we take the 1st bits of every bytes how we put it in a register I will take the 2nd bits of every bytes and will put in in the lower register in the lower register the and for every bits In these bytes we will put it in a separate register and in the end we will have used 8 different registers the
28:51
so now we'll implements this algorithm in cell using normal operators like I don't know division multiplication as set trap we will implement this thing using only logical bitwise operators so only really bitwise and bit less is on and it was on and remember it like this is a full adder 4 2 bits and this is just a really small part of how was CPU X 2 numbers and this is an example of how we could do this so will make this whole thing insights these kind of circuits and we'll have to finish this computation In our case we were building a 32 bit footpath form so we could easily run on all are devices and in this case we have a really large more bulky computation but we also have a parallelism vector of 32 end well this was a 32 bit upon form if we use a 64 bit platform we will get 64 it parallelism the and on even on a VAX to an ABX and this works and even if the CPU wouldn't clock down this would have worked in AVX 512 the
30:19
so any answer we've got is overview of how we implements a share such an algorithm so we take is really a random thing this by weight is 1 of these all the challenges that I'd did not talk about and we generate a random key we encrypts With this key secret message and then at and then we take this key every bitslice it's so that we actually so the again 10 computes are a secret shares that in parallel the and then when we're done with this computation we actually have to include besides operation and we get the shares restoring the original secrets is just the other way around we take our shares we bitslices our shared values the we executes the recombination algorithm using this these Lagrange interpolation formula so we have to embody the lies operation the answer and we use to ski too decrepit and verify the original cyphertext
31:42
so the performance of the thing is quite good I think well this is a kind of bad that benchmarks because I did not make and that's uh like proper and but well I made is that this presentation that some benchmarks not really accurate and so tight CUP they've done microseconds at centrality all things also take them like 2nd I have no clue wider bindings actually are better then the other ones if any was able to tell me please do so of but in the end roughly 100 thousand calls per 2nd and this is plenty performance we don't really need to get more performance but if we do and well I noticed that's about more than half of the time it's in the encryption algorithm not Soviet secret sharing so to optimize this further we made just use a better encryption implementation that's an artery case we use tweets at which solves a really security really good implementation which is really portable but is not optimized for performance so in the end stuff
33:02
that could have gone wrong the 1st thing is that well this is something that's we yes cryptographers off see on for example stack overflow that people think that's encrypting a secrets will make it secure against integrity the ever sequencing crap that's people don't know how to change its to gets another value but in the case of cryptography this is not the case people integrity is only assumes if you have a mass is out of the cation goats or in our case using in authenticated encryption scheme right and other the 2nd thing of could gone wrong is diving attacks and timing index is stop that actually exists in a lot of implementations and so it is gives me the impression that's the amount of cryptography engineers in this world maybe a little bit too small because otherwise we do we wouldn't that have had um both in time crypto implementations for example in the ghost in the library which I think we may not have or so we wouldn't have timing in the crypts which was published recently In the I've made a force be with you paper the so this is kind of a problem and this last problem that's and in this case it was an armory and armory is a highsecurity Bitcoin Wallet system and armory heads this should be a secret sharing implemented and they did not generate a polynomial fully randomly and I think this led to act actually let's to quite bad 3rd abilities in their implementation so it's kind of dangerous terrain don't to implement this cryptographic codes but is a sidetrack this is something that most programmers so not limited to cryptographers most programmers do not think about the existence of dark goes as a tool for everybody do well do whatever they wanted and I think is important to ask ourselves we have both the software what does this software how is the software meant to be used and it was this cannot be used for people with malicious intent for people who don't actually want to play by the rules it the and I'm telling you this because I think that most programmers will actually have to think a bit more about this sometimes so In our case we distribute secrets to a masses and we distributes secrets to trust trust the people and stuff so I do not really think that's the malicious user is able to and Due to use this for many measures brought purposes does power is most of the time centralized centralized and this tool most of the time allows us only to decentralize is power but in that in most important thing is that we are responsible for writing their own software and when I'm making a cryptographic library or if I'm making testing go Volkswagen we then we are responsible for stuff that happens with so the go back I'll show you a small demo the this will obviously go wrong
37:04
so I have installed my secret sharing tool the thank you yeah but tried to so that carriers
37:19
plus no we cannot use plus how we can use both other we but this is
37:32
but
37:37
let's make a sound this makers 5
37:41
secrets we're restoration thresholds
37:44
before who had but my secret well I'm the Hey the bad and over here thank you it the it but
38:11
hey and so we've got a couple of secret
38:17
here 3 is the 3rd 1 local copy
38:20
basis into my into my room restoration scripts so we start with that so all all ditch
38:28
the first one I'll take the 2nd 1 up to the first one to you can actually see what happens
38:34
when we ditch 1 of those it can
38:41
and the In the thank you yes then will also move but it so that it begins dog I said to you know not implementer of crypto and well I hope that you may have seen a couple of reasons and have like I've given you quite a bit of feeling about why implementing crypto is hot of and sulfate to please do implement crypto try to implement the tied to understand how the crypto works but if you're not really sure if you of 110 % here about what you're implementation does and if you're implementation is secure against every attack factor if it's I don't know maybe cited a resistance or checking that single carry bits In this single flag register then put the big warning in boldface letters at the top of your read me saying Hey guys this academic codes I this go to learn myself how good to have additional words that are not really share an object is would any that the 1st please do not use this for your really high secure well all of software or whatever and so that fits these are some people I would like to thank Hey an of my slides
40:33
can be among website that can be fun of my websites I've got some extra reading for you if you'd like to some I I forgot to register my deck text engine this . 1 does not work and so that sits you have any
40:50
questions the consequently this
40:53
thing here which thank you thank you any questions please feel free to assemble behind the microphones and I will you through than that our number 3 how do you make sure you didn't make an implementation mistake to have unit test long so further that's the that's the terrible thing is that in a cryptographic implementation world like to have unit test unit tests do not always fix your problem Europe's space is large enough that you won't be able to test everything and In the case of my that elliptic curves implementations the only thing I can try to do is prove every single function and that's really errorprone and can also be doing wrong that's mean honestly not 100 % here about the fact that my implementation does not contain and any errors I checked people objected for me is I'm well quite sure but I still and not this 100 % share and I think this is a lot with all goats that the security got security relevant and I feel microphone number for trees 1st of all thank you for the interesting talk 1 technical questions OMB as a formidable that the center of the actual number of shares of quite a lot of an original text from and my question is how are those of the sum of the number of and for the number of bytes information scale with the number of shares that haven't with the number of this you require cheers but so I'll get back
43:01
to the slides ever I the uh what we do here is we have this encryption key and we have this point is x value so we have to add 1 single value for x 0 1 bytes because through working bytes and this is the 1 that due to 3 and this will be the 1st 2 bytes of share so this as 1 might and that will take this key and the key has to be randomly generated and this key in our case we use salsa 20 as an encryption algorithm which uses of to 456 bits the which is 32 bytes and this adds another at the 2 bytes so in the end we only have 30 3 bytes which are actually to our shares and that's like the amount of shares that regenerates and the thresholds will always generates the same among the bytes in the shares and actually from the share the load you cannot see what the threshold of the algorithm was in the 1st place this is another question we have a question from our ROC church yes 1st of all and guileless this setting which thank you for losing latish so much as for what this is there's a big discussion the IIsi see how to defend against social engineering what is some of the shareholders evilly plot against you and so are there any ideas to remedy this issue we have that's a good question I that's the thing that ironsulfur myself because I don't have every person's environment and so my own recommended stuff in my reading and stuff if generate 5 shares of war shuffle prefer to original secrets but even this I'm not aware of it is secure in your case you have to yeah well you have to choose yourselves you trust with your shares so I can't really answer this question volume OK my phone number 2 a question about the integrity problem and how exactly does Europe hybrids um encryption engines solve this problem and swaps does your tool if you put in some tempered secret not yeah that's a good question so m so
45:35
here we actually could spoil the secret because the original secrets whilst some value that we knew and and what this does is it a randomizes the value that's come out of any temperature secrets so if we if we that would share we change even 1 bits then the value that will come out all of the secrets will be fully random and because the original thing was fully random so and what are the algorithm will do is in the salsa 20 41 305 authenticated encryption the correction step and this will actually feel only other application Derek of the cyphertext and it was a recombination fields otherwise the key or cyphertext was a valid and we just jet say no this won't work my want please hello and and is similar to a previous question probably but I mean assuming I'm trying to protect my huge Bitcoin wallet I mean that is and I don't wanna really fully trust anyone and I would be an option to so I would like to avoid that is free of my you family components agree with the charter based in my wallet basically is an option to double up the shares and they keep 50 per cent of it yet but you also have the larger problem of and of that losing the shares actually it may be a risk for you so and that's the trade off here so there's lot like let me tell you a small anecdotes of which you can use this also is for example if you better bit what bitcoin wallets and you want your relatives to be able to inherit your wealth if you die then you may choose to uh distribute your shares among of family members and people and so that after you die you can actually tell me how it that you're allowed to reconstruct secrets and then you can inherit might it's going well and and there's also an application for this but in your case well if you have but if you have a system where you have yourself most of the shares then In this case you always have the the facts that's have that if you you lose those shares then you also maybe use a secret which in your case may be which 1 I'll see please and Dodik is asking if your separating them separating the message into individual bytes and then applying as for each part separately doesn't suffer from the similar problems as the electron codebook Morton stream cyphers namely that data patterns are not hidden yes so that's also why we use this as a hybrid encryption scheme and so this hybrid incursions scheme encryption works on the whole block on the whole message ends distribu secret sharing works on the eventual bytes and there's no better in there because we generated this secret key 20 randomly the a microphone free please well I come from a few would we choose quite similar in the way to use a problems that you have consider here which our error correction codes and I well in my feuds there are alot of error correction cause inferences Arie's is a low density parity check codes which in can be from my point of view of course In the wake facts to make a scene there are implementations at and you can see the rates also quotes so the idea and the reason that we actually use this was lost because of real security stuff but because of the source of 20 provide and the recommendation was already there and if I would do this in a more sophisticated way of choosing which area is not the only treshold scheme that X is there so we all also got along the what verifiable secret sharing and we also have some Peterson verifiable secret sharing and is actually secret sharing that's the solve the integrity problem but they are a little bit more complex and so that's probably what I would have used to the high and great talk um and back to implementations did you go a bit into do relationship between optimizations both from compilers and just what we as programmers tend to do our cells and vulnerabilities in their 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 goats but when I do something in my C goes then I mean it's yes and no I do not states so that C compiler developers but I choose to program in C. and really really low level stuff I actually program in assembly so the that well they do not have this obligation to cater to us as the depreciation there's so yeah what can I say maybe it's nice to have a lot of well you could say to the compiler yes I really really want to use these these things in a way and please do not assume that because this stuff in memory is not a rat after this line that you do not have to really be initialized to 0 because I really wanted want to set this key value to 0 at the end and so yeah well there are tricks in composite you can exploits and this is mostly the way we do it when we actually needs to really delicate compiler yes we want to do is this way and most of the time Peter I we look at the assembly code that rules out of it and we think OK well they didn't have and the and now it's it's it's OK and if it's really really critical that we implemented in assembly so so what would you what would be your advice to
52:29
you basically told people to implement a of proto and I since we have not enough cryptographic engineers as a good advice what would you tell them to check for How to see if there's going to be a timing problem so yeah that we you know you can always look at the assembly codes and see if there's stuff well so the 1st 2 items that I showed you this branch and these do not look up well compilers won't do is wrong if you don't put in a statement there they won't actually introduce a branch and also most of the time they won't change and instruction wall like a bitwise instruction they wanting changes to a multiplication ITER so if you have these kinds of really simple instructions as actually actually well not be that big a deal um and another thing is so this is maybe not really good for me to say but well there are a lot of not really good implementations out there as well as your 1 is better than the others that this is because it's good right the microphone number for these fine so what you the dome of the threshold and the share what the the the real family application moreorless shares some of it expects was trying to solve the problem nominal often wrongly really on so if the so if we have less then the required amount of shares then I will reconstruct the pathway no meal and it will try to use the lowest coefficient of this that polynomial too decrepit our secrets and this will fail so if we have I too many shares and then the uh then the solving of the equations will actually just work so more shares will not have um be a bad that thing there's only 1 problem which is a few add topic it shares then it will fill with the same that with the 1st ever I and that's 1 thing that I did not solved yet uh in a in a grouped manner the number 3 hiding to foder told how close is your code to be used in production so living of how well how much do you you go to and and stuff this thing kernel the really needed I'll I'll say the these through the beam production so that's a really dangers question because and I say it's super safe and people use them and make the other the was say and then all like it's final I well note so the effort said it was up I'd made its and I checked letter as jects but it by putting them uh so but like having checked by all the operative every engineers and having my method texts by older group of engineers and and the cost c codes I expect there won't be any problems there's also the way we do is Nisbet slice slice of operations using only bitwise operations it's quite easy to do this correctly thank you it and go ahead thank him how you're talking about optimizations and I was thinking that instead of making 1 very large prime to use as a mode low for a finite field think a prime which is just slightly bigger than your secrets is this implementable the use of variable prime yes sir but modulo deductions are tricky in a in In our constant time and uh implementations of Don so when we do marginal reductions in the elliptic curve at cryptography we muscle time we do with this kind of a conditional subtraction and this comfort collisions suppression will be done but when only when when numbers larger than a prime or if there is the number of overflows or in the froze the during a subtraction and this can be quite easily done in the in software because we have we we can just do his bingo sometimes but this becomes a lot harder not only when our prime is and but when our prime is notes chosen acts like the time when we built a software that's also when this prime is not really regular so that's why there's is prime which is called 200 of the due to the power 255 minds 19 it's a really popular prime to implement have to left because it's really easy to reduce because any number of of debts we can carry its to the lowest level and multiply by 19 and but if we do not have a really a regular prime then this problem becomes actually really hot and we would have to use another position library which are often not um site or resistance right you number 2 things on the way I understand this rate on the security of the whole thing depends on on the integrity and security of the machine it's been computed on is there any way to distribute the computation of mission your secret sharing of music which I no direct and I think that's terror casual schemes yes where are you that way you compute still we can compute the sting separate the on separate computers but initially secret sharing case we assume that the dealers computer so the person we could get such as is actually trust that's bad because it also holds the secrets so if we just a computer all the secret and will also trusted to compute shares yes no any further questions no so then please Walpole's abounds bagels thank thank some to watch
59:21
and and so on and uh and uh the effect the kind of 2 at top to
00:00
Dienst <Informatik>
Folge <Mathematik>
Bit
Task
Punkt
Algorithmus
Implementierung
SecretSharing
Grundraum
01:27
Cybersex
Einfügungsdämpfung
Computersicherheit
Kryptologie
Implementierung
SecretSharing
Nummerung
Datenfeld
Kryptologie
Fahne <Mathematik>
tTest
Mereologie
Computersicherheit
Wiederherstellung <Informatik>
Informatik
Elliptische Kurve
03:51
Bit
Mereologie
Punkt
Schaltnetz
SecretSharing
Implementierung
Befehl <Informatik>
NPhartes Problem
Information
Nummerung
Datensicherung
Term
Gerichteter Graph
RaumZeit
Eins
Mooresches Gesetz
MessagePassing
Font
Konsistenz <Informatik>
Distributionenraum
Nummernsystem
Computersicherheit
Programmbibliothek
Inverser Limes
Schwellwertverfahren
Passwort
Implementierung
Graphiktablett
Leistung <Physik>
Konstruktor <Informatik>
Parametersystem
Wald <Graphentheorie>
Assembler
Zehn
Computersicherheit
Abstraktionsebene
Kryptologie
Quantencomputer
Einfache Genauigkeit
Nummerung
Arithmetisches Mittel
Forcing
Physikalische Theorie
Rationale Zahl
Mereologie
Serielle Schnittstelle
Schlüsselverwaltung
10:30
Bit
Punkt
LagrangeMultiplikator
Polynom
Gleichungssystem
Zahlensystem
MessagePassing
Koeffizient
Nummernsystem
Randomisierung
Programmbibliothek
Lineare Geometrie
Punkt
Maschinelles Sehen
Leistung <Physik>
Schwellwertverfahren
Mathematisierung
Nummerung
Physikalisches System
Polynom
Minimalgrad
Menge
Interpolation
Koeffizient
Parametersystem
Interpolation
MessagePassing
13:48
Netzwerktopologie
Polynom
Punkt
Konsistenz <Informatik>
Koeffizient
Mereologie
Programmbibliothek
Gleichungssystem
Physikalisches System
Vektorraum
MessagePassing
15:58
Web Site
Bit
Punkt
Prozess <Physik>
Mereologie
SecretSharing
Implementierung
Systemplattform
Kryptologie
Konsistenz <Informatik>
Nummernsystem
Programmbibliothek
Gerade
Implementierung
Caching
Randomisierung
Systemplattform
Humanoider Roboter
QuickSort
Polynom
Minimalgrad
Mereologie
Codierung
Information
Programmbibliothek
Fitnessfunktion
19:20
Implementierung
Zellularer Automat
SecretSharing
Computerunterstütztes Verfahren
Term
Chiffrierung
Zufallszahlen
Algorithmus
Kryptologie
Konsistenz <Informatik>
Nummernsystem
Randomisierung
Programmbibliothek
Hybridrechner
Implementierung
Soundverarbeitung
Computersicherheit
Optimierungsproblem
Systemaufruf
Integral
Rechenschieber
Polynom
Chiffrierung
Ganze Zahl
Mereologie
Schlüsselverwaltung
MessagePassing
22:17
Bit
Konfiguration <Informatik>
Punkt
Primideal
Ortsoperator
Hyperbelverfahren
Minimierung
SecretSharing
Implementierung
Element <Mathematik>
Computerunterstütztes Verfahren
Zentraleinheit
Division
Festplattenlaufwerk
Multiplikation
Algorithmus
Kryptologie
Software
Restklasse
Nummernsystem
GaloisFeld
Coprozessor
Datenstruktur
Struktur <Mathematik>
Hardware
Leistung <Physik>
Funktion <Mathematik>
Statistik
Befehl <Informatik>
Kategorie <Mathematik>
Mathematisierung
Systemaufruf
Schlussregel
Primideal
Modul
Schlussregel
Mapping <Computergraphik>
Höhere Programmiersprache
Software
Forcing
Last
Ganze Zahl
Festspeicher
Mathematikerin
Mereologie
Wort <Informatik>
Ordnung <Mathematik>
Schlüsselverwaltung
28:50
Bit
Mathematische Logik
Gewicht <Mathematik>
LagrangeMultiplikator
Polynom
Chiffre
SecretSharing
Zellularer Automat
Subnormaler Operator
Computerunterstütztes Verfahren
Zentraleinheit
Systemplattform
Mathematische Logik
Division
Chiffrierung
Weg <Topologie>
Bildschirmmaske
Multiplikation
Algorithmus
Maßstab
Nummernsystem
Programmbibliothek
Parallele Schnittstelle
Parallele Schnittstelle
MetaTag
Implementierung
Algorithmus
Nichtlinearer Operator
Logische Schaltung
Systemplattform
Vektorraum
Interpolation
Mereologie
Digitaltechnik
Interpolation
Schlüsselverwaltung
LieGruppe
MessagePassing
31:39
Zentralisator
Demo <Programm>
Bit
Programmiergerät
Hintertür <Informatik>
Implementierung
SecretSharing
Kombinatorische Gruppentheorie
Eins
Konsistenz <Informatik>
Software
Kryptologie
Programmbibliothek
Einflussgröße
Implementierung
Benchmark
SchreibLeseKopf
Leistung <Physik>
Softwaretest
Schnelltaste
Computersicherheit
Ruhmasse
Nummerung
Schlussregel
Physikalisches System
Systemaufruf
Integral
Software
Chiffrierung
Schnelltaste
Twitter <Softwareplattform>
Loop
Rechter Winkel
Automatische Indexierung
Pufferüberlauf
Codierung
Authentifikation
NotebookComputer
36:57
Schwellwertverfahren
Konfiguration <Informatik>
Freier Ladungsträger
EinAusgabe
Zählen
SecretSharing
Schwellwertverfahren
Programmbibliothek
Information
Hochdruck
Versionsverwaltung
37:42
Konfiguration <Informatik>
EinAusgabe
Basisvektor
Zählen
Skript <Programm>
Schwellwertverfahren
Programmbibliothek
Atomarität <Informatik>
38:33
Sichtbarkeitsverfahren
Bit
Kryptologie
Einfache Genauigkeit
Implementierung
Teilbarkeit
Rechenschieber
Objekt <Kategorie>
Software
Kryptologie
Fahne <Mathematik>
Codierung
Wort <Informatik>
Implementierung
Lesen <Datenverarbeitung>
40:28
Web Site
Gewichtete Summe
Komponententest
Programmverifikation
Implementierung
Content <Internet>
Maßerweiterung
EMail
RaumZeit
Netzwerktopologie
Digitalsignal
Kryptologie
Nummernsystem
Programmbibliothek
Rechenschieber
PetersenGraph
Elliptische Kurve
Nummernsystem
Zentrische Streckung
Lineares Funktional
Architektur <Informatik>
Computersicherheit
Kryptologie
Einfache Genauigkeit
Information
Fehlermeldung
Lesen <Datenverarbeitung>
42:59
Programmiergerät
Bit
Punkt
Polynom
Freeware
Inferenz <Künstliche Intelligenz>
Compiler
Minimierung
Social Engineering <Sicherheit>
Chiffre
Familie <Mathematik>
Kartesische Koordinaten
Übergang
Streaming <Kommunikationstechnik>
Algorithmus
Nummernsystem
Mustersprache
Randomisierung
Vorwärtsfehlerkorrektur
Gerade
Schwellwertverfahren
Sichtenkonzept
Assembler
Physikalischer Effekt
Computersicherheit
Güte der Anpassung
Nummerung
pBlock
Quellcode
Bitrate
Exploit
Konfiguration <Informatik>
Rechenschieber
Datenfeld
Chiffrierung
Menge
Festspeicher
LowDensityParityCheckCode
Programmierumgebung
Schlüsselverwaltung
MessagePassing
Lesen <Datenverarbeitung>
Aggregatzustand
Codebuch
Telekommunikation
Implementierung
Zellularer Automat
ROCKurve
SecretSharing
Demoszene <Programmierung>
Chiffrierung
Reelle Zahl
Programmbibliothek
Zusammenhängender Graph
Spezifisches Volumen
Hybridrechner
Optimierung
Softwareentwickler
Fehlererkennungscode
Relativitätstheorie
Programmverifikation
Physikalisches System
Integral
Flächeninhalt
Softwareschwachstelle
Last
Mereologie
52:27
Subtraktion
Web Site
Ortsoperator
Minimierung
Compiler
Stoß
Mathematisierung
Program Slicing
Gruppenkeim
Familie <Mathematik>
SecretSharing
Implementierung
Kartesische Koordinaten
Gleichungssystem
Computerunterstütztes Verfahren
Computer
Kernel <Informatik>
Virtuelle Maschine
Variable
Multiplikation
Software
Kryptologie
Reelle Zahl
Gruppe <Mathematik>
Nummernsystem
Vererbungshierarchie
Programmbibliothek
GaloisFeld
Elliptische Kurve
Leistung <Physik>
Nichtlinearer Operator
Befehl <Informatik>
Schwellwertverfahren
Assembler
Computersicherheit
Güte der Anpassung
Verzweigendes Programm
Biprodukt
Bitrate
Ordnungsreduktion
Integral
Rechter Winkel
Pufferüberlauf
Koeffizient
Codierung
59:21
Soundverarbeitung
Hypermedia
Medianwert
Systemprogrammierung
Metadaten
Formale Metadaten
Titel  We should share our secrets 
Untertitel  Shamir secret sharing: How it works and how to implement it 
Serientitel  34th Chaos Communication Congress 
Autor 
Sprenkels, Daan

Lizenz 
CCNamensnennung 4.0 International: Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen. 
DOI  10.5446/34800 
Herausgeber  Chaos Computer Club e.V. 
Erscheinungsjahr  2017 
Sprache  Englisch 
Inhaltliche Metadaten
Fachgebiet  Informatik 
Abstract  Backing up private keys in a secure manner is not straightforward. Once a backup has been compromised you need to refresh all your key material. For example, the disclosure of a private key of a Bitcoin wallet gives access to the coins inside. This makes it unattractive to store a complete backup of your private key(s) with your bank or your spouse. The better option would be to split the key into multiple parts. The recommended way to do this securely is to use the Shamir secret sharing scheme. This talk provides a detailed breakdown of how the scheme works and explains how it is implemented in C in a new library called SSS. 
Schlagwörter  Security 