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);) 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

11111

**000**0xF8

_____________& result

11011000 0xD8

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

11011001 0xDD

11111

**000** 0xF8

_____________& result

11011000 0xD8

And the last one:

11011000 0xDC

11111

**000** 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:

**01**111000 0x78

**10**111000 0xb8

**11**111000 0xf8

**00**111000 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.

__UPDATE__:

Frank Denis was kind giving motivations for this behavior.

I'm glad to receive his answer.

Cheers,

RE Solver