 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I've seen a simple encryption like this:
uint64_t poor_encrypt(uint64_t x)
{
x = x ^ SECRET1;
x = x * SECRET2;
x = x ^ SECRET3;
return x;
}
the decryption is just the reverse:
uint64_t poor_decrypt(uint64_t x)
{
x = x ^ SECRET3;
x = x * INVERSE_OF_SECRET2;
x = x ^ SECRET1;
return x;
}
How many "x, encrypt(x)" pairs are necessary to reveal the 3 secret
constants? I think, 3 pairs should be enough, but am I right?
x=0x29ad711fdc0d4f4b enc(x)=0x2453938ddf924a49
x=0x44626112006ce11b enc(x)=0xe1ba98b582ec7899
x=0xc747d38561de6e54 enc(x)=0xa7d31873bc59182c
If you got the 3 secret values, you can reveal this pair, too:
x=0x51265200dfaaaa11 enc(x)=0x87461422********
Lars R.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Le 01/07/2014 14:23, Lars Rohwedder a écrit :
> I've seen a simple encryption like this:
>
> uint64_t poor_encrypt(uint64_t x)
> {
> x = x ^ SECRET1;
> x = x * SECRET2;
> x = x ^ SECRET3;
> return x;
> }
>
> the decryption is just the reverse:
>
> uint64_t poor_decrypt(uint64_t x)
> {
> x = x ^ SECRET3;
> x = x * INVERSE_OF_SECRET2;
> x = x ^ SECRET1;
> return x;
> }
>
Which value of Secret2 would allow the * (without overloading) to
reverse the value with a value of Inverse_of_secret2.
If * is not overloaded for uint64_t, I see only Secret2 = 1 as valid if
the original code uses the whole 64 bits range.
Therefore either the encrypt/decrypt is a simple xor of a single 64 bits
(you won't get Secret1 and Secret3, but (Secret1|Secret3)), or the * is
overloaded and we need to known more about that operation.
--
Just because nobody complains does not mean all parachutes are perfect.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Am 01.07.2014 15:30, schrieb Le_Forgeron:
> Le 01/07/2014 14:23, Lars Rohwedder a écrit :
>> I've seen a simple encryption like this:
>>
>> uint64_t poor_encrypt(uint64_t x)
>> {
>> x = x ^ SECRET1;
>> x = x * SECRET2;
>> x = x ^ SECRET3;
>> return x;
>> }
>>
>> the decryption is just the reverse:
>>
>> uint64_t poor_decrypt(uint64_t x)
>> {
>> x = x ^ SECRET3;
>> x = x * INVERSE_OF_SECRET2;
>> x = x ^ SECRET1;
>> return x;
>> }
>>
>
> Which value of Secret2 would allow the * (without overloading) to
> reverse the value with a value of Inverse_of_secret2.
if SECRET2 is be 123456789, its inverse is 16969517551553616445.
It is just the "multiplicative inverse modulo 2^64".
Note the arithmetics of unsigned integer data types is always "modulo"
2^BITSIZE of that data type.
Lars R.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Le 03/07/2014 14:06, Lars Rohwedder a écrit :
> Am 01.07.2014 15:30, schrieb Le_Forgeron:
>>
>> Which value of Secret2 would allow the * (without overloading) to
>> reverse the value with a value of Inverse_of_secret2.
>
> if SECRET2 is be 123456789, its inverse is 16969517551553616445.
>
> It is just the "multiplicative inverse modulo 2^64".
>
> Note the arithmetics of unsigned integer data types is always "modulo"
> 2^BITSIZE of that data type.
You use the crypto-version of the * operation (from Nist), not the usual
multiplication. Using "just" and crypto-modified operator in the same
sentence is... delicate.
--
Just because nobody complains does not mean all parachutes are perfect.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> Which value of Secret2 would allow the * (without overloading) to
>>> reverse the value with a value of Inverse_of_secret2.
>>
>> if SECRET2 is be 123456789, its inverse is 16969517551553616445.
>>
>> It is just the "multiplicative inverse modulo 2^64".
>>
>> Note the arithmetics of unsigned integer data types is always
>> "modulo" 2^BITSIZE of that data type.
>
> You use the crypto-version of the * operation (from Nist), not the
> usual multiplication.
No, it is just the integer multiplication that is done by nerly every
common CPU, so the usual computer arithmetics. That is no crypto foo.
Btw, the GCC translates integer divisions (with constant divisor) to
"multiplications with the inverse element", because multiplications are
faster than divisions on many CPUs.
Lars R.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Lars Rohwedder <rok### [at] gmx de> wrote:
> >>> Which value of Secret2 would allow the * (without overloading) to
> >>> reverse the value with a value of Inverse_of_secret2.
> >>
> >> if SECRET2 is be 123456789, its inverse is 16969517551553616445.
> >>
> >> It is just the "multiplicative inverse modulo 2^64".
> >>
> >> Note the arithmetics of unsigned integer data types is always
> >> "modulo" 2^BITSIZE of that data type.
> >
> > You use the crypto-version of the * operation (from Nist), not the
> > usual multiplication.
> No, it is just the integer multiplication that is done by nerly every
> common CPU, so the usual computer arithmetics. That is no crypto foo.
> Btw, the GCC translates integer divisions (with constant divisor) to
> "multiplications with the inverse element", because multiplications are
> faster than divisions on many CPUs.
Doesn't division via multiplication require a right-sift, though?
In other words, dividing an integer value by a constant can be done as
(value * x) >> y
where x and y are some magic integers calculated from the divisor?
Can it really be done with just a multiplication?
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Can it really be done with just a multiplication?
Yes, because it takes advantage of the fact that on a computer A*B
actually calculates (A*B)mod(2^N), when N is the number of bits in the
destination register.
For example, with 8-bit numbers, the inverse of multiply-by-3 is
multiply-by-171. Note that it only works if the multiplicand is greater
than 2 and prime. So that narrows down the possible values of SECRET2 in
the OP quite a lot.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Note that it only works if the multiplicand is greater
> than 2 and prime.
OK ignore that comment - I found this on wikipedia that explains it better:
http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> I've seen a simple encryption like this:
>
> uint64_t poor_encrypt(uint64_t x)
> {
> x = x ^ SECRET1;
> x = x * SECRET2;
> x = x ^ SECRET3;
> return x;
> }
>
> the decryption is just the reverse:
>
> uint64_t poor_decrypt(uint64_t x)
> {
> x = x ^ SECRET3;
> x = x * INVERSE_OF_SECRET2;
> x = x ^ SECRET1;
> return x;
> }
>
>
> How many "x, encrypt(x)" pairs are necessary to reveal the 3 secret
> constants? I think, 3 pairs should be enough, but am I right?
I think it depends what you mean by "reveal". If you mean, can you
"solve" the equations to find SECRET1-3, in the same way you would a
mathematical equation, then it might not be possible without some
element of brute-force. For example how do you solve (x*5)^(x*10)=49
(where * and ^ are 8-bit CPU integer multiply and xor)?
The other question is, given the 3 pairs, is there a unique set of
SECRET1-3, or could a different set allow the same pairs?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Am 22.07.2014 17:10, schrieb scott:
>> I've seen a simple encryption like this:
>>
>> uint64_t poor_encrypt(uint64_t x)
>> {
>> x = x ^ SECRET1;
>> x = x * SECRET2;
>> x = x ^ SECRET3;
>> return x;
>> }
>>
>> the decryption is just the reverse:
>>
>> uint64_t poor_decrypt(uint64_t x)
>> {
>> x = x ^ SECRET3;
>> x = x * INVERSE_OF_SECRET2;
>> x = x ^ SECRET1;
>> return x;
>> }
>>
>>
>> How many "x, encrypt(x)" pairs are necessary to reveal the 3 secret
>> constants? I think, 3 pairs should be enough, but am I right?
>
> I think it depends what you mean by "reveal".
A way to tell me the 3 SECRET constants. Dumb brute force is AFAIK
impossible for 3 64 bit constants, so a little bit of thinking is
necessary to shrink the search space. And the more thinking you invest
the smaller might be the search space, at best it is shrunken to only
one triple. :-)
It is a trade-off in the algorithm. ;-)
> If you mean, can you
> "solve" the equations to find SECRET1-3, in the same way you would a
> mathematical equation, then it might not be possible without some
> element of brute-force. For example how do you solve (x*5)^(x*10)=49
> (where * and ^ are 8-bit CPU integer multiply and xor)?
For 8 bit numbers I'd just make a brute-force scanniing, no more mental
efforts are necessary here. Your x is 99. That's the only solution. :-)
> The other question is, given the 3 pairs, is there a unique set of
> SECRET1-3, or could a different set allow the same pairs?
Right. How many pairs are necessary so the 3 SECRET constants are unique
and definite?
Lars R.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
