Dear viewer, these subtitles were generated by a machine via the service Trint and therefore are (very) buggy. If you are capable, please help us to create good quality subtitles: https://c3subtitles.de/talk/1082 Thanks!
[Music]
hey our next talk is going to take a
look at what you can do wrong if you're
using secure crypto Primitives but don't
use them the right way and what you can
possibly do about that by writing formal
proofs so to tell you more about that we
have Florian and Lucas a warm Round of
Applause
[Applause]
please so good morning and thank you for
waking up it's a great honor for us to
give this talk especially in the slot
directly after djb and Tanya langa
uh before we start I want to mention two
points which might not be clear in the
talk the first one is we like provable
security and AIT gold is a great
cryptographer and this talk should not
be a
rent the organization is as follows
we'll give a short motivation why you
want to
have proofs of
security and then we'll show how to do
them and the next uh the the latest two
points will be on strange stuff happens
if you use provable
security anyone from the most clueless
Amer to the best cryptographer can
create an algorithm that he himself
can't break it's not even hard this
quote by Bruce schneer shows a little
bit why you want to have provable
security just because you look on your
own scheme and you don't find the floor
it does not mean that it's not there and
a strict mathematical proof can handle
this
problem
but it's not that easy and you should be
aware of the boundaries of proof
systems I'm sure you know this
example the uh electronic code book mode
is an encryption scheme where you take
blocks of a plain text and you encrypt
each block on its own and uh it's it's
secure in the the meaning that uh each
block looks random compared to this uh
plain text but in the end that's maybe
not what you mean by a secure encryption
scheme
a more complex example is the CBC or
Cipher block chaining mode here you see
that you have uh blocks of Cipher text
and of PL
text and in the decryption step and I
use
my L um you use the cipher text from one
block
and exort it uh to the decryption of
another uh Cipher text block to get a PL
text and for a for a deeper insight into
this uh protocol you can watch the talk
on TLS 1.3 by Hano uh but we'll show
small problem of this um but before I
need to introduce so-called
oracles oracles are a way to formulate
that you have some protal party which
takes a well- defined input and answers
with a well- defined output and it's
typically used to perform operations
that the parties by themselves can't
handle and if you introduce a special
so-called petting Oracle to the to this
CBC mode which takes a cipher text and
answers you if the padding of the plane
text is correct which means that sorry
it
it ends with either a one b or two two
bytes or 3 three byes uh just entering
an oracle which tells you this
information is enough to break the
complete Cipher text because you now can
just guess uh one bite after another
which is much more efficient than
Breaking the complete Cipher in one shot
so to understand the security of a
system you need to understand
uh what problem you have and what
definition of security you want to have
and then you can go there and prove that
your system is
secure but
unfortunately you won't be able to prove
it without taking
assumptions you might know about the P
versus NP problem and that you can get
quite Rich by solving
it if you have a cipher
text
an encryption
scheme and you prove that it's secure in
the sense that given um encryption of
something you can't tell that this is an
encryption of a
zero and you can prove this without
taking additional assumptions then you
would have shown an example of a problem
which is in NP because given the secret
key it's easy to do this you uh decrypt
it and then you know if it's a zero or
not but it's hard to do without and then
you would have found an example uh where
p and NP is different uh which make you
quite rich and famous but it's not that
plausible that you find it just uh on
the way of proving the security of your
scheme so we have to do some assumptions
and uh Floren will now tell you about
some of these okay uh good morning
everyone
um now many of you may have seen RSA and
I've just um written down the uh a short
version of it on the slides uh let me
check here um it's quite commonly known
that you have two very big primes p and
Q you multiply them and get a very big
integer n and you also take some
exponent that we will just set to three
in this example and this is all you need
for a public key and then there is some
uh more complicated way to compute the
secret key and once you have these
values um encrypting uh stuff is as
simple as taking the Blaine text and
taking it to the power of E so in our
case three and doing that modulo n
modulo uh in case you don't remember if
you do division with remainder you throw
away quotient and keep the remainder and
that's what we call modulus so almost
all examples that we will show will have
some modulus in them um and in this case
encryption as you see it's not really
complicated and decryption uh you take
the secret key as the exponent and for
some uh reasons that we won't go into in
this talk this actually works out to
give you back the um original BL text
and there is this common misconception
that RSA is secure if factoring is
secure that's not really the case the
assumption that RSA uses is the
so-called RSA assumption and it is
roughly equivalent to the following it's
impractical um if you I give you a
public key and some Cipher text that was
created with the public key with a
random plane text for you to fully
extract that Blaine text it sounds a
little bit like RSA is secure because
RSA is secure and actually that's
getting quite close except that we have
the problem that this version of RSA is
not even really secure for sensible
security definitions because just being
unable to extract the Blaine text from a
cipher text doesn't mean that there are
no practical attacks on it if you're
only able to extract half the plain text
and you know that the it that it
contains um asy text that says either
yes or no and I give you the first bite
of it you can pretty much guess what's
the other bytes might
be and there are many other problems uh
with RSA in that shape for example if
you um want to encrypt uh small numbers
23 you take 23 to the power of three
modulo some really huge uh number 23 to
3 is
12,167 that's way way smaller than
though than n so you can simply throw
the cube cube root at it and you get the
BL text back that's an efficient
operation and one of the reasons why you
should naively use RSA U RSA now you
might say I'm not going to encrypt um my
plane text with RSA directly anyways I'm
going to use hybrid encryption where I
just encrypt a secret key for symmetric
scheme with RSA and then encrypt the
message with the symmetric scheme
because that's way more efficient and it
is indeed what you would usually do in
reality but think about it um let's be
generous and say you're using 256 uh key
bits for some secure version of
as and you're quite um daring and use
only 1,24 uh bits of RSA
key 256 * 3 is still a lot smaller than
uh 1,24 so this attack perfectly works
there and this means that you really
have to be careful with RSA and also
it's a deterministic scheme if you have
an idea what the Blaine text might be
you can simply encrypt it after all it's
a public key encryption scheme and check
if the result matches so the long story
short version here is using RSA is not
trivial there are secure versions of RSA
or versions that we believe to be secure
but they are a lot more complicated than
what you're usually shown and for
example none of them for none of them
the often claim case of encrypting uh
signing is encrypting with the secret
key doesn't work um that statement that
signing is encrypting with the secret
key is not to my knowledge true for any
secure scheme in either
direction now RSA is not the only thing
that has its
issues and um we will later look at
elgamal which is a very great encryption
scheme but even there if you don't pay
close attention you might end up leaking
plain text bits and a single PL text bit
can be disastrous in certain
circumstances imagine you're doing an
election and you encrypt your yes or no
vote if I learn one bit about the plain
text I learn everything and another
example where people uh often have wrong
ideas as with hashes yes it is true if
you take some um random input from a big
set and you throw it through a hash it's
impractical to learn a pre-image for the
hash but if the original set from which
you're play uh pre-image comes is small
you can simply brute force it and I've
heard this several times that where
people made this claim maybe they even
knew it but they didn't say so the
result is of course that you get
vulnerabilities
everywhere now we need so one of the
issues that we saw in RSA with this RSA
assumption was that we need some proper
definition of what security actually
means and a rather old notion that is
not without problems but is a good first
idea is called semantic security and
what you see on the slides is a
simplified version in the sense that it
uses regular language instead of very
comp complicated formulas but it gives
you the CH uh the gist of what the idea
is if I give you a public key and a
cipher text you should not be able to
learn anything about the contained PL
text except for its length if this is
true for an encryption scheme then we
consider that um scheme secure in the
sense that it provides semantic
security the issue with this is it's not
really that simple to prove that for
schemes even if you use proper
assumptions so there is another notion
and that is called in CPA that is sh for
indistinguishability under chosen Blain
text
attacks again this is the um colloquial
version of it but it boils down to if I
give you a public key and you are the
attacker and you are now allowed to
choose two plane texts can be anything
as long as they have the same length you
give both of them to me I pick a random
one I will encrypt it with the public
key and give you the cipher text you
should not be able to uh distinguish
which um plane text that you gave me I
encrypted better than just making random
guesses or at least substantially better
there's always the chance that you just
by pure chance guessed the secret key
correctly we don't worry about that but
anything that is substantially better
than guessing is a real issue and we uh
and the nice thing is at some point some
people went through uh the trouble of
proving that those two Notions are SEC
are equivalent and thus if you prove in
CPA security you have proven semantic
security but again semantic security is
just one definition of security and it
is not necessarily A sufficient one for
what you want we mentioned the CBC mode
in the beginning um where you could had
were able to fully decrypt some Blaine
text using a petting Oracle CBC mode
provide semantic security it's simply
that they attack this um the uh pading
Oracle is not part of the definition of
semantic security and thus the attack
happens outside of the security model so
it's it's really important that you
choose um a good and appropriate
security model I believe we have a
couple of more examples where this will
come up and a very notable one that we
won't talk about anymore in this talk
are site Channel attacks if you are
capable of learning The Secret Key by
just um looking at the network stream
and take a stopwatch the encryption
scheme can be as good as you want it
won't help you if that is the way you
get a key and and that's where why uh
implementing cryptography is so hard
because you have to um take care of all
these problems also just because a
scheme is secure on its own that doesn't
mean that this is secure if you combine
it with other schemes and finding a
proper definition of security can
sometimes be the hardest problem of all
in cryptography there are actually cases
where it's easier to come up with aure
solution to a problem than with a proper
definition of what sec cure
means now that being said let's look at
how we do the
proofs um we are doing so-called
reductions as Lucas already
explained we cannot do absolute proofs
that don't need assumptions because
there is this Millennium problem in the
way so we need some assumption for a
hard problem and this is usually defined
as some kind of game where you have a
Challenger in this case we call this the
Assumption Challenger
that gives us some kind of challenge for
example um The Challenge where he says
here is an RSA public here in a cipher
text give me the plain text and we then
have some kind of translator and we have
the um an attacker on our scheme that we
want to prove as secure so for example
um this might be an attacker on the ncpa
security of an encryption scheme and it
will take um again some kind of uh
public key and play uh some kind of
security game and the translator now has
the task to translate the challenge that
it received from the Assumption
Challenger into something that the um
attacker on the um scheme that we want
to prove as secure can use to attack
that scheme if it is capable of
attacking the scheme and then translate
the result of that attack back into
something that um the original
assumption Challenger would accept as a
break of the Assumption and since we
believe that there is no way to break
the Assumption and we demonstrated that
uh breaking our scheme uh breaks the
also implies an attack against the
Assumption we believe that is
Impractical to break uh our
scheme we will now look at a full
example where this will maybe get a
little bit more clear and for that we
will look at a encryption scheme called
elgamal which unlike RSA is secure out
of the box at least in a sense of
semantic
security again we start with two big
primes p and Q but this time they are
required to have a special property P
has to be twice Q + 1 so they are
closely related primes and we also call
P a safe Prime and Q a sopa mod Prime
and the reason of this these we won't go
into here um you also need to take some
something called a generator and we just
pick four because that always works if
you pick a bad generator this is
actually the case that I mentioned in
the beginning where you leak PL text
bits and we will now do several
operations of those we have some
operations between elements where we
multiply base elements those are all
modulo P so the lowercase here and we
have exponents in the game and those are
modular q and for reasons that you can
learn about in a group group Theory um
university lecture this makes actually
sense and for notational purposes the
set of all integers between zero and Q
minus one we will call set
Q now in order to use elgamal we need we
assume we have those integers P andq
they don't need to be secret or anything
they can even be standardized and
usually or very often they actually are
and the key generator will Now sample a
random exponent x from set q and this is
the secret key then um he or she will
take the generator G and compute G to
the power of X so again this is modulo p
so this number won't grow completely out
of proportion but um what um yeah the
result is the public key you already see
here um this operation this G to the x
is probably hard to reverse so you can't
undo this to get a signature scheme out
of this and that's everything you need
to do for key generation which is much
easier than finding two primes for
RSA encryption is a little bit more
complicated but also doable you pick
another random integer R this is your
encryption Randomness this avoids the
attack of um looking uh of trying to
encrypt some assumed BL text and
checking whether they match because
every time you script you use a
different value R and then you compute G
Tod R first this is your first part of
your Cipher text then you take the
public key G to the X and compute it to
the power of R and by the rules of uh
how Powers work G to the X to the r is
equal to G Tod x * R and that you
multiply simply with the pl text M those
two elements are now your complete
Cipher text and that is everything you
have to do for encryption and finally
decryption um you take the second part
of the um Cipher text here so this G to
the XR * m and the idea is now that you
remove this G to the XR and for that you
take the G Tod R and compute it to the
power of X and again rules of power G to
the r to the x is g to the RX and if you
now do this to the minus one you get G
to the minus RX G to the minus RX * G to
the RX is g to the RX minus RX this is g
to the Z which is 1 so it's you just
have the BL Tex left here and you're
done with the decryption and that's all
there is to the scheme so it's not
really that hard now we still need an
assumption relative to which we will
prove uh that algal is secure and for
that we will use the decisional defy
Helman
assumption it says that if you take
three random exponents it is not you're
not able you're not going to be able to
tell whether I give you a triple that
consists out of GTX G to the Y G to the
Z or of or a triple that consists of G
to the x g to the Y and G to the
XY um we won't argue why this is true
there is some good rational why we might
believe that but this is an assumption
so we don't have to prove it we just
have to assume it and then prove that
our scheme is secure if this assumption
holds
and for that we are going to use the uh
game structure that you just that I
showed you before that and this is the
full game so at the start you see the
ddh Challenger uh passes some triple to
the translator and at the end the
translator outputs a bit B that tells
the translator's Assumption whether set
in this case is equal to x * y so you
have this game on the left side on the
right side you have the in CPA game game
so you have in the start you give a
public key so for this you use ch2d x to
the elgamal attacker then the attacker
will hand out two uh possible plane
texts m0 and M1 and the translator now
selects one at random for that uh he
picks a random bit B and MB will from
now on be the selected plane
text you then take it then takes the
second part of the provided triple G2 Dy
and uses that in place of G Tod R so
that's the first part of the cipher text
and it takes G to the Z in place of G to
the RX so the second part of the cyer
text except for the plain text which we
let at afterwards so you see here this
has basically the structure of an algal
uh Cipher text and then you let the
attacker guess it can now do pretty much
what it wants as long as it doesn't run
uh extraordinarily long and at the end
it will output an assumption uh B Dash
about which BL text was encrypted the
translator then just checks whether the
assumption is correct and outputs the
bit whether it is correct to the
Challenger it might not be completely
obvious at this point why this is a
proof but let's consider the different
cases um let's say the attacker has a
success rate of 1/2 plus Epsilon 1/2 is
the uh probability that you would get by
just r guessing so if the attacker is
better than just random guessing there
has to be some additional so-called
adversarial Advantage Epsilon and we
just assume that it is
positive now if x * Y is equal to set
which is the case 50% of the time then
this is a perfect simulation of the uh
real uh ncpa game because the public key
G2 Rex is a completely random element so
perfectly IND distinguishable G to d y
perfect indistinguishably also random G
Tod Z is in that case by definition
equal to x g Tod x * y so again perfect
uh simulation and we simply get the um
success probability of the attacker in
that case and yeah so that's fine
otherwise however um g2d set is not in
any kind of correlation to uh G2x and G2
d y and as such it is also this plane
this Cipher text won't be in any
correlation uh with to either of the
Blaine texts with overwhelming
probability so it's only possible to get
a success rate of 1 half for the
attacker and since either of these have
a probability of of occurring of one2 we
simply compute the mean value of those
and that happens to be 1 12 plus Epsilon
half therefore if the there is an
attacker against the semantic security
or the ncpa security of elgamal we just
converted it into an attacker on the ddh
Assumption with success probability 1 12
plus Epsilon half if Epsilon is non-
negligible then the definition of
negligible implies that Epsilon half is
also non- negligible and since we
believe that there is no attacker on the
uh ddh assumption that has non-
negligible Advantage we conclude that
there also no attacker on the security
of the elgamal scheme that has um non-
negligible Advantage it follows that
elgamal is ncpa secure and thus provides
semantic security end of
proof now you might say yeah but what
did we gain of that we um replaced the
assumption that the encryption scheme is
secure with an assumption that is also
quite weird well first of all the
assumption is a little bit less complex
though in that that case the difference
is not that huge but this is an image of
the old version of the TLs handshake as
you see you probably see nothing because
it is too complicated to properly fit on
the slide which is the entire point I'm
trying to make here these kinds of
proofs allow you to take a complex
scheme and reduce it to the security of
some small simple well understood uh
assumption and you can also share this
assumption there are many cryptographic
schemes that can be can be reduced to
incp uh to DD to the ddh Assumption and
that way all everyone who wants to try
to break the schemes can simply try to
break the ddh Assumption and either all
schemes are broken or none of them but
we have uh something that we can very
well concentrate on if you visited the
postquantum crypto talk yesterday uh
Tanya and djb were complaining about all
those proposals for the postquantum uh
schemes and that it was impossible to
review them all this is what allows to
review all those new um cryptographic
schemes that are not only encryption
schemes because everyone just has to
look at very few
assumptions and you also avoid problems
from weird interactions if you have
multiple assumptions um this was not the
case right now but in reality you use
several Primitives and even if those are
secure on their own they might not be if
you combine in with others and the proof
now gives you the certainty that my
scheme is secure as long as all of those
are secure I didn't introduce issues
from combining them which is also very
valuable now um back to the definition
of security and the problems there or
well in this case not really that much
of a problem what you just saw is a so
called game based proof I mean you saw a
game so it's rather intuitive why it's
called that way and those are generally
speaking easier to do than the
alternative exceptions exist but they
often have a less intuitive meaning for
example I told you that rough definition
of ncpa and semantic security ncpa was
comparatively weird and Technical
whereas semantic security was pretty
straight to the point and that is often
an issue that those game based
definitions have they are very technical
and it's harder to get an intuitive idea
what they really mean also the more
complex your protocols get and for
example if you want to design
cryptographic voting schemes the less
these proof scale at some point you need
to switch to the
alternative which are so-called
simulation based proofs for those you
define some ideal functionality so
imagine it as a trusted party that just
falls from the sky and is perfectly
trustworthy you define whatever you want
to do is done by that party and then um
assume that everyone has perfectly
secure connections to that party and
then prove that your real protocol is as
secure as this idealized uh thing those
proofs tend to get more intuitive
meanings uh semantic security is a
simulation-based
um uh definition of security and as I
said it's a lot easier to understand
what it means but they also usually a
bit harder to do also especially with
them though that may be because the uh
schemes that you will usually prove of
them are more complicated you can get
something called proof artifacts that's
where you need some very weird thing in
your cryptographic scheme that doesn't
appear to serve any purpose for
example you suddenly have a cipher text
in some place for a public key and no
nobody ever has a secret key for that
public key and that may sound sound very
weird and pointless and sometimes it may
be sometimes actually do serve a purpose
so just because something looks weird
doesn't mean that it is unnecessary but
maybe sometimes it is and that's one of
the big issues we Face there
now in the start I mentioned RSA and I
said there are secure versions of it and
this is the case however they require
something a bit more complicated and one
of the things they Ed to acquire
security are hash
functions and hash functions are pretty
much functions where you can throw in
some random some string of some length
and get out a random looking bit strings
of fixed lengths independently of how
long the um string that you throw in is
and I say random looking because the
proper definitions of what uh a secure
hash function is are shockingly
complicated you can ask me after the
lecture if you want but um it's very
very easy to get them wrong especially
since they appear to be so easy now
Lucas will now tell us how these hash
functions are used or well some of the
issues that they we face with them
because the RSA proofs are not really in
the standard model instead they use
something
else yes well if we want to model a hash
function in our proofs and we want to
get rid of all these strange properties
of hash functions we use something
called a random Oracle which is in fact
uh this dwarf and this dwarf uh lives in
a box and he has a DI in a book and if
someone comes to the box and wants to
have a hash for a specific message he
looks into his book and wants to check
out if he already answered such an
message and if he did then he answers in
the same way as he did before
and otherwise he rolls his Dice and gets
a new random value uh which is now the
hash of this
message unfortunately no one has ever
found such a box with a dwarf and
furthermore it would be quite difficult
to handle because every time you want to
compute a hash you would have to go to
the
dwarf but the biggest problem is that
this is not a
abstraction and I'll show you what the
problem
is let's assume that we have a secure
encryption
scheme and let H be either a hash
function or a random
Oracle then we simply
reuse the generation algorithm which
gives us a Keir for a new encryption
scheme and we partly reuse the
encryption
algorithm and modify it like this we
check is the message valid
code note that uh a code execution
attack is not the problem here we simply
look at it is it a valid uh code we take
random input X and evaluate the code
given this uh random input and if the
results of the code is different than
what age tells us then we use our secure
encryption
scheme but if it's the
same we use our secret key as the cipher
text this might sound very weird yes you
should not do this in a real encryption
scheme but here we can see that this
scheme is secure if we use a random
Oracle
but insecure for any instantiation with
a hash
function if you use a random Oracle the
probability of uh the dwarf to get uh
the same output as the given code is
negligible because it's randomly
chosen but for a real hash function you
simply can put in the code of your hash
function and it will of course be
evaluated to the uh same result as the
hash function and then you always get
the secret
key so the random Oracle allows us to
prove schemes which are obviously
insecure uh the authors who uh write the
first paper on this came to some harsh
statements it should be clear that the
random Oracle mythology is not sound
that is the mere fact that a scheme is
secure in the random Oracle model cannot
taken as evidence or indication to the
security and furthermore he
said indeed what happened with the
random Oracle model reminds us of the
biblical story of The Bronze serpent the
story illustrates the process by which a
good thing may become a fetish and what
you should do in such a
case spoiler alert this snake had to be
destroyed but if you need to sign the
Bible as a cryptographer uh your point
maybe is not as uh good as you might
might think other also authors
said that if one of the world's leading
Specialists put forth his best effort to
undermine the validity of the random
Oracle assumption and if the flawed
construction is the best he can do then
perhaps there's more reason than ever to
have confidence in the random Oracle
model so you see that even in the
scientific Community this model is uh
it's not clear what what to do with it
because it's widely used in proofs and
there are schemes that can only be
proven in the random Oracle model and
they seem to be secure
but obviously as you you saw the random
Oracle model allows also to prove the
security of insecure
protocols so people try to get rid of
it
they invented uh signature schemes which
don't use the random Oracle model but
suddenly strange stuff
appeared this duplicate signature key
selection attack is an attack which is
also out of model for the typical
definition of the security of uh
signature schemes and it allows that
given a signature and the message under
some public key you could be able to
find a new key pair such that the
signature is valid under your new
generated key for the same
message and maybe that's not a problem
in your specific uh use case but you
should really be aware that uh this
could happen if you use this kind of
sign
signatures another example the bonen
signatures uh were derived from another
signature scheme but suddenly the
signatures get much more complicated
here in the easy one you have just one
group element in the complex one you
have two and the second one is quite
difficult to calculate and the
probability that a programmer will do
some mistakes by implementing it is much
higher than in the easy scheme and then
the question is is this worth the effort
do we want to have
have schemes which are secure without
using this unsound model or do we want
to have the easy
ones so you might have noticed that we
get a little bit deeper in the beauty of
proving brinar and for the next step
I'll introduce another cryptographic
tool which is called commitment
schemes a commitment scheme works like
this
uh a party Alis has a message
M and she wants to tell Bob that she
knows that that she's choosing the
message but not telling the message to
Bob you can imagine it like uh having a
save writing the message on a piece of
paper put it into the save lock it and
give the save to to Bob and if you tell
Bob the the code for the save then he
can open it and read the
message for this scheme we have two
messages the first one is called the
commitment and it should have two
properties it should be binding which
means after sending the commitment Ellis
should not be able to manipulate the
message and it should be hiding which
means that Bob should not should not
learn anything about the message given
the commitment
and later Ellis can open this commitment
which is called the
unveil in this case she simply sends the
message and the random and now Bob can
calculate if this message and this
random matches to the uh commitment
given
before well let's assume we have this
secure scheme and we buil a more complex
protocol let's assume assume that they
both want to know if the message that
they've chosen is larger than the
message the other one has
chosen Ellis commits on M and send the
commitment to Bob Bob commits on another
message and sends the commitment to
Ellis and then they open the commitments
and they see who wins the
game but what happens if Alis is not
interacting with Bob who's nice but with
an evil party mallerie who acts like
this mallerie takes the commitment C and
multiplies it by the generator Ellis has
used then when Ellis opens the
commitment mallerie can simply open this
message as a commitment on M
plus1 that's not what we want to have
using our commitment scheme so composing
protocols together
can make them insecure or can can lead
to
insecure
protocols and what we want to have in a
security definition is that the security
definition should contain all imaginable
properties and should be secure
regardless of the context in which you
use your uh
primitive you see that using these uh
locks for the like are not composable
they're not even
secure to do this we use this simulation
based uh proofs and a special uh variant
of it called the universal composability
model here we have this ideal function
floran mentioned
before and we have the real protocol and
we prove that um environment which is
everything
outside of the protocol all computers
all protocols on the internet for
example is unable to distinguish if it's
interacting with the real world or with
the ideal world so we have
this uh sorry that's not an ideal
functionality um this one um so we have
here is Catholic so that's why it's
trusty so we have this trustworthy
Authority and the parties simply put
their input to the trustworthy Authority
and the
authority calculates stuff and gives it
back to the parties in the ideal
scenario and in the real scenario we
have the parties executing our
protocol but we don't have only the
parties but also an
adversary who can for example listen to
the message messages uh manipulate them
or even corrupt
parties and he interacts with the
environment
that so you can think about like the
environment and the adversary are one
party and uh they want to know if they
are in the real scenario or in the ideal
one in the ideal one you have a So-Cal
simulator and he tries to con convince
the environment that he is a real
attacker but he is interacting with the
ideal
function which uh won't tell him too
much on the messages the parties gave
in and now we say that a scheme is
secure
if for every
adversary there exists a simulator such
that any environment is unable to
distinguish uh in which world uh it
lives how does such an Nal functionality
look
like we'll look at the uh functionality
for
commitments Alis can put the message in
then the message uh the functionality
tells Bob that Ellis has committed later
Lis says unve it and then Bob gets the
message so now now we'll try to prove
such a system in this Universal
composability
scheme the environment using the
attacker tells the corrupted Senter to
use this
commitment the corrupted Center uses
this commitment later it he's told to
unveil he unveils and then uh the
receiver who is not corrupted can ask
answer with the
message in the ideal
scenario the simulator is on the good
side because he wants to confirm the en
environment that he's in the real
scenario and he works together with the
corrupted
party the environment tells the
corrupted party to use this
commitment it tries to uh send it to the
uh ideal functionality and
ideal functionality is confused because
there is no definition of to give in a
commitment but you want to have a
message instead and you could try to
extract the message from this
commitment which should do the simulator
but this would break the security
definition of our commitment scheme so
there can't be a commitment scheme which
realizes this ideal
functionality that's bad because we
believe that there are secure uh
commitment
schemes so what's the reasonable and
most clear solution for this of course
we could introduce a back door uh sorry
I mean uh we could introduce a common
reference string a common reference
string is a randomly choosen value by
from a given distribution
it's choosen honestly but exists only in
the real
world so let's assume that our uh common
reference string in this case is a
public key and two
generators such that the uh public key
is chosen randomly and no one knows the
secret key now Ellis can uh use this
same commitment scheme as before for c0
she encrypts the message with the public
key where no one knows the secret key of
she proves with some magic cryptography
that the message in C1 and C2 is the
same and then she uses this as a
commitment the simulator
now uh uh can just uh take the uh common
reference string on its own but he's not
taking it from a given distrib
distribution randomly but instead he
uses uh a real uh key generation
algorithms so he knows the secret key
and he don't take random
generators but he chooses them in a way
such that he knows an X with g to the x
h and now he's able to extract the
message bit from the
commitment and put it into the ideal
functionality so in producing this uh
back I I mean introducing the common
reference string uh allows us to prove
this
CQR so maybe when the uh NSA gave us ecd
RBG they didn't want to Snoop on us but
maybe they just wanted to give us a tool
to provide extractability in UC
scenarios well maybe they probably they
wanted a snoop um as we said common
references strings are basically back
doors so it's quite hard to convince
people that they honestly
generated the probably most
sophisticated one where people actually
use complex com reference strings um
involves the cryptocurrency ccache where
they went through quite Great Lengths to
produce a common reference thing that is
plausibly honestly generated of course
it is
indistinguishable it must be
indistinguishable whether that's the
case um we did uh subtitle there is a
link if you download the uh slides uh
you can watch the video it's quite
interesting um in other scenarios uh
sometimes you might get away with
nothing up my sleeve numbers for example
the Monero guys will tell you that they
don't involve uh they don't they don't
use anything that uses a trusted setup
well they use Patterson commitments
which are the commitments that we
started out with and for them you still
um need some kind of plausibility that
nobody knows the discrete logarithm
between that G and that age and what
they did was basically they uh took uh
the element she G through uh through it
through sha 3 and use the output as the
other uh group element and that is
indeed quite plausible that it's secure
but still it is a kind of common
reference string now all that being said
let's come to the conclusions the first
one as always for these kinds of talks
please don't roll your own crypto it's
extremely likely that you will get it
wrong we um skipped over several details
here and even if you implement manage to
implement um a scheme in a secure way
for some security definition it's still
doesn't mean that your security
definition is what you might
want um other than that security is
difficult if you do it please at least
employ proofs and be aware of their
limitations also um the random Oro model
may be a flaw um framework but no scheme
no real world scheme that has been
proven secure in it has ever been broken
because of the random ARA model so a
good euristic is a lot better than
nothing so at least use that and if your
proofs are too complicated for other
people to read they are not all uh that
much worse that's the big problem with
UC proofs they are so complicated that
often nobody really reads them and they
are arguably therefore less uh
convincing than random Oracle model
proofs because those tend to be simple
enough for people to understand with all
that being said we are now here for some
questions and thank you very much for
your
[Applause]
[Music]
attention thank you very much for this
most excellent talk we have microphones
in the S here so please line up behind
them and to start it off we have a
question from the internet
okay and can you elaborate why there is
such such much conference in ddh
assumptions yeah um the first thing is
it's very people spend a lot of time
looking at it and assumptions usually uh
stem from the idea that if we looked at
it for a very long time and nobody found
an attack there's a good chance that is
secure there's also a different argument
um there is something called the um
generic group model and it uh formalizes
the notion of those mathematical um
Concepts that are used I only showed you
um the a very technical definition of
the alal scheme there is actually a way
to view it in terms of group Theory and
if you do that it Al it becomes much
simpler but you require the previous
knowledge and you see how you can
um map it to this generic group model
and the generic group model allows you
to prove that there are no generic
attacks that only use the structure of
the group and there is a proof that um
in the generic group model the
decisional defy Helman assumption holds
but that doesn't mean that there are no
attacks on it that use non-generic uh
properties of the group for example the
reason we want use elliptic curves is
that we believe that they are mostly
equivalent to generic groups and the
reason we need so huge uh groups for if
you want to use regular prime numbers is
that they have more structure than that
so it's a very good argument but it's of
course not perfect and also if you get
quantum computers all bets are off uh
that's completely broken in that case
microphone number two please hey
thanks um my question is is do you think
doing a proof in the random Oracle wle
is helpful in constructing um a proof
that can later be Advanced to remove the
random Oracle model and does this
usually happen in your
experience well
yes often you start by approving your
scheme in the random Oracle model and
then try to get rid of
it but
this you saw the results yes you saw the
result
uh often you need to uh change stuff in
your protocol uh to get rid of the
random Oracle model and this leads to
complicated constructions uh which are
difficult to implement and may introduce
strange
properties does that answer your
question yes then microphone to again
please what's on the next
slide okay that's the bonus slide um a
little bit on security levels um if you
want I can tell um I believe we have
some time left there is four more
minutes okay that's uh is enough um
there is this uh you occasionally count
the uh encounter the idea that there
that some security level is enough or
insufficient or whatever and the first
thing uh that is maybe not that trivial
is that there are fundamentally
different kinds of Security even for the
same definition the one that most people
think about is called computational
security and what that means is
basically if I give the attacker a
certain amount of computational power
the attacker shouldn't be able to break
my scheme using brute force and that's
where you um where this 128 bit comes
from which is a level where the energy
if you use somewhat realistic
assumptions on Hardware the Pure Energy
conern Assumption of going through that
many steps is I believe enough to boil
the oceans so 128 bits on itself is
pretty much sufficient there are also um
certain schemes that provide statistical
security which is in a way much better
because in that case the question is not
how much computational power does the
adversary have but just how much luck
does he have and if you think about it
um computational Power has to factor
that in if you um have a one in a
thousand chance to um brute force a
certain key using 2 Tod 128 operations
you still have to factor in that factor
of one in a thousand you um so the
statistical security uh parameters can
be much smaller and if you read 40 bits
of statistical security that's not great
but it's not as terrible as it may sound
at first
and finally there's perfect security
which is even if you give all
computational power of the world and
then a lot more to the attacker and if
the attacker has perfect luck he still
isn't able to break it the most popular
scheme that provides that is of course
the onetime pad where for every um
possible blame text there is a key that
will encrypt the cipher text to the
plane text those are completely
impossible to break and as such there is
no security parameter yeah I think we
might be able to take one last question
do we have another question from the
internet no no question from here well
then a warm Round of Applause for Lucas
[Applause]
[Music]
and
[Music]
a