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
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.
UPDATE:
Frank Denis was kind giving motivations for this behavior.
I'm glad to receive his answer.
Cheers,
RE Solver
My Nas is infected by Cr1ptT0r, and I'd like to thank you for your hard work!
RispondiEliminaMine too !!!
RispondiEliminaWe rely on you !.... And your girlfriend too as far as I understood 😁😁😁
Bravo. I put more faith in you than I do in D-Link to provide any hope of recovering my data.
RispondiEliminaHi Resolver, Did you manage to decrypt this?
RispondiElimina