Libsodium sealed boxes: multiple (32) working secret keys for one public key

Hi Everybody,
starting from the strange fact where, during Cr1pT0r RE, I found 3 different but valid secret keys, I wanted to dig a bit more.

And yes I was wrong. For a single public key there are 32 valid keys!

 


Figure out how the key pair are generated is the most obvious start point.
From Libsodium Documentation:
digging into the sources we face the crypto_box_keypair(*pk,*sk)


take a look into the crypto_scalarmult_curve25519_ref10_base. This function is going to create our public key.
The first step is to copy the secret key (previously created by randombytes_buf(sk, 32):wink: into t array.
Next, before to create the public key by calling other methods some math is applied:
t[0] &= 248;
t[31] &= 127;
t[31] |= 64;

the first byte of our secret key undergoes a bitwise AND operation with 248dec (0xF8).

Take a look more closely at how it works starting from my old keypairs:
>>> publicbob.hex()
‘3d3f78633ea6a799c4dcf2522d9021c51031de6ba3ebcf061cc5caf8f843c52f’
>>> privbob.hex()
‘dba2d474c0b72b620ecdc87f43eaab2e2465009174dc03b422c848301f19dd78’

At the time it was invoked, crypto_scalarmult_curve25519_ref10_base function had
t[0] = 0xdb;
Let’s reproduce the bitwise and in binary:

11011010  0xDB

‭11111000‬   0xF8
& result
11011000   0xD8

Now, do the same for the others 2 bytes which were working: 0xDD 0xDC

11011001  0xDD

‭11111000‬   0xF8
& result
11011000   0xD8

And the last one:
11011000  0xDC

‭11111000‬   0xF8
& result
11011000   0xD8

Bitwise AND is a lossy transformation, by doing such operation we face a mask that leaves us free to rewrite the last 3 bits as we prefer!
3 bits = 8 possibilites -> so, the public key is valid for 8 different secret keys!! 

But we’re not done yet! Remember?
t[31] &= 127;
t[31] |= 64;

A similar application over the last byte is valid! 
Bring back the last byte in the example key: 0x78, in binary:

‭01111000‬  0x78

‭01111111‬  0x7f
&result
‭01111000‬  0x78
‭00111000‬  0x38
‭01111000‬  0x78
‭00111000‬  0x38
_____________| result
01000000  0x40 

Same logic applied before: which bytes we’re free to change in order of having a valid secret key?
The first bitwise AND operation leaves us free to change the first bit (MSB) only but, the OR operation extends our possibilities up to the second bit.
So accepted bytes in this case are:
01111000‬  0x78
10111000  0xb8
11111000  0xf8
00111000  0x38

2 bits, 4 possibilites: 00,01,10,11.

So we know that for a single public key up to 8 keys * 4 = 32 different keys could be valid and acceptable!
Starting from the source code I wrote in the last article, let’s brute the first and last byte of the sk:




32 different valid secret keys!

In the context of a bruteforce those valid keys are substantially adjacent, so in the set of reducing the time spent during bruteforce the whole key it does not help, because remains extremely long and not practicable, but it is a step forward within the general knowledge.


Cheers,
RE Solver



Article Link: https://resolverblog.blogspot.com/2019/03/libsodium-sealed-boxes-multiple-32.html