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/84 Thanks!
Well, thanks for the nice welcome.
We actually a few weeks ago at
the Asia Krypt conference, which happens
every year, we asked cryptographer, Hey,
what do you think the most important
thing that happened in crypto this year
was? And he said, Well,
of course, the answer is obfuscation and
distinguishable the obfuscation based on
multi linear maps.
Now, I hate
to say this, but you know, the flagship
cryptographic conferences are full of
this sort of shit.
And if this is the best defense that the
world has against in the US National
Security Agency, we're screwed.
So on that note, this is a picture
that I took at a talk that I went to
at the University of Pennsylvania last
month.
This is John Inglis, the deputy director
of the NSA.
And here he is, showing an unclassified
NSA slide of how they understand
cyberspace.
And apparently, they understand
cyberspace as a series of layers.
There's people, devices, information,
geography, et cetera.
Yeah. So somewhere in there, there's a
turtle. All right.
So taking our inspiration from the NSA
here is, you know, a way that you can
understand cryptography.
This is just to get our bearings here.
So at the top, we have some mathematical
problems, like factoring a discrete log
from those. You can construct
cryptographic primitives like RSA, Jiffy
Hellman and so on.
You use those in different protocols
like tell us at this age, p-gp the things
you use to keep yourself secure on the
internet.
Those are implemented in libraries like
open SSL and be safe, and
those libraries are used in these
software applications that you as users
actually use.
We're going to be talking about all of
these different levels today.
So let's start at the very top
with the crypto apocalypse.
So actually, like earlier
this year, we were thinking, well, last
year we actually we talked about
factoring for those of you who are here
and we're thinking, Oh, well, the
obvious follow up is this year we're
going to talk about discrete log.
This will be great.
We'll give a nice, you know, instructional
lecture about discrete log.
So the first, you know, five slides of
this will be all that we have the
instructional lecture about discrete log
because some other things happened this
year.
So what is the crypto apocalypse?
Well, sort of. It's if you look at this
headline, this is the big picture
that you should have.
Massive events has raised the prospect of
an internet security crisis.
Oh my god.
Academic advances suggest that the
encryption systems that secure online
communications could be undermined in
just a few years.
This is an article written about a talk
at Black Hat about the crypto apocalypse.
So the crypto apocalypse is
sort of summarized in this
article a quasi polynomial
algorithm for discrete logarithm in
finite fields, a small characteristic
which, if you are not an academic,
perhaps is a little bit more confusing.
But essentially, this is a big
breakthrough in the discrete log problem
for small characteristic fields.
The context for why this is an important
to cryptography is the fact that all
of the public key cryptography that we
use on the internet relies on three
basic assumptions.
Those assumptions are factoring integers
into primes discrete log modulo large
primes and discrete log and elliptic
curve groups.
Every single public key crypto algorithm
that you actually use relies
on one or more of these assumptions.
This is all we have after
thirty five years of public key crypto
research.
Some examples just to, you know, make
this really concrete here.
I'm generating a and that's the key.
It's an RSA key that means I use
factoring or that I hope that factoring
is safe here.
I'm looking up run reverse
p-gp key.
It happens to be a DSA key that means
discrete log modulo prime.
And here I am.
I have a secure HTTPS connection
to Google.
It's telling me it's using AC DC.
That's Elliptic Curve Discrete Log, and
it uses RSA signatures.
That's factoring.
This is all we have.
Look at any, any crypto system that you
use. This is what you'll see.
So discrete log over small
characteristic fields is not one of
these assumptions. Nobody actually relies
on this in for public key cryptography,
but it is intimately related to the
assumptions that we do use, such as
factoring in discrete log over large
characteristic fields.
And the important thing here
is that factoring a discrete log have
some exponential time algorithms.
We've known this since the 80s.
There have been no big algorithmic
improvements since about 1993.
Basically, all of the progress in sort of
the crypto analysis of these basic
assumptions has been improvements due to
Moore's law and small implementation
details, essentially,
and the running time for a small
characteristic fields and large
characteristic fields.
Basically the same until this
year, when or
earlier this year when there was
a series of breakthroughs for
a small characteristic fields.
So the only important thing that you need
to know from this chart is that if you
look at these numbers, they're getting
very large, very fast.
Oh, OK.
I'm still back.
And here it is.
March there's been some actual
algorithmic improvements.
There's an L of one fourth algorithm and
an end to the O of log, an algorithm
for these special fields.
Now what is the
impact of this?
So if this kind of algorithmic
improvement could be translated from
small characteristic fields, which we
don't care about for cryptography in most
cases to factoring
or large characteristic fields,
then?
There would be problems for all of the
cryptography that we use in the real
world, big, gigantic, if here
everything I'm saying is predicated with
an within. So the current
general purpose factoring running time
for some integer is
this complicated function, which
is sub exponential and that's
all you really need to know.
The small characteristic field
improvement went from one third to L of
one fourth to and
to the big of log in.
If we took factors running time from
L of one third to one fourth or
something smaller than that,
then this would be sort of catastrophic
for the security of key sizes.
So this is just a very hand-waving
chart. The top line is the current state
of the art.
If you just sort of blindly take
sort of this running time to try
to estimate the bit security of different
sizes of RSA keys.
So for a 10 24 bit RSA key,
this equation gives
you an eighty six bit security, which is
approximately right.
So we'll just take this as our ground
truth.
So 2048 bit should have one hundred
sixteen bit security and 496 bit should
have 156 bit security.
If there is a small improvement in the
constant of this algorithm,
I'm not saying it's happened.
But if this should happen, then
the bit security of 10 24 bit RSA
would drop to sixty eight bits, which is
already enough to basically be a gigantic
problem in the real world right now.
2048 gets pretty close to being
scary if
on. On the other hand, if we dropped from
an elephant through to an O one fourth
algorithm, the bit security
of RSA upturned 24 bit RSA would
would drop to 49 bits, which is basically
solvable almost immediately now,
and even 496 bit RSA would
be way too close for comfort.
This is
food for thought.
I guess the
upshot of this, however, is that no,
we don't know how to adapt the these big
improvements for small characteristic
fields into the cases that
we care about in cryptography now, like
large characteristic primes
or factoring.
But this is a reminder that sometimes big
progress can be made on old problems.
There was very little progress for two
decades, and then all of a sudden there
was a massive improvement.
We do not know the end of the story for
factoring. As far as I can tell, there
is no proof that these problems are hard
and the complexity theoretic sense.
And
therefore, just because
nothing has happened for two decades
doesn't mean that something cannot
happen.
Asterisks elliptic curves are completely
different story.
All of these techniques are unlikely to
work in that case.
So for practitioners, the things to
think about Dan and I actually had some
big arguments about what to say here.
I want to say, don't hard code.
Your algorithms are key sizes because
things can change.
Stone doesn't like algorithmic or
algorithmic agility.
But he says that we we know what the
correct choices are, and you should put
in the correct choices, which is, you
know, very conservative choices for
elliptic curves.
And the big lesson here is listen
to the cryptographers because this
kind of news is actually old news
and if you need
to use new
public crypto.
Think about elliptic curves.
There will be a little bit more on this
later.
All right. We, as Snoddy mentioned,
have some other topics to talk about
because sadly,
some other things happened in crypto this
year. Actually, what I found most
interesting from the beginning of the
year was for the first time in recorded
human history, a non-technical user
actually tried to use cryptography.
Now, as you know, the results
were not pretty.
They were really not pretty.
Oh yeah. All you went to the keynote, so
you know who I'm talking about here.
Glenn Greenwald was trying to install
p-gp. He found it so annoying
and complicated that Snowden
gave up on contacting Greenwald and
contacted Laura instead.
So, OK, now eventually, Glenn got
back into the game, but this is an
example of how unusable today's high
security cryptographic solutions are.
So maybe let me propose a New Year's
resolution for
2014.
How about some high security
cryptographic software that's so
easy to use? A journalist can use
it.
Now, of course, we do have some crypto
that's actually deployed on the internet
like TLS https, that's
something which is a pain to set
up on the server side, but it's actually
reasonably easy on the user side.
But is it actually secure?
Well, been a bunch of problems with
it over the years, and there's some
interesting news about that this year.
So in February.
Well, here's a quote from 2008
from the TLS specification, which says
there's a small timing channel that's not
believed to be large enough to be
exploitable.
And this is like, you know, in the movie
when you see, you know, there's the bomb
of it, it's inside a box, so it's not
going to blow up. You know what's going
to happen here? So
there's this lucky 13 attack announced
in February, which says that, yeah, this
timing side channel is exploitable.
It can be wrangled into revealing
plaintext data. And look, here's the demo
they actually did it and got cookies out
of supposedly secure SSL connections.
Now, vendors have experience with
this kind of problem. When you look at
the details, you see where this timing
side channel is coming from is CBC
the way that CBC is used inside
TLS. There's some do
a message authenticator and then pad
and then encrypt, because CBC only takes
full block sizes for its messages that
it's encrypting and, well, the fact
that CBC causes problems.
We already saw that with, for example,
the beast attack and attacks.
Before that and after that, lucky 13
is just the latest example of this.
So vendors know what to say when
there's attacks against CBC.
TLC offers algorithm
agility. Telus gives you the opportunity
with less costs maybe
than it would have been if it hadn't
supported this. To begin with, Telus
offers the option to switch from CBC
to the backup plan.
The backup plan is, of course, RC four.
So here's from EF five.
EF five is
big network equipment vendor and very
widely used, and they are one of many
examples of vendors saying, OK, protect
yourself against all these attacks like
Lucky 13 by configuring your SSL
to use RC four and try to do this on the
client side, try to do it on the server
side and RC four is immune to these
attacks. So RC four
by February was successfully
used for more than half of all
SSL traffic on the internet, according
to some surveys, which caused
a little bit of a fuss months
later, with attacks against RC
for as used in TLS, which would
recover cookies after some
number of millions, or maybe even
billions of repetitions of the cookie.
It's not the fastest attack in the world,
but it doesn't need all of the fancy
timing being close to the server you're
attacking or the client you're attacking.
Like Lucky 13.
So RC four is not looking too good in TLS
is also problems with using RC four and
WPA rc four being broken.
This is not new.
This is something where RC four has had
weakness after weakness.
After weakness starting in 2000
were already major papers saying RC four
sucks. This is just not a good stream
cipher and still it is deployed
as well.
It's dropped from 50 percent, but is the
stream cipher that's widely implemented?
Intel's So at this point, TLS
has the Ace CVC
option, which is extremely
difficult to implement in a secure way,
and it has the RC four option,
which is broken
no matter how you implement it, it just
doesn't encrypt your data properly.
And then it has, for example,
the JKM option.
If your client and server support
TLS 1.2, which
your client doesn't.
Your server might.
It's not really a pretty picture.
So that's the story for TLS.
Continuing with this sort of attack theme
that we have going here, I
want to give a little update on something
that we talked about last year in our
talk, which was the Taiwan Citizen
Digital Certificate.
So Taiwan has this sort of nifty
government level PKI.
Citizens can get these little smart cards
and use them to interact with their
government in a secure way.
This is cool.
So last year, when we were talking
about weak RSA keys,
we reported on a student project from
Taiwan, where they collected three
million certificates with
RSA keys in them and computed
the pairwise jacks of all of these
keys, and found that some
actually shared common factors which let
them factor these keys easily.
There were a hundred and three keys that
had this property, so if you have to
ask keys that share one common problem
p, you can compute the CD
that gives you P. You can divide out, get
P and Q that gives you the private key.
OK. So, you know, there's lots
of R&D failures of this form.
You know you if you went to Alex's talk
earlier today, you heard about weak
keys and routers and things.
Bad random number generator.
End of story. Right?
OK. You know, they got to fix it.
Then we took a closer look at the prime
factors.
This is the most commonly shared prime
factor in these keys.
It's prime.
It's random.
This is the next prime after two of the
511 plus due to the 510.
So yes,
that's the problem
with the random number generator.
This is the next most commonly shared
prime factor.
And as we went down the list of the prime
factors, we found a whole bunch more of
this form. So by sort of extrapolating
cleverly doing some trial division,
random guessing
and some nifty math tricks involving
lattices, we were able to factor 80
more keys.
This is a lesson that there's lots of
ways that crypto can fail if
you have a better random number
generator. There's lots of structure in
these problems.
It turns out the root of the problem was
sort of a combination of two things
there's a faulty hardware R&D in the
Renaissance IEEE 45C one
microcontroller, which is the card,
one of the cards that they were using for
this PKO deployment.
And this was combined with a failure to
do any post-processing whatsoever on
the card output.
So yes,
we factored some keys.
So the old and the Snowden leaks started
and cryptographers started being kind of
interested in all the things going on
there. And so the NSA had to swing into
action.
And so here is what they threw at us.
So certainly on a print
publication from the NSA surfaced about
two stream ciphers or two small,
lightweight ciphers blog ciphers
designed by the NSA.
And sure enough, those worked
so throughout the year. There is four
more papers on Eappen, so
apparently the cryptographic community
has been successfully distracted from
looking at this.
Actually, it's worse than this.
I took an oath of secrecy as a member
of the Program Committee for
the Fast Software Encryption Workshop
that I wouldn't reveal to you what I'm
about to reveal to you.
There were eight submissions of papers
to this workshop which were encrypt
analyzing Simon and Speck.
Now imagine this for a moment you have
like eight papers that are 15 or 20
or more pages each, and
we're scientifically obliged to
review these papers and have three people
write detailed reports about each of
these papers. It's like twenty four
reports, about eight papers about
these NSA ciphers.
How could you possibly be crazy enough to
deploy an NSA cipher in the first place?
But nevertheless, we have to spend time
on this
more productive stuff, so we didn't
get distracted. So we sat down we being
Peter Schwab, a student of the army,
and did a small version of the Solve
library. So this whole library is
not dead or no slides already.
It's a very small
compact.
It just gives you one option, but that's
the option we think you want.
And now you can have the same thing in a
very short version in just a hundred
tweets. So if you go to Twitter.com
slash Twitter, you can find
the whole library in just our tweets.
There are also some nice indented
versions, a little bit of advertisement.
So for those of you who are interested
in this whole library and other stuff,
this you broke the internet assembly
going on in parallel and whole E.
And tomorrow afternoon, starting at one
o'clock. There is a meeting where we
will be reporting in more detail
about this whole library.
So later on
in August, some other things happened
in the crypto world, including
the sudden shutdown of an email provider
that nobody had heard of before then.
So that our Levison
wrote this very
touching letter of
apologizing that he had to shut down his
email provider for unknown reasons.
A couple of months later, we actually
found out the reason which is, among
other things, this document.
This is a grand jury summons
commanding him to appear in
Alexandria and bring to the
grand jury the public and private
encryption keys used by law to become
in any SSL or TLC sessions,
including HTTPS sessions with clients
using the love of Inc.com website and
encrypted SMTP communications
or internet communications using other
protocols with mail servers.
This is amazing.
I mean, we, you know, since the NSA
revelations, people have been
speculating, OK, is there some sort
of legal procedure that the government
can use to get private keys out
of internet providers?
Is this possible?
Is this legally possible or their Fourth
Amendment restrictions?
And then suddenly, like, we have this
thing appearing out of outer space and
we actually see that it's happening and
this is so casual that there's no way
that this is possibly the first time that
this has ever been done.
But this is the only case that we've
actually seen of an internet provider
being compelled to turn over the
keys for their entire service this way.
This is incredible.
So I want to explain just a little bit of
sort of basic crypto to understand why
this is so damaging.
So this is a diagram of how
the tools RSA key exchange works.
This is the most commonly used key
exchange method.
If you do a session.
So the way that it works, that the client
so Alice wants to connect to say a lot of
bitcoin.
She says hello.
The server replies with a certificate,
which contains a public RSA key.
Then what Alice does is
she uses that RSA key to encrypt
some symmetric key information and sends
it to the server.
And then what the server does is it
responds by then initiating an encrypted
session using the symmetric
key information that Alice sent over.
And then from then on, all their
communication is done using
this key information.
So once the government
has asked for love of its private key
if they have been collecting
the information that
love of it has been sending to everybody
over time.
They can then decrypt
the traffic that is sent from
now on or from any point in the past
where they have the traffic because they
have the private key for this
RSA key
here. They can just decrypt the packet
that is that contains the
symmetric key information and then
decrypt the entire session.
So this so demanding a private
key of this form endangers
not just the one customer that they're
going after, but every single customer of
the entire service.
The other thing that the having the
private key allows is for
the server to impersonate or anyone
who has the private key to impersonate
the law of a bitcoin server to anyone
on the internet, because this key has
been verified by a certificate authority.
This is presumably what the government
actually wanted from the server.
But as a side effect, they got
bullet point number two, which is much
more dangerous.
In contrast,
this is an alternative key exchange
as the Diffie Hellman key exchange, which
offers a property called forward secrecy.
So the way the Diffie Hellman key
exchange works is that Alice
and the server exchange these values
due to the axiom due to the way and then
using the
these values do the same due to the way
they can derive a shared secret
due to the X Y, and that will form the
private key and the security of the
Diffie Hellman key exchange relies
on it being impossible for
an adversary such as the government who
is sitting on the wire between them given
due to the accident due to the way to
derive this value due to the X Y.
And so this property is for
its secrecy, which is that once
Alice and the server have forgotten the
values X and Y, then nobody
can reconstruct the private key due to
the X Y anymore.
And if Lavabit had, instead of
using the RSA key exchange used to defeat
Hellman key exchange, then they would not
have been endangering their customers in
this way.
So a piece of homework
for you, as if you're an end user,
you can actually check whether the
websites you're visiting have enabled for
secrecy. If you go, this is in Chrome.
I don't know how your browser works.
It's probably similar.
If you click on the little lock and you
click on sort of connection, you can find
out all the cipher information that your
HP connections are using here.
It says it's using DHC.
RSA is the key exchange mechanism.
The DHC is diffie home and ephemeral.
That means that it's using for
its secrecy or if it says
that also means it uses for secrecy.
But data is bad and OECD
is bad. You have to have the E at the end
is important, but the data
is better than ours.
If you are a website operator,
it would be wonderful if you would enable
for secrecy for your users.
There are many guys online.
Here is one.
And here's an example of a website that
does not use
for its secrecy they're using.
RSA is the key exchange mechanism and a
couple of other broken
cryptographic ciphers and
recommendation. If you're building a
privacy tool, please use and end crypto.
As a little footnote,
if you try to visit https lovehoney.com
now, you get a big
warning that the server certificate you
searched, the Server Certificate Security
Certificate is revoked, which means that
if nothing else, at least the
picture that we have is working the way
that it should somebody else have
the private keys to love become.
Therefore, the security
of this entire system is compromised
and the CAA has recognized that.
In August, there was a huge news
conference and made headlines
that one of the talks was not being
presented.
So this was a talk by British ego Flavio
Garcia, who also adult and what they
showed is an attack on
breaking the wall.
Its car mobilizes the company behind it,
assuming the was folks will, but it was
more for their high end luxury cars.
Now they got an injunction
in the U.K.
and it was saying that they couldn't
publish the paper because that paper
would reveal the secret
algorithm.
It is not. They cannot publish the paper
because they broke the algorithm.
It's they couldn't publish a payment
because it would reveal the algorithm.
Now
we the I asked him if he
could at least publish the attack.
And OK, they were also not allowed to
publish the attack because the attack
would allow a reader
to reconstruct what
the secret algorithm is.
So those who
now have these cars are
no more secure than they were before.
But the people couldn't publish the paper
and cryptographic conference.
All right.
Back at the crypto conference
circuit, if you're
going to be writing papers about things
like in distinguish ability obfuscation
using multi linear maps, then well, it
doesn't mean that you don't care.
And so a bunch of people got up on
stage and sang to this year to the
tune of Surfin USA,
a song called Spy NSSA, which
finished off with something like
Everybody use crypto screw.
The NSA are not going to spend the next
three or four minutes trying to sing this
for you. Go to YouTube.com, slash
the URL listed there.
I think it's a zero.
And then Rykoff underscore
lowercase Aussie B for
in more serious news
shows 2013.
So this is the cryptographic hardware
workshop that happens every year.
There was this terrifying paper where
I'm going to have to give you a little bit
of background.
You know, the current Intel chips, the
big Intel chips, maybe not the low end
atoms, but anything like a Haswell
is going to have inside it a
random number generator, which
Intel's been telling you to use
to generate your random numbers.
You're not supposed to use all of that
entropy collection, this kernel entropy
pool or are injured or anything like
that. You're not supposed to have
something where there's lots of different
interrupts and entropy sources and
timings of this and that all being hashed
in a complicated way in your application.
You're just supposed to take R.D.
Rand, which is this new instruction.
Or I've learned from the intel people I'm
supposed to say, read rand, the R&D.
You're supposed to just call that
instruction. They don't make it
privileged, so you can use it from your
applications. It's not just for the
operating system.
And I did a GitHub search a week
or two ago, something like thirty two
thousand results for applications
using Read Rand or will file.
So maybe some of that is documentation.
Lots of people are using read rand now.
This in the last few months has raised
some controversy.
People saying, Hey, is read
Rand actually trustworthy?
And Intel says, Well, yeah, we designed
it like this. We're sure it generates
good random numbers.
Much better than that Taiwan smart card
you heard about. We know what we're doing
generating random numbers, but wait a
minute. What if Intel is actually
generating as output with a key
that they know?
How would we be able to tell the
difference between that and random
numbers? Or what if somebody else knows a
kid? And while Intel's response to that
was, it's OK, we produce
these chips and we looked at them through
an electron microscope and we verified
that they don't have anything, you know,
even if somebody managed to sneak into
the manufacturing room, we checked
through an electron microscope that
everything's laid out exactly as it
should be.
Now what this paper is saying
is here's how you can manufacture a chip
so that through an electron microscope,
it looks totally legit.
And it's back to it.
So this paper, it's it's worth reading
the paper if you're interested in
hardware and what you can really do by
maliciously manufacturing hardware.
It's a fantastic paper to read, and it's
telling you that everything that Intel
has done, at least that they've publicly
stated for verifying that they're random
number generators working properly could
actually have been backdoored, and they
wouldn't have been able to tell.
Intel says, Well, yeah,
yeah, well, we're looking more closely,
really, and everything's fine.
So all good.
He comes a little bit of a blast from the
past for
reasons that become clear soon.
I would like to take a look at a random
number generator, which is
not quite as interesting as the
rebranding that we have had hardware
graphics. This is a software
pseudo random generator, so you have to
fit in some seed, some true when
number generated by something like the
Intel chip or something else.
And then
you can have no input, but it's not
really recommended.
It runs through this algorithm a few
times now.
What it does there is is doing operations
on elliptic curve, so at every moment.
So once you're through the initialization
stage, then you always
run around to the
thing they're usually X or zero,
so nothing happens there.
You have the scalar T you
compute T times piece upon elliptic
curve. This point is hardcoded
in the description
now. Then you take the X content
of this point.
You take the file usually 256
bit, you discard the top
sixteen bits
and output rest.
No, you take the rest and call it s
and then s times Q
Now from this thing, you do the same
procedure and then you actually output
it. Now you've taken your
randomness and gotten some
other randomness from it.
So 256 minus six to
12 to 40 bits of animals,
however, you want to get more randomness
out of it. So you also feed this s
into the feedback and now
s changes to T because you
always zero.
And so you compute the.
Next time the next calling off the
previous point times point and
keep on running each time you all put
the 140 bits
now at the time that this was designed.
The oldest reference I could find was a
public draft, which was
given at a nice workshop in June 2002.
The workshop was July 2004.
The drafts from two thousand four in
June.
At that point, this has been already
discussed in NC, but I haven't been able
to track down any and the only documents
of it. So at that point, Nest was
inviting people to look
at this and say how great it is because,
hey, look, I like
optics.
But at that point, I already existed
ahead of the curve.
So she was like, This is not how we
designed to curve and no generators.
We had a bunch of those out there
with security proofs and
ideas, in particular the idea that
you never, ever output more than half
of the bit length.
So out of the 256 bits, you should never,
ever output more than Howard Tate.
And there's just no way that these 240
bits will be anywhere well distributed.
But it sounds very nice.
They have a no theoretical problem there,
and we all know that this gridlock
problem on elliptic curves is hard.
So if you're given these points P and Q
and optic curve, then you
can have a heartiness relation to the
heart problem of finding an integer
so that this integer times p
gives a point. Q
now, soon
after, lots of papers came out say
This is really not pretty.
This is not how it should look like.
So that was because sanctioning saying
that the output by its sequence is
biased, which is absolutely not a
surprise. As I said, we should never have
output more than half of the bits of such
a thing.
And if you output too many bits, then you
get a bias.
He was saying that, OK,
he doesn't know how to turn this into a
real break, so you have to have a quote
from some official input that he gave to
the standardization process.
But the point is, if
you take all this pain and suffering of
taking such a slow random generator
because you want something provable,
secure, then you shouldn't have anything.
That's an outcome that's biased.
They should not be accepted and generated
based on no theoretic assumptions.
About the same time Dan Brown was Soji.
Com was publishing something
which just looks like a security proof.
So he was showing like, OK, if you assume
that P and Q are random,
then this thing is secure
where you said that the output sequence
as points is secure and then also
show similar to the goosed.ie.
And some of these papers were later
merged. He shows that
there is a bias if you look at this as a
bit sequence.
He already has a statement in there
that this proof makes essential use of
cubing random.
If anybody knows an integer D, so
the D Times Q is P.
Previous slide.
We had eight times as Q,
do you know the group order?
So if you know this from the from the
description, you also know the D here
they are interchangeable.
They're not the same.
One is one over the other.
The the product with two is one model,
the group order.
So if you have one, you get the other.
And he concludes that if you would know
such a scalar, then you would have a
distinguishable.
It distinguishes this kind of thing where
you like, yeah, OK, you don't want to
have a distinguished you don't want to
have a bias, but it's not really a break
to colleagues from my University
Eindhoven.
And I do think I'm very school.
Markus, also 2006, and
Mason Note Tune is
saying that the output bias
is even worse than what looked like in
the previous two papers.
And I was talking with him lately because
of some news.
And Barry told me, Yeah, he got this
reply from an honest
saying that, well, they can't
really remove this R&B anymore
because it's already being used.
Well, this is a little strange
because they were asking for
comments before making it a standard.
In 2006, it was not yet a standard, they
were asking, Hey, should we have this as
a standard, but then those sorry, the
counter move it because it's already
implemented.
Year later, corruptors 2007 a RAM
session, then Asimov and
Neil Ferguson were giving a talk and
showing that it's not just the
distinguished, but even a back door.
So if anybody knows this d, then they
can predict the sequence.
It's a very small computation and you can
just get the next point.
Now, the new standard differs from
the NZ standard in that there is an
appendix showing yes,
you can choose your own points.
You do not have to use this
P and Q that we publish here, but
the standards is full of rules of saying,
Well, you should use these as much
better. If you don't use them, you have
to go through all kinds of hops and prove
that these are randomly
generated by at least
the sound allows it.
Now, if you look at
what do we know now?
So September five, suddenly there was the
publication of the Borland program,
which as one of the topics, has
to insert vulnerabilities into commercial
encryption systems, IT systems, networks
and communication devices used by
targets, and also
to influence policy standards and
specifications for commercial public key
technologies.
So apparently, the NSA was
having its fingers in the game, and
soon after that, the New York Times
actually names the Dulles
even number generator as
a candidate for this.
But honestly, at that point I was like,
Yeah, but nobody will use this.
I mean, we all said in 2006
and 2007, don't use this.
I mean, after the backdoor thing, it was
really, really clear that nobody should
ever possibly useless.
Now when you look at I put a URL
on the slide,
there actually quite a few companies that
have FIPS validation for their
R&D implementation of this system.
Most interesting part is when you look
at this list, there are very few of
them which have it enabled as a default,
but our ABC library
is one of these.
Now on the positive side
at that point had enough public pressure
to open the discussion, and
they're now recommending against using
this particular orange.
And they're asking for comments of
people, and I think the comment is pretty
clear. No, we do not suggest to continue
using this system.
And ours has also stated that
based on this recommendation, they now
recommend that users change it
from the default and the new library
would be changed.
Oh, oh, sorry, I feel sleazy.
Actually, we did some fun, we have some
limitations now.
I said before that out of the 256 bits
of code and we only give you 240
when you've now read the standard, well,
you know that this is likely a backdoor
and likely something where the NSA wanted
to use it then.
It's very interesting that it goes
that you should not add extra randomness.
This is an R&D.
You should think that randomness is a
good thing here, but it very
clearly points out that no, no, no, no,
please make sure to use the find
representation, which is unique for
point. Do not give us anything that we
cannot figure out how it works.
So here is how the attack works.
I assume that you have the secret.
Do you have the and it's a backdoor?
Then you can compute.
You can expand.
This candidate are the 140 bits
to a point for every
candidate.
Sixteen bits. You have a 50 percent
chance. It works.
If it doesn't work, then move on to the
next one.
So if you are missing 60 Minutes to turn
16 out of those, two to the 15
will work for the next few steps.
So then you have to do it to scale on
modifications.
Check with your and as secret vector the
next point.
Compute the exponent.
Extract the next scalar
and check whether the next output
actually matches the output you've seen.
If it does, it's very, very likely the
right point.
If it doesn't, OK, move on to the next
one. Now we've implemented this
and on a single call on a
kind of recent process, it takes 20
seconds to go through all 16
bits.
If you removed more words, if you moved
like eight bits extra, then it takes
eighty five seconds, still pretty doable
to check all of them. But if you remove
like thirty two bits, then starts
being painful.
But the NSA has a few more than just one
core.
So if you start with like 64k, it is
and you're down to the 20 seconds
now. But, you know, in 2004,
2005, this looks like a big computation.
So yes, the standard is
very clear and says for performance
reasons.
Hey. 20 seconds with a 15 day, that's
performance reasons for performance
reasons. The value of what length should
be set to the maximum value is provided
in table for. Do not do not think
of giving us fuel. Ibbetson in the 140.
OK, so
later in September 2013,
people are starting to look at more of
these nest standards.
It's not just the easy dual.
Do you see the R.B.G?
But there is, for instance, the SHA three
competition.
Now there's a long history of
competitions in crypto, and it's one of
the best ways that we have having an open
competition.
Well, maybe it's not completely open if
Nest is then declaring who the winner
is. But if you look back at the ace
competition and say
the shot three competition, then there's
been pretty widespread support.
I mean, the algorithms that were selected
for ACE and four shot three
listen to Bruce Schneier, for instance,
he had one of the competing candidates
for Sha three, and he said, yeah, their
choice for Sha three was fine and same
thing for everybody.
Well, maybe there are a few complaints,
but but everybody feels like these are
reasonable algorithms and nobody's
been seriously criticizing the the
the choices, except after
the SHA three competition finished.
It's been more than a year since the SHA
three winner cut check was announced
after the competition finish, and this
has been writing all these detailed
standards for OK.
What exactly is SHA three compared
to this sketch act that the competition
was about now for comparison, as
was submitted 15 years ago or
something, whenever the deadline was a
few years of competition, people trying
to break it and then the standard was
exactly the same algorithm that was
submitted 128 bikies and
256 or 192 bit case.
They threw away some options, but they
kept the core options with zero
changes. And now, well, Marcia
was tweeting 19th of September this
year that this is proposing
to weaken Catch X, the winner of the
SHA three competition, far below what was
Krypt analyzed during the competition.
Now the weakening is something
like they were taking, for instance, some
256 bit security options
and turning them into 128 bit
security. Probably not a problem, but the
process is kind of scary.
We like these competitions because
everybody can see what's going on, and
at the end, there's never been a case of
an algorithm being selected that was
unpopular and lots of complaints about
it. It's always been popular algorithms
being selected, so the cryptographic
community is happy with as much Sha three
as it finished the competition.
And that's not the same as what next in
August and September was talking about
standardizing.
So after this list has said,
after a whole lot of public outcry,
they've said, Oh, oops!
Yeah, maybe that wasn't the best idea.
Other nice stuff, so.
Back in May this year, we then they
were giving a talk, which you have titled
The Security Dangers of the nysc.
So this was a talk about it looked a
curve cryptography.
And we are going through the current
suggestions of the newest pictures
of the two six three reference on
ensuring that
it's really hard to implement and
properly that if you want to implement
the curves in a way that you don't have
failures who don't have such strong tax
chances are you're doing it wrong.
We also had in there one slide saying,
Oh, by the way, the provenance of these
curves is kind of questionable.
The NSA generated and, you know,
if the NSA would know something which
happened just like with a chance of, say,
one over 10 billion, 10 million,
they could have tried hashing lots of
different seats until they find one
off the curves. That's weaker.
Now we put those slots online, and sure
enough, Matt Green pops up and saying,
well, what if this or A.
A. A weakness instead of using
a trapdoor, he says, Oh, a weakness.
You know, this might be nice to us and
actually want to protect us.
This was made.
In September, he tweets
saying discussion was hash breaker from
when I was younger and more naive,
pointing to this discussion.
Now we put this into
the September part of the talk because
you and I were working on a page
called Safe Curves How
to choose safe elliptic curves
for using cryptography.
And we going on this page through all
the known security criteria for
elliptic curves. And we have the machine
verified.
We also include like usability questions
like how easy is it to implement them in
a slideshow in a secure way.
We have a map called alligator,
together with an cousin of handbook
where you want to map a string to the
curve point and back.
And we also introduce a new curve, which
sounds circle is most likely going to use
for their south mail system.
If so, for the somphone system,
we also have a comment in there about
whether these curves could be backdoored
so we can go to save curves that Seattle
Typekit Otto you find
on the first page.
This overview green as good
grid is not good,
and they're just not many curves which
have a whole row of green.
In particular, the nice curves do not
have a whole row of green.
Another big development in elliptic curve
cryptography this year, I mean, it's not
really this year, but it's sort of this
year is bitcoin.
So bitcoin is everybody's
favorite cryptocurrency, and
this was not the year that it was
invented, but this is sort of the year
that it went mainstream, as shown by
this plot of the bitcoin exchange
values to real money.
I, you know, I'm sure
many of you own bitcoin and everything.
I think I find it very interesting
because bitcoin has suddenly got the
entire world like normal people talking
about are coming cypherpunk future,
where we have decentralized,
you know, pro libertarian.
Everybody is free to implement all this
strong cryptocurrency they want.
It's very interesting. This is sort of
the Napster moment for cryptocurrency.
So on a sort of on
a cryptographic note.
So, OK, so
bitcoin relies on elliptic
curve, the elliptic curve DFA algorithm
for its signatures.
Every transaction that you do is signed
by your address,
which is your key.
And the DSA
algorithm and the Elliptic Curve DSA
algorithm.
These are nice standards, and they come
with a little sort of
bomb that is built into
these standards. It's a little landmine
that if you happen to trip across, it
will cause the algorithm to blow up in
your face, which is that if you use bad
randomness to generate your signature,
suddenly your private keys revealed
strange property
and it's possible to get around this.
But if you don't know how to get around
it, then you might have an accident, as
hundreds of people did with their
bitcoins.
And so there is some
enterprising soul
with this bitcoin address
who has been watching the blockchain for
the past nine months or so
and stealing bitcoins from people who
happen to use bad randomness in their
bitcoin transactions.
This person now has more than 59
bitcoins.
Some of these ended up being due to an
Android Java random number generation
vulnerability that was disclosed in
August.
Not all of them are.
So it's interesting what happens
when you suddenly have irreversible
transactions that
are secured only by
crypto standards and implementations
from random people on the internet.
OK, so muscular.
One of these entertaining code names for
NSA HQ programs, everybody's
seeing this wonderful picture where
in the middle, at the bottom you can see,
SSL added, Maybe I can point to it here
just in case anybody hasn't seen it.
This is some NSA person writing SSL
added and removed here and putting a
little spy kind of a smiley face in the
middle. And that's the Google Front end.
So SSL is only outside of Google.
At the time, this picture was drawn.
And then inside, hey, NSA can just
as the part on the right says, traffic
and clear text here.
Google's just sending all their traffic
and clear text. They've been changing
this after seeing this picture.
The official Google statement about
this picture said We are outraged.
So that's already pretty serious.
The unofficial but very public
Google statement about this said, Fuck
these guys.
They.
The lesson that we've added at the bottom
there is even if there's problems with
SSL, you know, it's a whole lot better
than sending around clear text, so
deploy something, you know, even if it's
better, even if it could be better, it's
it's going to be better than clear text.
Meanwhile, at the NSA.
Also, meanwhile, at the NSA, here's
another slide from this NSA presentation
that I went to.
It's a little bit blurry from the
picture, but there's is kind of like this
diagram of cyberspace
on a railroad track
and.
One rail is labeled protecting and
maintaining privacy and civil liberties,
the other rail is labeled safeguarding
wealth and treasure.
This is the strangest mixed metaphor I've
ever seen,
but I'm pretty sure that it means that
all of us in cyberspace are being
railroaded by the NSA.
Oops, I forgot this is my slide.
Yeah, so something else that happened
this month, we're almost at the end of
the year here.
And sorry for anybody who had crypto news
that we left out. We have limited time,
so a few minutes left.
Though so exceed CD is one of the most
popular ways to encrypt your hard
drive. If you're doing that, which I do,
and I hope actually I'm curious how many
people here are encrypting their hard
drives.
All right. All right.
All right, one of the original standards
for hard drive encryption.
Encrypting each block is XY B
and it actually has two versions.
The second version, version two.
Well, this paper from Chakraborty and
Hernandez Mendez and Sarkar 4th
of December this year is
saying x kbe is not secure
as a test, as is the sort of thing
you say to make sure that people who
haven't been in the community aren't
allowed to write papers.
If you say it's not secure.
Encrypting your hard drives, then
everybody laughs the paper out of the
system. You have to know to say it's not
secure as a T.
Anyway, this is saying it's not secure as
a disk encryption system.
There's an easy attack, faulty padding
scheme, blah blah blah.
Proof of the security theorem is wrong.
And then the really funny thing is this
again, this is a second version.
The first
version was thrown away because
the authors of X CD said
that they were modifying it to help the
analysis to enable easy analysis.
Maybe that means to make the crypto
analyst job easier.
Somehow, they changed XKB in a way
that, well, they said, would actually
allow a security proof.
But the security proof was wrong and
they made it weaker.
Actually, the original X CD from
everything we've seen now is stronger
than the modified disk encryption method.
Now there's lots of even worse ways to
encrypt your disk, but this is kind of
scary that we have these provably secure
standards where the proof is wrong and
it's still standardized and lots of
people are using it.
I haven't seen any comments from the
authors of KB about this attack.
Another attack that happened is acoustic
attacks.
There's a long history of power analysis
attacks.
This is watching the power consumption
of your CPU or whatever your
cryptographic devices, smartcard or
something. And acoustic
attacks are doing power attacks where
they're reading out the power signal
instead of through a wire watching
voltages or something on the wire.
They're watching the home of a
capacitor or something else that's making
noise, and that noise gets sent through
the air. If you look at this picture, you
can see some sort of cool parabolic
microphone here focusing on a
target ThinkPad over on the right side.
And so from a considerable distance,
they were able in one hour to find
a four thousand ninety six bit GPG
key. The one hour was the key was
being used for. Somehow, they were
forcing the machine to do a lot of
descriptions using that RCA key, and then
they got the four thousand ninety six
secret bits.
Now you might think, OK, I can look
around the room. There's nobody who's
that's that close to me with a
microphone.
But they also
demonstrated the same attack,
using the totally wimpy
microphone on a typical smartphone.
And again, one hour they managed to get a
four thousand ninety six bit key, though
they hear is Jenkin and Shamir and
Troma.
So another thing that happened in
December was that President Obama
has personally picked NSA review panel,
released its transparency report
on the NSA.
This is a 300 page document, so it's a
little bit difficult to get through in
the couple of minutes that we have left
in the talk.
But here's one interesting paragraph
which appears near the end in one of the
appendix and appendices,
which is talking
about specifically cryptographic
vulnerabilities.
So I have for ease
of reading here, underlined
all of the weasel words
that are being used in this paragraph.
Upon review, we are unaware
of any vulnerability created by the US
government in generally available
commercial software that puts users
at risk of criminal hackers or foreign
governments, not our government.
The only foreign ones decrypting their
day, it goes on.
So yeah, under this program
is the only thing missing here.
So just to illustrate
this, here's a list of, you
know, some wild speculation, some of
it perfectly reasonable,
like the first one and some of it totally
unreasonable, like the last one.
That is not ruled out by this paragraph.
The NSA could have backdoor the dual OECD
RBG, and only they have the key.
They could have backdoor the NYSC curves,
and only they have the key.
They could have introduced vulnerabilities
into cryptographic software like open
SSL, which is free software and not
commercially available.
They could have introduced
backdoors into Windows, macOS
and RedHat, which are only three
commercially available operating systems
out of the hundreds that are on the
market.
They could have introduced backdoors into
cryptographic hardware because that's not
covered by the commercially available
software that they were talking about
things like the Intel Hardware Orange
or the iOS instructions, or
they could have modified 100 percent of
the general generally available
commercial software to disable encryption
whenever possible.
And you know, finally, they could have
built in a key escrow feature
into a yes that allows lawful
access to any as encrypted
data anywhere.
How are we supposed to know with that
kind of denial?
Now, what we learned soon after
was that RSA has accepted a payment
of 10 million U.S.
dollars in round 2004
Spec. So it's not just one payment, but
multiple payments in order to
implement the beautiful, easy dual
round number generator that I mentioned
before. And so
it was now disclosed that they actually
got money for having this and be saved.
This also explains why in 2006,
Nissan could say no, sorry, we can't
remove it anymore has already been
implemented.
RSA issued a nice
statement saying, Sorry, we didn't know
this was the good guys.
How could we have guessed that there was
anything fishy? You know, everybody
was so excited about love tacos at that
point.
Now, all right.
Maybe 2004. That was correct, but it
certainly wasn't correct any more in 2006
or 2007, and they kept it in
there until September 2013.
Now, if you pay attention, I put a little
public or commonly stated
history of the dual duality earlier.
There's one very interesting thing from
2005.
Fall January 21st, 2005.
Provisional patent later on.
It's a patent by Dan Brown and Scott
Winstone from Sir to come
about elliptic curve and generation.
Now this is not the patent.
Explain the duly c rg.
They actually explicitly refer to NC
for explaining for for defining this.
However, if you look at it already
in the abstract.
So the patent was granted
in 2007, even before the
0:48 session, and the patent goes
in length about how
to use the relation between QUE
as an escrow facility.
It even goes into details of
how this escrow facility could be used
in a ship traffic
that you would guess most of the bits
from the nonce from the server, which
is being sent there.
So
there's also a part one to this patent,
which is saying, Oh, if you want to use
the appendix of this standard, then
you should pay us royalties because it
also goes into details of how avoid
this escrow feature, which
makes it very clear that nobody would
ever implement this.
It also gives a very nice whitewash to
to come.
Because they say, look,
we told the world about it, nobody wanted
to listen. We even explained how to
how to use it.
And at the same time, it makes very clear
that nobody will ever use the protection
against the backdoor.
So whoever has the key to this backdoor
will keep on being able to decrypt
all traffic.
Thank you for the attention, I guess.