Cryptanalyzing a Pair of Russian Encryption Algorithms

A pair of Russia-designed cryptographic algorithms -- the Kuznyechik block cipher and the Streebog hash function -- have the same flawed S-box that is almost certainly an intentional backdoor. It's just not the kind of mistake you make by accident, not in 2014.

Posted on May 10, 2019 at 6:30 AM • 25 Comments

Comments

Wilhelm TellMay 10, 2019 6:58 AM

> countries hoping to cement their cryptographic
> algorithms as standards

The secrecy and a standard can not exist in the same space and time.

jbmartin6May 10, 2019 7:36 AM

I understand a similar flaw exists in already implemented algorithms, but it is not one that has a definite path to exploit. Do you think the Russians have a way to exploit it in this case, or would they simply put it in their proposal and hope to find a way to exploit it later? And would that exploit also possibly apply to the other similar flaws? Talking about this bit:

“One of the points the Russians made in the meeting, [was that] other algorithms, that are even more widely used—we also have concerns of [a] similar type, and yet we don't think we should stop using them. And they're right about this point.”

draft_May 10, 2019 8:44 AM

Can anyone give me/us a list of cryptographic algorithms, that
are safe to use in 2019, have no known weaknesses/backdoors?
Thanks!

RealFakeNewsMay 10, 2019 9:58 AM

When you say "same flawed S-box", is it the same vulnerability or it's using an identical S-box?

Bruce SchneierMay 10, 2019 10:22 AM

@RealFakeNews

"When you say "same flawed S-box", is it the same vulnerability or it's using an identical S-box?"

The two algorithms use the same S-box.

scotMay 10, 2019 10:42 AM

@RealFakeNews It looks to be identical. Here is the content of the S-box, from the paper "Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1":

.0 .1 .2 .3 .4 .5 .6 .7 .8 .9 .a .b .c .d .e .f
0.fc ee dd 11 cf 6e 31 16 fb c4 fa da 23 c5 04 4d
1.e9 77 f0 db 93 2e 99 ba 17 36 f1 bb 14 cd 5f c1
2.f9 18 65 5a e2 5c ef 21 81 1c 3c 42 8b 01 8e 4f
3.05 84 02 ae e3 6a 8f a0 06 0b ed 98 7f d4 d3 1f
4.eb 34 2c 51 ea c8 48 ab f2 2a 68 a2 fd 3a ce cc
5.b5 70 0e 56 08 0c 76 12 bf 72 13 47 9c b7 5d 87
6.15 a1 96 29 10 7b 9a c7 f3 91 78 6f 9d 9e b2 b1
7.32 75 19 3d ff 35 8a 7e 6d 54 c6 80 c3 bd 0d 57
8.df f5 24 a9 3e a8 43 c9 d7 79 d6 f6 7c 22 b9 03
9.e0 0f ec de 7a 94 b0 bc dc e8 28 50 4e 33 0a 4a
a.a7 97 60 73 1e 00 62 44 1a b8 38 82 64 9f 26 41
b.ad 45 46 92 27 5e 55 2f 8c a3 a5 7d 69 d5 95 3b
c.07 58 b3 40 86 ac 1d f7 30 37 6b e4 88 d9 e7 89
d.e1 1b 83 49 4c 3f f8 fe 8d 53 aa 90 ca d8 85 61
e.20 71 67 a4 2d 2b 09 5b cb 9b 25 d0 be e5 6c 52
f.59 a6 74 d2 e6 f4 b4 c0 d1 66 af c2 39 4b 63 b6

They are finding patterns, and since the developers of the algorithm did not detail the techniques used to generate the S-box, they suspect the patterns may be due to an exploit engineered into the S-box.

markMay 10, 2019 11:14 AM

Bruce, you wrote,
"It's just not the kind of mistake you make by accident, not in 2014."

Er, how 'bout in 2019?

Ross SniderMay 10, 2019 12:02 PM

This highlights the criticality of requiring fully public design rationale for any potential international standards.

Without transparency into the threat and design of these ciphers, we're subject to the "everyone should be secure, except for from me" race to the bottom.

A similar issue faces transparency in software, firmware and hardware.

Parry NoirMay 10, 2019 3:47 PM

@Ross Snider

> This highlights the criticality of requiring fully public design rationale for any potential international standards.

A problem with public design rationale is that, for seemingly random elements, you can't tell whether they are just a random choice satisfying all the disclosed criteria, or whether they are carefully chosen to meet additional unstated ones. Maybe the develop process can be structured in such a way that the designer specifies the design rules, and all the random elements are chosen randomly by an independent, verifiable process.

Ross SniderMay 10, 2019 6:44 PM

@Parry Noir

I agree that this can a problem, but solutions do exist - such as NUMS ("Nothing Up My Sleeves") curves. You specify the design rationale for the cipher and from it derive the canonically first valid system that meets the specifications. Your recommendation also seems fair.

Also: I'd be willing to accept random elements chosen by an authoring agency if its also supplied with a security model covering how choice over the combined seemingly random fields might allow the standard to be subverted, and it be shown that the amount of computation required to design such parameters is unfeasible, etc.

anonMay 11, 2019 10:50 AM

Although I do know a bit about mathematics, it's somewhat hard to understand the papers. To me, it's quite impressive the authors are able to gain that kind of information about the S-box, what's beneath the surface. Especially the second paper, by Perrin, reconstructing the design process. Are there more examples like this in the history of cryptanalysis? To me, this is pretty amazing.

justinacolmenaMay 11, 2019 12:06 PM

Wilhelm Tell • May 10, 2019 6:58 AM

> countries hoping to cement their cryptographic
> algorithms as standards

The secrecy and a standard can not exist in the same space and time.

It's an Establishment Masonic obsession over “peculiar arts.”

Regard not them that have familiar spirits, neither seek after wizards, to be defiled by them: I am the LORD your God.

Cryptology and cryptanalysis as “black arts” fail the standards of гла́сность and openness required by the Holy Bible.

MarkHMay 11, 2019 3:27 PM

@justina:

For a few moments, I thought the little tick mark over the letter "a" in glasnost' might be a speck of dust on my screen ...

... until I realized it must be stress mark from a dictionary entry.

For anyone who cares about the pronunciation, you can come close enough to be understandable by saying GLOSS-nust (rhymes with dust).

But to get it accurately, the 't' must be enunciated concurrently with a subtle 'y' sound (as in "yellow"). That's the soft palatalization which is so challenging for many students of Russian.

SpaceLifeFormMay 11, 2019 4:12 PM

@draft

No.

Kidding. It is extremely difficult.

IMHO, use curve and a good hash.

And think, really, really think about how your protocol can be attacked.

Get back to us in a few years when you have really, really thought about the attack angles and let us know if you have found a solution.

I would not use RSA, AES, or any DHE.

Did I mention good random?

Bruce SchneierMay 11, 2019 4:50 PM

@mark

"Bruce, you wrote, 'It's just not the kind of mistake you make by accident, not in 2014.' Er, how 'bout in 2019?"

Near as I can tell, the original public specifications of the two algorithms are from 2014. The cryptanalysis papers come later.

justinacolmenaMay 13, 2019 11:33 AM

@MarkH

stress mark from a dictionary entry.

Those Russian stress marks or accents go back to classical Greek, actually. I’m not entirely sure.

Greek also has the smooth breathing and rough breathing marks, and there are hard and soft signs in Russian, similar but not quite the same thing.

Ъ Ь

TIARA GNOMEMay 14, 2019 2:21 AM

I am very grateful for this excellent blog. I am glad Mr. Schneier takes his time to help keep us informed.

I hope the tone of the conversations and statements can remain civil, which reflects well on all of us and makes for pleasant reading.

I will stop using Kuznyechik.

WeatherMay 14, 2019 12:19 PM

12 rounds 3 different sbox, make a 12^3 2d array start at 0x7fffff800000 if 1 do I/2 and add to the above value the next 2d array value say its 2 add to the first I+0ff/2 at the end of array subtract 0x7fffff800000, you should be left with the start,
Its got rotate function which you can do at each round, the xor breaks it thought.

WeatherMay 14, 2019 7:49 PM

Round 1 =1
" = 2
" = 1
" = 3
......
Made up 2d array
Start at 0x00 sbox value = 0x63
0x63 with round 1 = 0x63 - 0
0x7fe3

0x63 _ 0xaa
(0xaa + 0x99)/2 = 0x86 for round 2
0x7fe3 + 0x86 = 0x8069


0x86 _ 0x97
0x97 - 0x86 = 0x11 for round 3
0x8069 + 0x11 = 0x807a

0x11 _ 0xca
(0xff - 0xca)/2 = 0x1a
0x807a + 0x1a = 0x8094

0x7f80 + 0x1a = 0x7f9a

0x8094 - 0x7f9a = 0xfa which is 15 in the sbox table.

Neal McBurnettMay 15, 2019 8:18 AM

What I'm wondering is what the pitch was. Why would anyone (in particular ISO) want a new hash function or 128-bit block cipher? What was novel or noteworthy about the design of Kuznyechik or Streebog when compared to the many other algorithms, many of which have been widely vetted, designed more openly, etc?

How often does ISO get, or accept, new crypto functions like this?

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Sidebar photo of Bruce Schneier by Joe MacInnis.