1
00:00:00,000 --> 00:00:04,340
All right, folks. Thank you so much for your patience. Welcome to Crypto and Privacy

2
00:00:04,340 --> 00:00:11,100
Village. Great to have you here as we wrap up a fantastic Saturday of the Con. And we have a

3
00:00:11,100 --> 00:00:19,260
fantastic talk by Evgeny Sidorov. He is an InfoSec engineer at Yandex.ru. You might

4
00:00:19,260 --> 00:00:25,300
recognize that. And the talk is yet another password hashing talk, which will not be just

5
00:00:25,300 --> 00:00:40,340
yet another password hashing talk. Give it up. Okay. So hello, everyone. And thank

6
00:00:40,340 --> 00:00:45,720
you for coming to my talk. My name is Evgeny Sidorov. And as that man said, I'm from

7
00:00:45,720 --> 00:00:55,280
Yandex. Yandex is a search engine in Russia. And actually, Yandex, I want to give a few

8
00:00:55,300 --> 00:01:00,180
words about the naming of this talk. So Yandex means yet another indexer. So yet another

9
00:01:00,180 --> 00:01:06,960
internally at Yandex, we refer to, we usually use prefix yet another for something related to

10
00:01:06,960 --> 00:01:13,720
Yandex. So this talk is a result of the work I've been working on at Yandex on password

11
00:01:13,720 --> 00:01:21,520
hashing. So before I start, I want you to make out my accent. I'll be referring to several

12
00:01:21,520 --> 00:01:25,140
algorithms. So the first algorithm I pronounce like yes grip.

13
00:01:25,300 --> 00:01:31,140
The second algorithm I pronounce like s-grip. And the third algorithm I pronounce like b-grip.

14
00:01:31,260 --> 00:01:38,700
So I hope you understand my accent and make out what I say. Here is a short agenda for

15
00:01:38,700 --> 00:01:44,760
today. So I'll start with a short introduction into password hashing. But in password hashing,

16
00:01:44,920 --> 00:01:48,740
I'll be talking about algorithms. I'll be talking about protocol designs. And I'll draw

17
00:01:48,740 --> 00:01:55,280
some conclusions. And today, I'm also going to share some code with you. Let's go for

18
00:01:55,280 --> 00:02:02,560
introduction. So I know some people think that passwords are dead. But the reality is

19
00:02:02,560 --> 00:02:08,820
that passwords are still alive. And in my opinion, they will probably always exist.

20
00:02:09,100 --> 00:02:16,840
Because OK, if we switch for some kind of maybe public key authentication, anyway, we

21
00:02:16,840 --> 00:02:22,220
need some passphrase to protect our private keys. If we use de facto authentication, we

22
00:02:22,220 --> 00:02:24,880
need something that user keeps in his brain and so on.

23
00:02:25,280 --> 00:02:33,420
So actually, password hashing, there are at least two stories around password hashing.

24
00:02:33,560 --> 00:02:38,320
The first type of password hashing, it's non-interactive operations. For example, it's password based

25
00:02:38,320 --> 00:02:46,200
encryption when you take your passphrase, run, put it into key derivation function,

26
00:02:46,500 --> 00:02:54,200
and get the key to encrypt your crypto container or some data. And the second story around

27
00:02:54,200 --> 00:02:55,260
password hashing is encryption.

28
00:02:55,280 --> 00:03:02,660
Interactive keys. Interactive case, it, when you have a, for example, web service, and

29
00:03:02,660 --> 00:03:09,880
a user comes to you, he shows you his username, his password, and you hash this password to

30
00:03:09,880 --> 00:03:18,380
authenticate him. So this talk is about interactive case, is about online operations. And actually,

31
00:03:18,440 --> 00:03:23,680
these cases are different because when you run a web service, you can't actually afford

32
00:03:24,220 --> 00:03:25,160
bigger parameters.

33
00:03:26,280 --> 00:03:31,660
You can't actually spend much time on password hashing in your web service because you'll

34
00:03:31,660 --> 00:03:37,560
be suffering from computational denial of service. Your users will be suffering from

35
00:03:37,560 --> 00:03:39,540
long latencies and so on.

36
00:03:40,160 --> 00:03:45,380
As usual, we have an attacker and defender. Defender uses traditional multi-core service

37
00:03:46,580 --> 00:03:54,100
CPUs, just because we usually run web services on such kind of CPUs. And the attacker can

38
00:03:54,100 --> 00:03:55,140
use, in other words, the same kind of CPUs as the attacker. And the attacker can use,

39
00:03:55,160 --> 00:03:56,140
in other words, the same kind of CPUs as the attacker. So that's the kinds of hardware

40
00:03:56,140 --> 00:04:00,180
to try to crack your password hashes.

41
00:04:00,420 --> 00:04:07,600
And in my opinion, you know, types of hardware, it's GPUs, FPGAs, and ASICs. And in my opinion,

42
00:04:07,620 --> 00:04:11,340
GPUs is the most important case because there are a lot of people who do cryptocurrency

43
00:04:11,340 --> 00:04:18,380
mining. There are a lot of people who play computer games, and they already have GPUs

44
00:04:18,380 --> 00:04:22,940
ready to crack your password hashing database. FPGAs, you need to find a cluster of FPGAs.

45
00:04:23,720 --> 00:04:25,140
You need to sort it down. Some RAM. You need to find a cluster of FPGAs. If vpgs is important,

46
00:04:25,140 --> 00:04:27,840
You need to, it's expensive.

47
00:04:28,200 --> 00:04:32,300
If we talk about ASICs, you need to find a manufacturer

48
00:04:32,300 --> 00:04:34,900
and order some ASICs and so on.

49
00:04:34,960 --> 00:04:37,360
It's just something that's really expensive.

50
00:04:38,560 --> 00:04:42,400
So I'll be talking about, I'll go to algorithms.

51
00:04:43,220 --> 00:04:46,140
So the role of password hashing algorithm itself,

52
00:04:46,340 --> 00:04:48,800
it's just to be a last hope.

53
00:04:49,060 --> 00:04:51,660
So you shouldn't, when you're building your security system,

54
00:04:51,660 --> 00:04:53,700
you shouldn't rely on, solely rely on

55
00:04:54,480 --> 00:04:56,060
password hashing algorithm itself.

56
00:04:56,400 --> 00:04:59,860
You should consider it to be as a final hope,

57
00:04:59,960 --> 00:05:00,900
as a last security measure,

58
00:05:01,040 --> 00:05:03,700
because in case of total compromise,

59
00:05:03,940 --> 00:05:06,460
the good password hashing algorithm will allow your users,

60
00:05:06,700 --> 00:05:11,400
will give your users some time to change their passwords before

61
00:05:11,400 --> 00:05:14,900
an attacker crack all these hashes

62
00:05:14,900 --> 00:05:18,360
and steal their account, their data, and so on.

63
00:05:19,980 --> 00:05:21,640
So strategies beforehand.

64
00:05:21,660 --> 00:05:26,220
Kind password hashing algorithms are to optimize as much as possible,

65
00:05:26,320 --> 00:05:28,660
to optimize algorithm as much as possible for CPU

66
00:05:28,660 --> 00:05:32,680
and their capabilities, their RAM pattern access,

67
00:05:33,100 --> 00:05:35,280
their maybe cache system and so on,

68
00:05:35,400 --> 00:05:40,020
and make GPUs, ASICs, and FPGAs inefficient or expensive,

69
00:05:41,040 --> 00:05:46,180
for example, and exploit their bottlenecks.

70
00:05:46,320 --> 00:05:49,720
And when researchers designed all these algorithms,

71
00:05:49,780 --> 00:05:51,180
algorithms, they,

72
00:05:51,660 --> 00:05:53,280
came up to a solution.

73
00:05:53,360 --> 00:05:55,880
It's to use so-called memory-hard functions.

74
00:05:56,260 --> 00:05:58,040
Informally, memory-hard functions,

75
00:05:58,200 --> 00:06:02,180
it's just functions that use RAM,

76
00:06:02,440 --> 00:06:05,860
some amount of RAM to perform computations.

77
00:06:06,080 --> 00:06:08,840
And they're designed in the way that it's very hard

78
00:06:08,840 --> 00:06:11,540
to trade the memory to computations.

79
00:06:11,700 --> 00:06:12,620
So, for example, if you,

80
00:06:12,720 --> 00:06:17,180
obviously you can always trade memory to computations,

81
00:06:17,260 --> 00:06:20,700
but, for example, if you're making an algorithm,

82
00:06:21,660 --> 00:06:23,600
memory-hard means that if you do,

83
00:06:23,720 --> 00:06:26,420
if you act this way, the amount of computations

84
00:06:26,420 --> 00:06:30,960
will be very enormously high, enormously expensive,

85
00:06:31,100 --> 00:06:37,340
so it becomes pointless to do such time memory trade-off.

86
00:06:37,740 --> 00:06:41,720
The first algorithm I wanna tell you about is YesCrypt.

87
00:06:42,240 --> 00:06:49,380
And YesCrypt was designed by a solo designer,

88
00:06:49,520 --> 00:06:51,340
also known as Alexander Pislak,

89
00:06:51,340 --> 00:06:53,680
and this algorithm actually got special recognition

90
00:06:53,680 --> 00:06:55,860
from Password Hashing Competition Committee.

91
00:06:56,280 --> 00:06:59,620
And the author claimed that this algorithm

92
00:06:59,620 --> 00:07:01,700
is optimized for password hashing at scale.

93
00:07:01,900 --> 00:07:04,480
So it optimized for use,

94
00:07:05,260 --> 00:07:06,980
for using in web services.

95
00:07:07,880 --> 00:07:10,020
YesCrypt is based on AsCrypt,

96
00:07:10,140 --> 00:07:14,320
and actually it fixes some time memory trade-offs in AsCrypt.

97
00:07:14,460 --> 00:07:16,120
And it introduces,

98
00:07:16,680 --> 00:07:21,140
it doesn't only read the memory,

99
00:07:21,140 --> 00:07:23,720
it also performs random rewrites of memory

100
00:07:23,720 --> 00:07:26,460
to increase complexity of,

101
00:07:27,700 --> 00:07:29,660
to increase the amount of free computation

102
00:07:29,660 --> 00:07:33,640
if you want to apply time memory trade-offs

103
00:07:33,640 --> 00:07:35,800
like that was in AsCrypt.

104
00:07:35,900 --> 00:07:40,120
It also replaces Salsa 28 in the AsCrypt

105
00:07:40,120 --> 00:07:41,640
with custom pvx form transformation

106
00:07:41,640 --> 00:07:44,280
to achieve bcrypt-like resistance to GPUs.

107
00:07:44,440 --> 00:07:50,520
So, you know, bcrypt, it allocates four kilobyte of memory

108
00:07:50,520 --> 00:07:52,160
and performs four byte lookups.

109
00:07:52,340 --> 00:07:54,500
And actually, if you run it on a GPU,

110
00:07:54,820 --> 00:07:58,900
it will perform, it will be slow because,

111
00:07:59,100 --> 00:08:02,200
for example, in NVIDIA GPUs,

112
00:08:02,200 --> 00:08:04,520
if you want to access global memory,

113
00:08:04,740 --> 00:08:06,900
and if you want to read four bytes,

114
00:08:07,100 --> 00:08:09,880
actually 32 byte will be fetched,

115
00:08:09,900 --> 00:08:12,540
and this technique just exhausts memory bandwidth.

116
00:08:12,820 --> 00:08:17,260
So it makes a lot of GPU cores just idle and do nothing.

117
00:08:18,420 --> 00:08:20,500
And YesCrypt also introduces, you know,

118
00:08:20,500 --> 00:08:22,100
introduces some tweaks and parallelism

119
00:08:22,100 --> 00:08:23,760
and makes it,

120
00:08:24,880 --> 00:08:29,260
makes it, allows for more fine-grained tuning.

121
00:08:29,540 --> 00:08:31,680
So you can independently tune memory,

122
00:08:32,020 --> 00:08:33,260
computational cost, and so on.

123
00:08:33,720 --> 00:08:35,100
So here is a diagram,

124
00:08:35,260 --> 00:08:38,000
and you can see primitives that were fixed

125
00:08:38,000 --> 00:08:39,440
by YesCrypt authors.

126
00:08:39,920 --> 00:08:41,980
As you can see, smix was modified,

127
00:08:42,380 --> 00:08:45,220
and random rewrites were introduced,

128
00:08:45,420 --> 00:08:46,980
and tweaks and parallelism were done,

129
00:08:47,200 --> 00:08:50,200
and pvx form was, is displayed.

130
00:08:50,500 --> 00:08:53,680
It is a replacement for Celsa 2028.

131
00:08:54,020 --> 00:08:55,460
So what is a pvx form?

132
00:08:55,640 --> 00:08:57,520
It's optimization for a low-memory case.

133
00:08:57,720 --> 00:09:00,020
It uses, as I said,

134
00:09:00,140 --> 00:09:03,640
it's an attempt to employ ideas from bcrypt,

135
00:09:03,740 --> 00:09:06,300
and it uses 12 kilobyte S-boxes,

136
00:09:06,300 --> 00:09:09,340
and it's very friendly to L1 CPU cache.

137
00:09:09,660 --> 00:09:12,660
It also uses integer multiplications

138
00:09:12,660 --> 00:09:16,520
because that operations have high latency

139
00:09:16,520 --> 00:09:18,640
on FPGAs and ASICs,

140
00:09:18,640 --> 00:09:21,820
and it's really friendly to SIMD instruction

141
00:09:21,820 --> 00:09:24,980
like ECC2, SSS, E3, and so on.

142
00:09:27,160 --> 00:09:30,320
And actually, this algorithm is good to study

143
00:09:30,320 --> 00:09:32,820
because, for example, if you want to plunge

144
00:09:32,820 --> 00:09:35,240
into what had been going on

145
00:09:36,360 --> 00:09:38,920
before password caching computation was launched,

146
00:09:39,100 --> 00:09:41,700
it's a good case to just to study

147
00:09:41,700 --> 00:09:44,100
the difference between S-crypt and YesCrypt.

148
00:09:45,960 --> 00:09:48,200
Here is the pros and cons of this algorithm.

149
00:09:48,640 --> 00:09:50,280
So it's optimized for a low-memory case,

150
00:09:50,380 --> 00:09:53,140
and it allows bcrypt-like resistance.

151
00:09:53,520 --> 00:09:57,220
It also introduces some tweaks in protocol design,

152
00:09:57,480 --> 00:10:00,200
and I'll be talking about it a bit later.

153
00:10:00,460 --> 00:10:02,800
And so it fixes S-crypt drawbacks,

154
00:10:02,960 --> 00:10:05,020
but the main drawback in this algorithm

155
00:10:05,020 --> 00:10:06,520
is that it's pretty complex.

156
00:10:06,640 --> 00:10:07,480
It's pretty complicated.

157
00:10:07,620 --> 00:10:10,480
It's hard to understand all this algorithm,

158
00:10:10,700 --> 00:10:13,260
and there is no resistance to side-channel attacks.

159
00:10:13,520 --> 00:10:17,200
So internally at Yandex, we opted for Argon2.

160
00:10:17,820 --> 00:10:18,380
Argon2.

161
00:10:18,640 --> 00:10:19,880
It's a good algorithm.

162
00:10:20,160 --> 00:10:22,100
It won password caching competition,

163
00:10:22,440 --> 00:10:25,600
and it's designed to be simple, tunable, and secure,

164
00:10:25,820 --> 00:10:27,820
and there are three modes in this algorithm.

165
00:10:28,140 --> 00:10:30,580
The first mode is data-independent mode.

166
00:10:30,740 --> 00:10:35,320
It means that all the RAM access pattern

167
00:10:35,320 --> 00:10:39,300
doesn't depend on password and salt.

168
00:10:40,360 --> 00:10:42,340
The second mode is data-dependent mode.

169
00:10:42,800 --> 00:10:47,200
It means that RAM access pattern

170
00:10:47,200 --> 00:10:50,700
depends on password and salt.

171
00:10:51,180 --> 00:10:53,300
So the first mode, independent,

172
00:10:53,680 --> 00:10:57,980
gives you resistance to side-channel attacks,

173
00:10:58,580 --> 00:11:01,660
but it's prone to time-memory trade-offs.

174
00:11:01,820 --> 00:11:04,780
The second mode gives you better resistance

175
00:11:04,780 --> 00:11:06,900
to time-memory trade-offs,

176
00:11:06,920 --> 00:11:08,340
but it's prone to side-channel attacks.

177
00:11:08,640 --> 00:11:11,280
And the third mode, in my opinion,

178
00:11:11,280 --> 00:11:13,220
is the most interesting mode, is ID.

179
00:11:13,360 --> 00:11:15,680
It's a combination of these two modes,

180
00:11:15,760 --> 00:11:16,200
and...

181
00:11:16,920 --> 00:11:19,660
It's some kind of mitigation of side-channel attacks

182
00:11:20,200 --> 00:11:23,920
and gives some resistance to time-memory trade-offs.

183
00:11:24,120 --> 00:11:26,220
Here is a short diagram of how it works.

184
00:11:26,400 --> 00:11:29,720
So it takes your password, salt, secret,

185
00:11:29,920 --> 00:11:31,440
and additional authentication data,

186
00:11:32,020 --> 00:11:33,740
puts them into Blake2B function,

187
00:11:34,060 --> 00:11:36,200
allocates several lanes of RAM,

188
00:11:36,400 --> 00:11:39,280
then performs some computations on this RAM,

189
00:11:39,420 --> 00:11:41,900
then takes the latest blocks,

190
00:11:42,120 --> 00:11:42,960
sorts them together,

191
00:11:43,180 --> 00:11:45,780
and puts them to Blake2B-like hash function.

192
00:11:45,780 --> 00:11:48,780
The main difference is the function with Blake2B

193
00:11:48,780 --> 00:11:51,000
is just it has variable length.

194
00:11:51,160 --> 00:11:53,440
It's variable length hash function,

195
00:11:53,560 --> 00:11:57,880
so it can give you tags with different lengths.

196
00:11:58,120 --> 00:11:59,800
So, for example, you need a short tag,

197
00:11:59,960 --> 00:12:00,960
you'll get short tag.

198
00:12:01,080 --> 00:12:04,140
If you need a big tag, you'll get big tag.

199
00:12:04,500 --> 00:12:05,780
So, and...

200
00:12:08,300 --> 00:12:09,340
So, and...

201
00:12:09,340 --> 00:12:11,360
Returning to Argon2ID mode,

202
00:12:11,540 --> 00:12:12,700
here you can see a diagram.

203
00:12:12,840 --> 00:12:14,980
So during the first pass,

204
00:12:15,780 --> 00:12:17,040
over all the lanes,

205
00:12:18,740 --> 00:12:23,860
Argon2 in ID mode acts as an I,

206
00:12:23,940 --> 00:12:27,800
in I mode and then switches to D mode,

207
00:12:27,940 --> 00:12:30,140
so acts as data-independent

208
00:12:30,140 --> 00:12:32,200
and then switches to data-dependent mode,

209
00:12:32,340 --> 00:12:33,900
and this provides mitigations

210
00:12:33,900 --> 00:12:37,320
against side-channel attacks.

211
00:12:38,440 --> 00:12:43,240
Here you can see round function from Argon2.

212
00:12:43,900 --> 00:12:45,560
You can see the diagram is...

213
00:12:45,780 --> 00:12:46,580
It's pretty clear.

214
00:12:46,720 --> 00:12:47,960
It's really simple.

215
00:12:48,120 --> 00:12:51,000
It's really easy to understand how algorithm works.

216
00:12:51,440 --> 00:12:55,040
And the core function of this is

217
00:12:55,820 --> 00:12:56,820
Blamco function.

218
00:12:57,060 --> 00:12:58,540
It's modified Blake2B function.

219
00:12:59,480 --> 00:13:01,480
And just as you can see,

220
00:13:01,520 --> 00:13:03,500
integer multiplications are added

221
00:13:03,500 --> 00:13:07,680
to make it harder to make...

222
00:13:08,760 --> 00:13:13,540
It adds some resistance to FPGAs and ASICs

223
00:13:13,540 --> 00:13:15,280
because integer multiplication

224
00:13:16,200 --> 00:13:17,080
has...

225
00:13:17,780 --> 00:13:20,860
It's a operation that has more latency

226
00:13:24,460 --> 00:13:26,900
on FPGAs and ASICs.

227
00:13:27,660 --> 00:13:30,080
So here are some design principles

228
00:13:30,080 --> 00:13:31,420
behind Argon2.

229
00:13:31,560 --> 00:13:33,280
It operates on one-kilobyte memory blocks

230
00:13:33,280 --> 00:13:36,660
and it's optimized for x64.

231
00:13:37,360 --> 00:13:39,560
It's extremely friendly

232
00:13:39,560 --> 00:13:44,220
to some SIMD instructions

233
00:13:44,220 --> 00:13:45,620
like SSE2,

234
00:13:45,780 --> 00:13:47,300
SSSE, and so on.

235
00:13:47,380 --> 00:13:48,780
It's some advanced instructions

236
00:13:48,780 --> 00:13:49,980
in modern CPUs.

237
00:13:50,960 --> 00:13:53,140
It fills out memory

238
00:13:53,420 --> 00:13:54,820
very quickly

239
00:13:54,820 --> 00:13:57,820
and it uses Blake2B

240
00:13:57,820 --> 00:13:59,600
and Blamco as underlying primitives.

241
00:14:00,720 --> 00:14:01,340
So,

242
00:14:01,460 --> 00:14:02,560
actually,

243
00:14:02,760 --> 00:14:04,400
there is no...

244
00:14:06,240 --> 00:14:07,040
especially...

245
00:14:07,040 --> 00:14:09,520
Argon isn't especially optimized

246
00:14:09,520 --> 00:14:10,940
for low memory usage

247
00:14:10,940 --> 00:14:13,500
and if you run a web service,

248
00:14:13,720 --> 00:14:15,440
actually, you can't afford

249
00:14:15,780 --> 00:14:18,120
bigger parameters of Argon2

250
00:14:18,120 --> 00:14:19,440
because you can suffer

251
00:14:19,440 --> 00:14:21,380
from computational denial of service

252
00:14:21,380 --> 00:14:23,100
or your users

253
00:14:24,340 --> 00:14:25,240
will suffer

254
00:14:25,720 --> 00:14:27,700
from big latencies and so on

255
00:14:27,700 --> 00:14:28,400
because, for example,

256
00:14:28,460 --> 00:14:29,800
if you want to authenticate

257
00:14:29,800 --> 00:14:32,000
in, say, a mobile application,

258
00:14:32,300 --> 00:14:35,600
you need to set up TCP handshake,

259
00:14:35,720 --> 00:14:37,700
then you need to set up TLS handshake,

260
00:14:37,820 --> 00:14:38,700
then you need to wait

261
00:14:38,700 --> 00:14:40,420
until your password caching algorithm

262
00:14:41,560 --> 00:14:43,240
will process password

263
00:14:43,240 --> 00:14:44,200
and username.

264
00:14:45,780 --> 00:14:46,740
It irritates users.

265
00:14:46,880 --> 00:14:48,500
They don't want to wait and so on.

266
00:14:48,780 --> 00:14:49,420
So,

267
00:14:49,540 --> 00:14:50,840
one of the ways

268
00:14:53,860 --> 00:14:55,700
to cope with this

269
00:14:55,700 --> 00:14:57,400
is to optimize Argon

270
00:14:57,400 --> 00:14:58,460
as much as possible

271
00:14:58,460 --> 00:15:01,020
and there are at least

272
00:15:01,500 --> 00:15:03,220
two implementations of Argon2.

273
00:15:03,300 --> 00:15:05,000
There is an official Argon2 implementation.

274
00:15:05,320 --> 00:15:06,620
You can find it in

275
00:15:06,620 --> 00:15:08,500
password caching competition repository.

276
00:15:08,960 --> 00:15:11,900
It uses a much native option to...

277
00:15:11,900 --> 00:15:13,460
This option tells

278
00:15:13,460 --> 00:15:15,260
a compiler to optimize

279
00:15:15,780 --> 00:15:17,320
this algorithm as much as possible

280
00:15:17,940 --> 00:15:19,580
for the current CPU

281
00:15:19,580 --> 00:15:21,700
on which the compiler

282
00:15:21,700 --> 00:15:22,200
is running.

283
00:15:23,540 --> 00:15:25,380
Using this option, you can easily

284
00:15:25,380 --> 00:15:27,080
run up against illegal instruction exceptions.

285
00:15:27,380 --> 00:15:28,760
For example, if you compile code

286
00:15:28,760 --> 00:15:31,700
on one CPU type and just move it

287
00:15:31,700 --> 00:15:32,920
into another CPU type,

288
00:15:33,120 --> 00:15:34,680
you can easily get an exception.

289
00:15:34,900 --> 00:15:36,840
I don't think you want to get it

290
00:15:36,840 --> 00:15:37,920
in a production environment.

291
00:15:40,000 --> 00:15:41,540
If you compile it

292
00:15:41,540 --> 00:15:42,980
in some kind of compatibility

293
00:15:42,980 --> 00:15:43,440
way,

294
00:15:45,880 --> 00:15:47,800
it will cost you

295
00:15:47,800 --> 00:15:49,720
at least 15 or 20%

296
00:15:49,720 --> 00:15:50,280
of performance.

297
00:15:50,640 --> 00:15:51,620
So what we did,

298
00:15:51,800 --> 00:15:55,140
we made our own implementation.

299
00:15:56,460 --> 00:15:57,820
This implementation

300
00:15:57,820 --> 00:15:59,620
features the technique

301
00:15:59,620 --> 00:16:01,660
that is called Runtime CPU Dispatching.

302
00:16:01,840 --> 00:16:03,660
We run CPU ID

303
00:16:03,660 --> 00:16:04,840
instruction and switch

304
00:16:05,620 --> 00:16:07,740
and take the most optimized

305
00:16:07,740 --> 00:16:09,440
version of the algorithm

306
00:16:09,440 --> 00:16:11,360
for this particular CPU type

307
00:16:11,360 --> 00:16:12,640
and we do it in runtime.

308
00:16:13,760 --> 00:16:15,560
You'll get maximum performance

309
00:16:15,780 --> 00:16:17,260
on your current CPU type

310
00:16:17,510 --> 00:16:19,780
and it makes

311
00:16:20,300 --> 00:16:21,540
deployment easier

312
00:16:21,540 --> 00:16:22,640
and

313
00:16:24,620 --> 00:16:25,480
so

314
00:16:25,480 --> 00:16:28,820
I think Runtime CPU Dispatching

315
00:16:28,820 --> 00:16:29,760
is a good way

316
00:16:29,760 --> 00:16:30,460
to get maximum

317
00:16:31,710 --> 00:16:32,880
performance on different

318
00:16:32,880 --> 00:16:34,120
types of

319
00:16:36,160 --> 00:16:37,020
CPUs.

320
00:16:37,690 --> 00:16:39,460
During the work on this algorithm,

321
00:16:39,620 --> 00:16:41,840
I also created AVX2 optimization

322
00:16:41,840 --> 00:16:43,480
and its

323
00:16:43,480 --> 00:16:45,440
instruction said that

324
00:16:45,780 --> 00:16:46,580
Runtime CPU Dispatching

325
00:16:46,580 --> 00:16:46,640
was

326
00:16:46,640 --> 00:16:51,400
a lot of

327
00:16:51,400 --> 00:16:52,480
modern CPU support

328
00:16:52,480 --> 00:16:54,200
and you can see

329
00:16:54,200 --> 00:16:55,620
in a couple of slides,

330
00:16:55,720 --> 00:16:56,780
you'll see the benefits of this.

331
00:16:56,980 --> 00:16:59,180
So we named our implementation

332
00:16:59,180 --> 00:16:59,980
Argonisha,

333
00:17:00,200 --> 00:17:01,720
that means Argon and Russian

334
00:17:01,720 --> 00:17:02,600
suffix "-ish".

335
00:17:03,800 --> 00:17:05,300
Russian suffix "-ish

336
00:17:05,300 --> 00:17:07,760
shows that it's something

337
00:17:07,760 --> 00:17:09,600
enormously bigger that scares

338
00:17:09,600 --> 00:17:10,940
small children and so on.

339
00:17:15,780 --> 00:17:16,460
So you can just

340
00:17:17,160 --> 00:17:19,060
get the code and review it yourself.

341
00:17:20,120 --> 00:17:21,500
Okay, here is

342
00:17:21,500 --> 00:17:23,080
some results of the benchmark

343
00:17:23,080 --> 00:17:25,120
and you can see that AVX2 implementation

344
00:17:26,040 --> 00:17:27,880
outperforms all the other optimizations.

345
00:17:28,560 --> 00:17:29,680
Actually, our library

346
00:17:29,680 --> 00:17:31,560
comes with a simple benchmarking tool

347
00:17:31,560 --> 00:17:33,780
that is similar to OpenSSL

348
00:17:33,780 --> 00:17:35,240
speed application

349
00:17:35,240 --> 00:17:37,480
and you can just take it

350
00:17:37,480 --> 00:17:38,440
and benchmark it yourself.

351
00:17:39,680 --> 00:17:41,520
Okay, and here is

352
00:17:41,520 --> 00:17:43,140
a repository where you can find

353
00:17:43,140 --> 00:17:45,760
the code. It's written in C++ for

354
00:17:45,780 --> 00:17:46,820
14. It uses constant

355
00:17:46,820 --> 00:17:47,640
expression,

356
00:17:47,900 --> 00:17:49,560
partial templates.

357
00:17:51,700 --> 00:17:53,260
It's just a convenient way

358
00:17:53,260 --> 00:17:55,440
to make a compiler do a lot of job for you.

359
00:17:56,340 --> 00:17:57,500
The license is

360
00:17:57,500 --> 00:17:58,840
BSD3 close.

361
00:17:59,080 --> 00:18:01,400
I think it's a very convenient

362
00:18:01,400 --> 00:18:03,180
license. You can do whatever you want.

363
00:18:03,380 --> 00:18:05,580
But if you wanted to modify the code and distribute

364
00:18:05,580 --> 00:18:07,380
it, you just need to wipe out

365
00:18:07,380 --> 00:18:08,780
the mention of Yandex and that's it.

366
00:18:09,920 --> 00:18:10,960
And now

367
00:18:11,540 --> 00:18:13,280
I'm working on AVX512

368
00:18:13,280 --> 00:18:15,540
optimization that was introduced in

369
00:18:15,780 --> 00:18:17,280
the recent Intel Skylake processes.

370
00:18:18,000 --> 00:18:19,540
But as I said,

371
00:18:19,580 --> 00:18:21,620
as I said,

372
00:18:21,660 --> 00:18:23,440
algorithm itself, it's

373
00:18:23,440 --> 00:18:25,460
not a perfect security measure and

374
00:18:25,460 --> 00:18:26,820
you can't afford big

375
00:18:27,680 --> 00:18:28,020
parameters.

376
00:18:33,340 --> 00:18:35,380
And if you rely

377
00:18:35,380 --> 00:18:37,440
solely on the algorithm, offline

378
00:18:37,440 --> 00:18:39,480
attacks are possible. What are offline

379
00:18:39,480 --> 00:18:41,680
attacks? Offline attacks is when

380
00:18:41,680 --> 00:18:42,840
for example an attacker

381
00:18:43,740 --> 00:18:45,000
hacked into your database

382
00:18:45,780 --> 00:18:47,300
dropped all the password hashes,

383
00:18:47,460 --> 00:18:48,720
took them

384
00:18:50,420 --> 00:18:51,620
home and had

385
00:18:51,620 --> 00:18:53,260
some fun with GPUs and

386
00:18:54,300 --> 00:18:54,860
some

387
00:18:55,440 --> 00:18:56,400
cracking software.

388
00:18:58,140 --> 00:18:59,260
So sometimes

389
00:18:59,900 --> 00:19:00,860
there are some

390
00:19:01,480 --> 00:19:03,420
ideas how to mitigate these

391
00:19:03,420 --> 00:19:05,560
and here you can see some ideas.

392
00:19:05,860 --> 00:19:07,460
The first idea is to use local

393
00:19:07,460 --> 00:19:09,500
parameters. The second idea is to use

394
00:19:09,500 --> 00:19:11,220
big ROMs and this idea was introduced

395
00:19:11,720 --> 00:19:12,000
by

396
00:19:12,000 --> 00:19:15,400
the authors of ChiaScript.

397
00:19:15,780 --> 00:19:17,560
You can also use crypto anchors

398
00:19:17,560 --> 00:19:19,520
and the last one is

399
00:19:19,520 --> 00:19:21,100
the most advanced one is to use

400
00:19:21,480 --> 00:19:23,320
partially obvious pseudorandom functions.

401
00:19:23,960 --> 00:19:25,560
Let's start with local parameters.

402
00:19:25,840 --> 00:19:27,540
The idea is pretty simple. Just

403
00:19:27,540 --> 00:19:29,580
add some secret key into

404
00:19:29,580 --> 00:19:31,440
a password hashing algorithm. For example

405
00:19:31,440 --> 00:19:32,660
argon2 can get

406
00:19:32,660 --> 00:19:34,180
a secret key

407
00:19:34,180 --> 00:19:37,320
to its input and

408
00:19:37,320 --> 00:19:39,520
just don't store

409
00:19:39,520 --> 00:19:40,940
the secret key into a database.

410
00:19:41,740 --> 00:19:43,380
Store it in environment

411
00:19:43,380 --> 00:19:45,540
variables of your application or for

412
00:19:45,780 --> 00:19:47,140
example configuration of your application.

413
00:19:47,340 --> 00:19:49,560
SQL injection into

414
00:19:49,560 --> 00:19:51,680
a database in your application

415
00:19:51,680 --> 00:19:53,660
becomes insufficient so if an

416
00:19:53,660 --> 00:19:54,720
attacker wants to steal

417
00:19:54,720 --> 00:19:57,780
all the password hashes

418
00:19:57,780 --> 00:19:59,220
and to crack them at home

419
00:19:59,640 --> 00:20:00,480
he needs to

420
00:20:02,040 --> 00:20:03,600
find a SQL injection

421
00:20:03,600 --> 00:20:05,380
or for example remote code execution

422
00:20:05,380 --> 00:20:07,320
vulnerability in your application and

423
00:20:07,320 --> 00:20:08,820
it's much harder to find.

424
00:20:10,840 --> 00:20:11,480
Let's

425
00:20:11,480 --> 00:20:12,740
talk a bit about big

426
00:20:12,740 --> 00:20:15,140
read-only memory.

427
00:20:15,780 --> 00:20:16,480
The authors of

428
00:20:16,480 --> 00:20:17,020
EScript

429
00:20:20,000 --> 00:20:20,600
introduced

430
00:20:21,520 --> 00:20:23,360
the idea of using big ROMs.

431
00:20:23,400 --> 00:20:25,440
For example you allocate a big

432
00:20:26,200 --> 00:20:27,620
area of memory and

433
00:20:27,620 --> 00:20:28,960
during the password hashing you perform

434
00:20:28,960 --> 00:20:31,700
random lookups and mix it into your algorithm.

435
00:20:32,120 --> 00:20:33,540
The idea is pretty simple because

436
00:20:33,540 --> 00:20:34,740
for example if you allocate

437
00:20:34,740 --> 00:20:37,620
100 GB of memory it will be very

438
00:20:37,620 --> 00:20:39,440
hard to exfiltrate it and you

439
00:20:39,440 --> 00:20:41,420
probably catch the attacker in your infrastructure.

440
00:20:42,300 --> 00:20:42,900
But

441
00:20:43,840 --> 00:20:45,540
there are some drawbacks because

442
00:20:46,760 --> 00:20:47,800
it's harder

443
00:20:47,800 --> 00:20:49,580
to switch to a new password hashing algorithm

444
00:20:49,580 --> 00:20:51,600
obviously you will live with all

445
00:20:51,600 --> 00:20:52,440
this big

446
00:20:54,000 --> 00:20:55,040
memory area.

447
00:20:55,300 --> 00:20:57,360
At least an additional step in case of

448
00:20:57,360 --> 00:20:58,740
server reboot because you need to

449
00:20:59,400 --> 00:21:01,280
initialize this memory, you need to

450
00:21:03,220 --> 00:21:03,740
check

451
00:21:03,740 --> 00:21:05,220
the integrity and so on and

452
00:21:05,220 --> 00:21:07,440
actually there are ways to amortize

453
00:21:07,440 --> 00:21:13,560
and actually there are

454
00:21:13,560 --> 00:21:14,740
some ways to amortize

455
00:21:15,780 --> 00:21:17,560
this approach.

456
00:21:19,020 --> 00:21:19,660
So

457
00:21:19,660 --> 00:21:21,580
for example you can just divide

458
00:21:22,540 --> 00:21:23,680
this big ROM

459
00:21:23,680 --> 00:21:25,520
into some parts and

460
00:21:25,520 --> 00:21:27,640
scatter it around some web service

461
00:21:27,640 --> 00:21:29,720
and instead of performing lookups in your

462
00:21:29,720 --> 00:21:31,640
RAM you can just make

463
00:21:31,640 --> 00:21:33,160
a network request.

464
00:21:33,480 --> 00:21:34,880
It will be slower but anyway

465
00:21:34,880 --> 00:21:37,200
it can be used to

466
00:21:37,780 --> 00:21:39,500
brute force your hashes.

467
00:21:40,180 --> 00:21:41,760
So crypto anchors

468
00:21:41,760 --> 00:21:43,760
the idea is pretty simple just introduce

469
00:21:43,760 --> 00:21:45,760
just set up a

470
00:21:45,780 --> 00:21:46,340
simple

471
00:21:48,120 --> 00:21:49,720
service, a tiny service

472
00:21:49,720 --> 00:21:51,660
in your infrastructure and it will

473
00:21:51,660 --> 00:21:53,540
do only, it will apply

474
00:21:53,540 --> 00:21:55,560
only to the random function

475
00:21:55,560 --> 00:21:56,720
for example HMAC

476
00:21:56,720 --> 00:21:59,640
and it will be very hard

477
00:21:59,640 --> 00:22:01,460
to hack into this service because it's small

478
00:22:01,460 --> 00:22:03,620
it's tiny you can easily audit it and so on.

479
00:22:04,120 --> 00:22:05,600
But there is

480
00:22:05,600 --> 00:22:07,580
for example if you use HMAC there is

481
00:22:07,580 --> 00:22:09,380
a drawback because you can't just rotate

482
00:22:09,380 --> 00:22:11,600
the key of this HMAC

483
00:22:11,600 --> 00:22:13,100
you will need to

484
00:22:13,780 --> 00:22:15,680
for example if the case

485
00:22:15,780 --> 00:22:17,620
is compromised you will need to switch

486
00:22:17,620 --> 00:22:18,720
to another key and so on.

487
00:22:18,960 --> 00:22:21,420
And the guys from Cornell Tech

488
00:22:21,420 --> 00:22:22,780
introduced a new

489
00:22:23,540 --> 00:22:25,660
new method that they called

490
00:22:25,660 --> 00:22:26,800
it PATH.

491
00:22:27,700 --> 00:22:29,080
The idea is also pretty

492
00:22:29,080 --> 00:22:31,700
simple. I really like the

493
00:22:31,700 --> 00:22:33,180
idea so here you can see

494
00:22:33,180 --> 00:22:35,080
a web service and this

495
00:22:35,640 --> 00:22:37,300
crypto service and you need to

496
00:22:37,300 --> 00:22:38,400
build a pairing

497
00:22:39,360 --> 00:22:41,220
and you get your

498
00:22:41,780 --> 00:22:43,400
hash, password hash

499
00:22:43,400 --> 00:22:45,680
and you perform blinding and then say

500
00:22:45,780 --> 00:22:47,260
send user ID

501
00:22:47,260 --> 00:22:49,340
T means user ID and this

502
00:22:49,340 --> 00:22:50,780
blinded hash to

503
00:22:51,380 --> 00:22:52,560
this PIF service

504
00:22:52,560 --> 00:22:54,960
performs, applies this

505
00:22:54,960 --> 00:22:57,200
pairing with secret key

506
00:22:57,200 --> 00:22:58,700
and return it back

507
00:22:58,700 --> 00:23:01,360
and the web application can unblind

508
00:23:01,360 --> 00:23:02,720
actually

509
00:23:02,720 --> 00:23:04,140
in this case

510
00:23:04,140 --> 00:23:07,440
this PIF service

511
00:23:07,440 --> 00:23:08,800
doesn't see

512
00:23:10,080 --> 00:23:11,560
the hash

513
00:23:11,560 --> 00:23:12,120
of the password

514
00:23:12,120 --> 00:23:14,680
so if

515
00:23:15,780 --> 00:23:16,460
anyone will

516
00:23:16,460 --> 00:23:18,100
hack into this PIF service

517
00:23:18,100 --> 00:23:19,680
he won't get

518
00:23:20,440 --> 00:23:22,440
he wouldn't be able to collect

519
00:23:23,380 --> 00:23:25,120
the hashes of passwords

520
00:23:25,690 --> 00:23:27,460
and this scheme also

521
00:23:28,960 --> 00:23:29,980
can be used

522
00:23:29,980 --> 00:23:31,820
to rotate keys

523
00:23:31,820 --> 00:23:33,060
for example this service

524
00:23:33,060 --> 00:23:34,800
can send a web application

525
00:23:34,800 --> 00:23:36,260
a key rotation token

526
00:23:36,260 --> 00:23:38,600
and it can apply this token

527
00:23:38,600 --> 00:23:40,140
and just rotate the key

528
00:23:40,140 --> 00:23:42,740
just process it's password hashing database

529
00:23:42,740 --> 00:23:44,800
and rotate the key. It is pretty

530
00:23:45,780 --> 00:23:47,600
simple and I think it's pretty cool

531
00:23:47,600 --> 00:23:49,840
and they also

532
00:23:49,840 --> 00:23:51,480
extended this idea

533
00:23:51,480 --> 00:23:52,760
and introduced so called

534
00:23:52,760 --> 00:23:55,180
Pyther PRF

535
00:23:55,550 --> 00:23:57,600
the idea is like those in PaaS

536
00:23:57,600 --> 00:23:58,720
but they also added

537
00:23:58,720 --> 00:24:01,340
zero knowledge proof scheme to prove

538
00:24:01,340 --> 00:24:02,460
correctness of the calculations

539
00:24:02,460 --> 00:24:05,200
and they also adapted the scheme

540
00:24:05,200 --> 00:24:06,600
to be multi-tenant

541
00:24:06,600 --> 00:24:08,500
so let's come to conclusions

542
00:24:08,500 --> 00:24:11,740
ok, good algorithms are not enough

543
00:24:11,740 --> 00:24:14,180
for online password hashing

544
00:24:14,180 --> 00:24:15,420
and you need to

545
00:24:15,780 --> 00:24:17,080
because you can't

546
00:24:17,080 --> 00:24:19,740
you can't afford bigger parameters

547
00:24:19,740 --> 00:24:21,700
and if you rely

548
00:24:21,700 --> 00:24:23,260
only on algorithm you'll be suffering

549
00:24:23,680 --> 00:24:25,540
from for example offline attacks

550
00:24:25,540 --> 00:24:27,500
and so on but there are good approaches

551
00:24:27,500 --> 00:24:29,540
to make up for it so offline

552
00:24:29,540 --> 00:24:31,280
attacks can be turned into online

553
00:24:31,280 --> 00:24:32,620
online attacks

554
00:24:32,620 --> 00:24:35,440
so if you want to afford more parameters

555
00:24:35,440 --> 00:24:37,240
you can optimize performance and

556
00:24:37,240 --> 00:24:39,460
you can for example use our

557
00:24:39,460 --> 00:24:41,000
optimized implementation

558
00:24:41,000 --> 00:24:43,420
and I want to say thank you to

559
00:24:43,420 --> 00:24:45,400
Dmitry Havratovich he is also

560
00:24:45,780 --> 00:24:47,680
with Argon2 and I want to thank

561
00:24:47,680 --> 00:24:49,740
him for all the discussions

562
00:24:49,740 --> 00:24:51,740
about Yescrypt

563
00:24:51,740 --> 00:24:53,840
and Argon2 I want to say thank you

564
00:24:53,840 --> 00:24:55,760
to Alexander Pislak for all the discussions

565
00:24:55,760 --> 00:24:58,140
about Yescrypt and Igor Klymanets

566
00:24:58,140 --> 00:24:59,720
who reviewed the code of

567
00:24:59,720 --> 00:25:01,700
our implementation of Argon2

568
00:25:01,700 --> 00:25:03,340
and just

569
00:25:04,500 --> 00:25:05,340
made some

570
00:25:05,340 --> 00:25:07,360
useful suggestions and

571
00:25:07,360 --> 00:25:09,240
a couple of useful links so if you

572
00:25:09,240 --> 00:25:11,460
want to get more information about Pyther

573
00:25:11,460 --> 00:25:13,200
PRF service here is a link to

574
00:25:13,200 --> 00:25:14,360
the original article

575
00:25:16,280 --> 00:25:17,820
here is once again

576
00:25:17,820 --> 00:25:18,940
it's a link to our

577
00:25:20,620 --> 00:25:21,520
Argon2 implementation

578
00:25:21,520 --> 00:25:23,640
and the last link

579
00:25:23,640 --> 00:25:25,580
it's Pyther reference

580
00:25:25,580 --> 00:25:27,200
implementation done by

581
00:25:28,800 --> 00:25:29,780
the guys from

582
00:25:29,780 --> 00:25:31,240
Cornell Tech so

583
00:25:32,300 --> 00:25:33,740
that's it for today thank you

584
00:25:33,740 --> 00:25:35,520
for coming and thank you for listening

585
00:25:35,520 --> 00:25:37,760
to this presentation so now I'm

586
00:25:37,760 --> 00:25:38,780
ready to take your questions

587
00:25:45,780 --> 00:25:46,720
thank you