All right, folks. Thank you so much for your patience. Welcome to Crypto and Privacy
Village. Great to have you here as we wrap up a fantastic Saturday of the Con. And we have a
fantastic talk by Evgeny Sidorov. He is an InfoSec engineer at Yandex.ru. You might
recognize that. And the talk is yet another password hashing talk, which will not be just
yet another password hashing talk. Give it up. Okay. So hello, everyone. And thank
you for coming to my talk. My name is Evgeny Sidorov. And as that man said, I'm from
Yandex. Yandex is a search engine in Russia. And actually, Yandex, I want to give a few
words about the naming of this talk. So Yandex means yet another indexer. So yet another
internally at Yandex, we refer to, we usually use prefix yet another for something related to
Yandex. So this talk is a result of the work I've been working on at Yandex on password
hashing. So before I start, I want you to make out my accent. I'll be referring to several
algorithms. So the first algorithm I pronounce like yes grip.
The second algorithm I pronounce like s-grip. And the third algorithm I pronounce like b-grip.
So I hope you understand my accent and make out what I say. Here is a short agenda for
today. So I'll start with a short introduction into password hashing. But in password hashing,
I'll be talking about algorithms. I'll be talking about protocol designs. And I'll draw
some conclusions. And today, I'm also going to share some code with you. Let's go for
introduction. So I know some people think that passwords are dead. But the reality is
that passwords are still alive. And in my opinion, they will probably always exist.
Because OK, if we switch for some kind of maybe public key authentication, anyway, we
need some passphrase to protect our private keys. If we use de facto authentication, we
need something that user keeps in his brain and so on.
So actually, password hashing, there are at least two stories around password hashing.
The first type of password hashing, it's non-interactive operations. For example, it's password based
encryption when you take your passphrase, run, put it into key derivation function,
and get the key to encrypt your crypto container or some data. And the second story around
password hashing is encryption.
Interactive keys. Interactive case, it, when you have a, for example, web service, and
a user comes to you, he shows you his username, his password, and you hash this password to
authenticate him. So this talk is about interactive case, is about online operations. And actually,
these cases are different because when you run a web service, you can't actually afford
bigger parameters.
You can't actually spend much time on password hashing in your web service because you'll
be suffering from computational denial of service. Your users will be suffering from
long latencies and so on.
As usual, we have an attacker and defender. Defender uses traditional multi-core service
CPUs, just because we usually run web services on such kind of CPUs. And the attacker can
use, in other words, the same kind of CPUs as the attacker. And the attacker can use,
in other words, the same kind of CPUs as the attacker. So that's the kinds of hardware
to try to crack your password hashes.
And in my opinion, you know, types of hardware, it's GPUs, FPGAs, and ASICs. And in my opinion,
GPUs is the most important case because there are a lot of people who do cryptocurrency
mining. There are a lot of people who play computer games, and they already have GPUs
ready to crack your password hashing database. FPGAs, you need to find a cluster of FPGAs.
You need to sort it down. Some RAM. You need to find a cluster of FPGAs. If vpgs is important,
You need to, it's expensive.
If we talk about ASICs, you need to find a manufacturer
and order some ASICs and so on.
It's just something that's really expensive.
So I'll be talking about, I'll go to algorithms.
So the role of password hashing algorithm itself,
it's just to be a last hope.
So you shouldn't, when you're building your security system,
you shouldn't rely on, solely rely on
password hashing algorithm itself.
You should consider it to be as a final hope,
as a last security measure,
because in case of total compromise,
the good password hashing algorithm will allow your users,
will give your users some time to change their passwords before
an attacker crack all these hashes
and steal their account, their data, and so on.
So strategies beforehand.
Kind password hashing algorithms are to optimize as much as possible,
to optimize algorithm as much as possible for CPU
and their capabilities, their RAM pattern access,
their maybe cache system and so on,
and make GPUs, ASICs, and FPGAs inefficient or expensive,
for example, and exploit their bottlenecks.
And when researchers designed all these algorithms,
algorithms, they,
came up to a solution.
It's to use so-called memory-hard functions.
Informally, memory-hard functions,
it's just functions that use RAM,
some amount of RAM to perform computations.
And they're designed in the way that it's very hard
to trade the memory to computations.
So, for example, if you,
obviously you can always trade memory to computations,
but, for example, if you're making an algorithm,
memory-hard means that if you do,
if you act this way, the amount of computations
will be very enormously high, enormously expensive,
so it becomes pointless to do such time memory trade-off.
The first algorithm I wanna tell you about is YesCrypt.
And YesCrypt was designed by a solo designer,
also known as Alexander Pislak,
and this algorithm actually got special recognition
from Password Hashing Competition Committee.
And the author claimed that this algorithm
is optimized for password hashing at scale.
So it optimized for use,
for using in web services.
YesCrypt is based on AsCrypt,
and actually it fixes some time memory trade-offs in AsCrypt.
And it introduces,
it doesn't only read the memory,
it also performs random rewrites of memory
to increase complexity of,
to increase the amount of free computation
if you want to apply time memory trade-offs
like that was in AsCrypt.
It also replaces Salsa 28 in the AsCrypt
with custom pvx form transformation
to achieve bcrypt-like resistance to GPUs.
So, you know, bcrypt, it allocates four kilobyte of memory
and performs four byte lookups.
And actually, if you run it on a GPU,
it will perform, it will be slow because,
for example, in NVIDIA GPUs,
if you want to access global memory,
and if you want to read four bytes,
actually 32 byte will be fetched,
and this technique just exhausts memory bandwidth.
So it makes a lot of GPU cores just idle and do nothing.
And YesCrypt also introduces, you know,
introduces some tweaks and parallelism
and makes it,
makes it, allows for more fine-grained tuning.
So you can independently tune memory,
computational cost, and so on.
So here is a diagram,
and you can see primitives that were fixed
by YesCrypt authors.
As you can see, smix was modified,
and random rewrites were introduced,
and tweaks and parallelism were done,
and pvx form was, is displayed.
It is a replacement for Celsa 2028.
So what is a pvx form?
It's optimization for a low-memory case.
It uses, as I said,
it's an attempt to employ ideas from bcrypt,
and it uses 12 kilobyte S-boxes,
and it's very friendly to L1 CPU cache.
It also uses integer multiplications
because that operations have high latency
on FPGAs and ASICs,
and it's really friendly to SIMD instruction
like ECC2, SSS, E3, and so on.
And actually, this algorithm is good to study
because, for example, if you want to plunge
into what had been going on
before password caching computation was launched,
it's a good case to just to study
the difference between S-crypt and YesCrypt.
Here is the pros and cons of this algorithm.
So it's optimized for a low-memory case,
and it allows bcrypt-like resistance.
It also introduces some tweaks in protocol design,
and I'll be talking about it a bit later.
And so it fixes S-crypt drawbacks,
but the main drawback in this algorithm
is that it's pretty complex.
It's pretty complicated.
It's hard to understand all this algorithm,
and there is no resistance to side-channel attacks.
So internally at Yandex, we opted for Argon2.
Argon2.
It's a good algorithm.
It won password caching competition,
and it's designed to be simple, tunable, and secure,
and there are three modes in this algorithm.
The first mode is data-independent mode.
It means that all the RAM access pattern
doesn't depend on password and salt.
The second mode is data-dependent mode.
It means that RAM access pattern
depends on password and salt.
So the first mode, independent,
gives you resistance to side-channel attacks,
but it's prone to time-memory trade-offs.
The second mode gives you better resistance
to time-memory trade-offs,
but it's prone to side-channel attacks.
And the third mode, in my opinion,
is the most interesting mode, is ID.
It's a combination of these two modes,
and...
It's some kind of mitigation of side-channel attacks
and gives some resistance to time-memory trade-offs.
Here is a short diagram of how it works.
So it takes your password, salt, secret,
and additional authentication data,
puts them into Blake2B function,
allocates several lanes of RAM,
then performs some computations on this RAM,
then takes the latest blocks,
sorts them together,
and puts them to Blake2B-like hash function.
The main difference is the function with Blake2B
is just it has variable length.
It's variable length hash function,
so it can give you tags with different lengths.
So, for example, you need a short tag,
you'll get short tag.
If you need a big tag, you'll get big tag.
So, and...
So, and...
Returning to Argon2ID mode,
here you can see a diagram.
So during the first pass,
over all the lanes,
Argon2 in ID mode acts as an I,
in I mode and then switches to D mode,
so acts as data-independent
and then switches to data-dependent mode,
and this provides mitigations
against side-channel attacks.
Here you can see round function from Argon2.
You can see the diagram is...
It's pretty clear.
It's really simple.
It's really easy to understand how algorithm works.
And the core function of this is
Blamco function.
It's modified Blake2B function.
And just as you can see,
integer multiplications are added
to make it harder to make...
It adds some resistance to FPGAs and ASICs
because integer multiplication
has...
It's a operation that has more latency
on FPGAs and ASICs.
So here are some design principles
behind Argon2.
It operates on one-kilobyte memory blocks
and it's optimized for x64.
It's extremely friendly
to some SIMD instructions
like SSE2,
SSSE, and so on.
It's some advanced instructions
in modern CPUs.
It fills out memory
very quickly
and it uses Blake2B
and Blamco as underlying primitives.
So,
actually,
there is no...
especially...
Argon isn't especially optimized
for low memory usage
and if you run a web service,
actually, you can't afford
bigger parameters of Argon2
because you can suffer
from computational denial of service
or your users
will suffer
from big latencies and so on
because, for example,
if you want to authenticate
in, say, a mobile application,
you need to set up TCP handshake,
then you need to set up TLS handshake,
then you need to wait
until your password caching algorithm
will process password
and username.
It irritates users.
They don't want to wait and so on.
So,
one of the ways
to cope with this
is to optimize Argon
as much as possible
and there are at least
two implementations of Argon2.
There is an official Argon2 implementation.
You can find it in
password caching competition repository.
It uses a much native option to...
This option tells
a compiler to optimize
this algorithm as much as possible
for the current CPU
on which the compiler
is running.
Using this option, you can easily
run up against illegal instruction exceptions.
For example, if you compile code
on one CPU type and just move it
into another CPU type,
you can easily get an exception.
I don't think you want to get it
in a production environment.
If you compile it
in some kind of compatibility
way,
it will cost you
at least 15 or 20%
of performance.
So what we did,
we made our own implementation.
This implementation
features the technique
that is called Runtime CPU Dispatching.
We run CPU ID
instruction and switch
and take the most optimized
version of the algorithm
for this particular CPU type
and we do it in runtime.
You'll get maximum performance
on your current CPU type
and it makes
deployment easier
and
so
I think Runtime CPU Dispatching
is a good way
to get maximum
performance on different
types of
CPUs.
During the work on this algorithm,
I also created AVX2 optimization
and its
instruction said that
Runtime CPU Dispatching
was
a lot of
modern CPU support
and you can see
in a couple of slides,
you'll see the benefits of this.
So we named our implementation
Argonisha,
that means Argon and Russian
suffix "-ish".
Russian suffix "-ish
shows that it's something
enormously bigger that scares
small children and so on.
So you can just
get the code and review it yourself.
Okay, here is
some results of the benchmark
and you can see that AVX2 implementation
outperforms all the other optimizations.
Actually, our library
comes with a simple benchmarking tool
that is similar to OpenSSL
speed application
and you can just take it
and benchmark it yourself.
Okay, and here is
a repository where you can find
the code. It's written in C++ for
14. It uses constant
expression,
partial templates.
It's just a convenient way
to make a compiler do a lot of job for you.
The license is
BSD3 close.
I think it's a very convenient
license. You can do whatever you want.
But if you wanted to modify the code and distribute
it, you just need to wipe out
the mention of Yandex and that's it.
And now
I'm working on AVX512
optimization that was introduced in
the recent Intel Skylake processes.
But as I said,
as I said,
algorithm itself, it's
not a perfect security measure and
you can't afford big
parameters.
And if you rely
solely on the algorithm, offline
attacks are possible. What are offline
attacks? Offline attacks is when
for example an attacker
hacked into your database
dropped all the password hashes,
took them
home and had
some fun with GPUs and
some
cracking software.
So sometimes
there are some
ideas how to mitigate these
and here you can see some ideas.
The first idea is to use local
parameters. The second idea is to use
big ROMs and this idea was introduced
by
the authors of ChiaScript.
You can also use crypto anchors
and the last one is
the most advanced one is to use
partially obvious pseudorandom functions.
Let's start with local parameters.
The idea is pretty simple. Just
add some secret key into
a password hashing algorithm. For example
argon2 can get
a secret key
to its input and
just don't store
the secret key into a database.
Store it in environment
variables of your application or for
example configuration of your application.
SQL injection into
a database in your application
becomes insufficient so if an
attacker wants to steal
all the password hashes
and to crack them at home
he needs to
find a SQL injection
or for example remote code execution
vulnerability in your application and
it's much harder to find.
Let's
talk a bit about big
read-only memory.
The authors of
EScript
introduced
the idea of using big ROMs.
For example you allocate a big
area of memory and
during the password hashing you perform
random lookups and mix it into your algorithm.
The idea is pretty simple because
for example if you allocate
100 GB of memory it will be very
hard to exfiltrate it and you
probably catch the attacker in your infrastructure.
But
there are some drawbacks because
it's harder
to switch to a new password hashing algorithm
obviously you will live with all
this big
memory area.
At least an additional step in case of
server reboot because you need to
initialize this memory, you need to
check
the integrity and so on and
actually there are ways to amortize
and actually there are
some ways to amortize
this approach.
So
for example you can just divide
this big ROM
into some parts and
scatter it around some web service
and instead of performing lookups in your
RAM you can just make
a network request.
It will be slower but anyway
it can be used to
brute force your hashes.
So crypto anchors
the idea is pretty simple just introduce
just set up a
simple
service, a tiny service
in your infrastructure and it will
do only, it will apply
only to the random function
for example HMAC
and it will be very hard
to hack into this service because it's small
it's tiny you can easily audit it and so on.
But there is
for example if you use HMAC there is
a drawback because you can't just rotate
the key of this HMAC
you will need to
for example if the case
is compromised you will need to switch
to another key and so on.
And the guys from Cornell Tech
introduced a new
new method that they called
it PATH.
The idea is also pretty
simple. I really like the
idea so here you can see
a web service and this
crypto service and you need to
build a pairing
and you get your
hash, password hash
and you perform blinding and then say
send user ID
T means user ID and this
blinded hash to
this PIF service
performs, applies this
pairing with secret key
and return it back
and the web application can unblind
actually
in this case
this PIF service
doesn't see
the hash
of the password
so if
anyone will
hack into this PIF service
he won't get
he wouldn't be able to collect
the hashes of passwords
and this scheme also
can be used
to rotate keys
for example this service
can send a web application
a key rotation token
and it can apply this token
and just rotate the key
just process it's password hashing database
and rotate the key. It is pretty
simple and I think it's pretty cool
and they also
extended this idea
and introduced so called
Pyther PRF
the idea is like those in PaaS
but they also added
zero knowledge proof scheme to prove
correctness of the calculations
and they also adapted the scheme
to be multi-tenant
so let's come to conclusions
ok, good algorithms are not enough
for online password hashing
and you need to
because you can't
you can't afford bigger parameters
and if you rely
only on algorithm you'll be suffering
from for example offline attacks
and so on but there are good approaches
to make up for it so offline
attacks can be turned into online
online attacks
so if you want to afford more parameters
you can optimize performance and
you can for example use our
optimized implementation
and I want to say thank you to
Dmitry Havratovich he is also
with Argon2 and I want to thank
him for all the discussions
about Yescrypt
and Argon2 I want to say thank you
to Alexander Pislak for all the discussions
about Yescrypt and Igor Klymanets
who reviewed the code of
our implementation of Argon2
and just
made some
useful suggestions and
a couple of useful links so if you
want to get more information about Pyther
PRF service here is a link to
the original article
here is once again
it's a link to our
Argon2 implementation
and the last link
it's Pyther reference
implementation done by
the guys from
Cornell Tech so
that's it for today thank you
for coming and thank you for listening
to this presentation so now I'm
ready to take your questions
thank you