Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > sci.crypt > #50242 > unrolled thread

IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION

Back to article view | Back to sci.crypt

Contents

  IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION 711 Spooky Mart <711@spooky.mart> - 2021-09-30 12:43 -0500
    Re: IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION Peter Pearson <pkpearson@nowhere.invalid> - 2021-10-01 15:52 +0000
      Re: IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION 711 Spooky Mart <711@spooky.mart> - 2021-10-02 05:41 -0500
      Re: IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION 711 Spooky Mart <711@spooky.mart> - 2021-10-02 09:08 -0500
        Re: IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION Peter Pearson <pkpearson@nowhere.invalid> - 2021-10-02 15:34 +0000
          Re: [BORKED] IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION 711 Spooky Mart <711@spooky.mart> - 2021-10-04 16:25 -0500
            Re: [BORKED] IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION Peter Pearson <pkpearson@nowhere.invalid> - 2021-10-05 15:20 +0000
              Re: [BORKED] IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION 711 Spooky Mart <711@spooky.mart> - 2021-10-05 14:26 -0500
                Re: [BORKED] IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION Peter Pearson <pkpearson@nowhere.invalid> - 2021-10-05 20:32 +0000

#50242 — IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION

https://eprint.iacr.org/2014/335

This interesting, simple cryptosystem looks easy to implement in
software. Does anyone know of any analysis on it? How does it scan on
first impression?

-- 
███████████████████████████████████
█░░░░░░░░░░░█░░░░░░░░███░░░░░░░░███
█░░███████░░█░░████░░███░░████░░███        [chan] 711
█░░░░░░░██░░█░░░░██░░███░░░░██░░███        spooky mart
██████░░██░░███░░██░░█████░░██░░███        always open
██████░░██░░███░░██░░█████░░██░░███        stay spooky
██████░░██░░█░░░░██░░░░█░░░░██░░░░█        https://bitmessage.org
██████░░██░░█░░██████░░█░░██████░░█
██████░░░░░░█░░░░░░░░░░█░░░░░░░░░░█
███████████████████████████████████

[toc] | [next] | [standalone]

#50266

On Thu, 30 Sep 2021 12:43:16 -0500, 711 Spooky Mart <711@spooky.mart> wrote:
>
> https://eprint.iacr.org/2014/335
>
> This interesting, simple cryptosystem looks easy to implement in
> software. Does anyone know of any analysis on it? How does it scan on
> first impression?

As best I can tell (the presentation is awfully muddled), the
public key is a multiplier "Sara" and a modulus "Bra", and message M is
encrypted as

  e = (M * Sara) mod Bra

while the private key is another multiplier "Sbr" and another modulus "B",
and ciphertext is decrypted as

  d = (e * Sbr) mod B.

This algorithm is so far from being cryptographically sound that
I'm afraid I must be missing some big, obvious, April-fools-day
joke.


-- 
To email me, substitute nowhere->runbox, invalid->com.

[toc] | [prev] | [next] | [standalone]

#50293

On 10/1/21 10:52 AM, Peter Pearson wrote:
> On Thu, 30 Sep 2021 12:43:16 -0500, 711 Spooky Mart <711@spooky.mart> wrote:
>>
>> https://eprint.iacr.org/2014/335
>>
>> This interesting, simple cryptosystem looks easy to implement in
>> software. Does anyone know of any analysis on it? How does it scan on
>> first impression?
> 
> As best I can tell (the presentation is awfully muddled), the
> public key is a multiplier "Sara" and a modulus "Bra", and message M is
> encrypted as
> 
>   e = (M * Sara) mod Bra
> 
> while the private key is another multiplier "Sbr" and another modulus "B",
> and ciphertext is decrypted as
> 
>   d = (e * Sbr) mod B.
> 
> This algorithm is so far from being cryptographically sound that
> I'm afraid I must be missing some big, obvious, April-fools-day
> joke.

Here's the patent:
https://patents.google.com/patent/US8811606B2/en?inventor=John+Almeida&page=2

I didn't see how it was awfully muddled. The presentation seemed very
clear and straightforward, without unnecessary and arcane verbiage. I
believe the author is Portuguese, but did well enough with his English
that I could follow his train of thought.  I was able to implement it in
Python in a few minutes from first reading.

It appears to divide up the DLP and factoring to two sets so the
attacker must solve both DLP and hidden subset composite factoring to
break it. How is it cryptographically unsound?

-- 
███████████████████████████████████
█░░░░░░░░░░░█░░░░░░░░███░░░░░░░░███
█░░███████░░█░░████░░███░░████░░███        [chan] 711
█░░░░░░░██░░█░░░░██░░███░░░░██░░███        spooky mart
██████░░██░░███░░██░░█████░░██░░███        always open
██████░░██░░███░░██░░█████░░██░░███        stay spooky
██████░░██░░█░░░░██░░░░█░░░░██░░░░█        https://bitmessage.org
██████░░██░░█░░██████░░█░░██████░░█
██████░░░░░░█░░░░░░░░░░█░░░░░░░░░░█
███████████████████████████████████

[toc] | [prev] | [next] | [standalone]

#50296

On 10/1/21 10:52 AM, Peter Pearson wrote:
> On Thu, 30 Sep 2021 12:43:16 -0500, 711 Spooky Mart <711@spooky.mart> wrote:
>>
>> https://eprint.iacr.org/2014/335
>>
>> This interesting, simple cryptosystem looks easy to implement in
>> software. Does anyone know of any analysis on it? How does it scan on
>> first impression?
> 
> As best I can tell (the presentation is awfully muddled), the
> public key is a multiplier "Sara" and a modulus "Bra", and message M is
> encrypted as
> 
>   e = (M * Sara) mod Bra
> 
> while the private key is another multiplier "Sbr" and another modulus "B",
> and ciphertext is decrypted as
> 
>   d = (e * Sbr) mod B.
> 
> This algorithm is so far from being cryptographically sound that
> I'm afraid I must be missing some big, obvious, April-fools-day
> joke.

Calling the work of a man with a pile of U.S. Patents a "April-fools-day
joke" is a spleen trope. I get it, you likely saw some simplistic part
of the maths and thought, "nah, this is basic woo." But the interesting
part to me that should be attacked comes later in the paper. It is so
simple yet elegant that I can see why the author went to the trouble of
getting a patent.

Did you read in to the simple parts and stop before he explained the
trap door function? Since you have authored some patent applications you
likely know that it takes a modicum of very precise attention to detail.

John Almeida, the author of this "Shadow Numbers" cryptosystem, has many
U.S. Patents and was running a technology company when making patent
applications. I think his work deserves a mite of attention.

The simplicity and ingenuity of this cryptosystem makes it more than
worthy of examination and attack. By attack is meant real crispy
crunchy, not mere assertions. I think we should try to break this system
and document it, or even do a short attack diagram right here on the
Usenet thread. Even if it can be broken, we might discover a way to cure
the defect and make it unbreakable.

The cryptosystem is based on the DH idea of hidden subgroup membership,
then the trap door is a combination of factoring composites (easy to do)
combined with exponentiation and addition of exponents (hard to do).
Prime numbers are not required for key generation. The exponentiation
and addition obfuscate the subgroup relationship between the numbers so
that discrete logarithm can't be computed with the usual algorithms. How
would one prove this is less hard than factoring RSA/Rabin semiprimes?

If the relationship to hidden subgroup and the additive element can be
determined for large numbers >= 2048 bits the algorithm is insecure. If
the subgroup relationship and additive element can not be determined
then the algorithm is secure. I think this is an accurate assessment of
the arguments that need to be proven or disproved to assert a break. I
chose 2048 bits since that is standard RSA key size still in use many
places. That would give us a Shadow Numbers key with two integers, total
size of 2048+ bits, as close to 2048 as we can generate in a short time.

If you or anyone else is down to attack the cryptosystem, let me know. I
can post the testing reference implementation as Python source code, and
some attack vectors to crack, and some of my own inspections of the
numerical oddities.

-- 
███████████████████████████████████
█░░░░░░░░░░░█░░░░░░░░███░░░░░░░░███
█░░███████░░█░░████░░███░░████░░███        [chan] 711
█░░░░░░░██░░█░░░░██░░███░░░░██░░███        spooky mart
██████░░██░░███░░██░░█████░░██░░███        always open
██████░░██░░███░░██░░█████░░██░░███        stay spooky
██████░░██░░█░░░░██░░░░█░░░░██░░░░█        https://bitmessage.org
██████░░██░░█░░██████░░█░░██████░░█
██████░░░░░░█░░░░░░░░░░█░░░░░░░░░░█
███████████████████████████████████

[toc] | [prev] | [next] | [standalone]

#50301

On Sat, 2 Oct 2021 09:08:16 -0500, 711 Spooky Mart <711@spooky.mart> wrote:
> On 10/1/21 10:52 AM, Peter Pearson wrote:
>> On Thu, 30 Sep 2021 12:43:16 -0500, 711 Spooky Mart <711@spooky.mart> wrote:
>>>
>>> https://eprint.iacr.org/2014/335
[snip]
>> 
>> As best I can tell (the presentation is awfully muddled), the
>> public key is a multiplier "Sara" and a modulus "Bra", and message M is
>> encrypted as
>> 
>>   e = (M * Sara) mod Bra
>> 
>> while the private key is another multiplier "Sbr" and another modulus "B",
>> and ciphertext is decrypted as
>> 
>>   d = (e * Sbr) mod B.
>> 
>> This algorithm is so far from being cryptographically sound that
>> I'm afraid I must be missing some big, obvious, April-fools-day
>> joke.
>
[snip]
>
> The cryptosystem is based on the DH idea of hidden subgroup membership,
> then the trap door is a combination of factoring composites (easy to do)
> combined with exponentiation and addition of exponents (hard to do).
> Prime numbers are not required for key generation. The exponentiation
> and addition obfuscate the subgroup relationship between the numbers so
> that discrete logarithm can't be computed with the usual algorithms. How
> would one prove this is less hard than factoring RSA/Rabin semiprimes?

Is my description of the encryption and decryption processes wrong?
I took those two lines straight from the paper, but maybe I missed
some explanation about how this wasn't the real algorithm.

If my description of the algorithm is wrong, please present the
correct algorithm.  

If my description is correct, please provide sample values for
e, Sara, and Bra, and I will either tell you what M is, or
demonstrate that there is no unique decryption of e.

-- 
To email me, substitute nowhere->runbox, invalid->com.

[toc] | [prev] | [next] | [standalone]

#50382 — Re: [BORKED] IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION

On 10/2/21 10:34 AM, Peter Pearson wrote:

> Is my description of the encryption and decryption processes wrong?
> I took those two lines straight from the paper, but maybe I missed
> some explanation about how this wasn't the real algorithm.
> 
> If my description of the algorithm is wrong, please present the
> correct algorithm.  
> 
> If my description is correct, please provide sample values for
> e, Sara, and Bra, and I will either tell you what M is, or
> demonstrate that there is no unique decryption of e.
> 

O, snap! Now I must belay this exercise. The system is borked, as you
said, Mr. Pearson. Secret and public values commute like a bus. Here is
a sample output you will probably break fast. Enjoy:

pubkey (Sara, Bra)  :
   57333613759833334679914302455108124,
   320632539812891314264995223041035707802067

ciphertext (e) :
   289609149406663016296773405950344946146989

Even with the exponentiation and addition as specified in the paper the
private base can be recovered from the public raised base modulus. The
public modulus is a multiple of half the private key (Sb, Sbr). With a
little searching we can get the common factors and recover both shadow
numbers. Here's a demonstration of all values in a keygen and ciphering,
showing borked with zero moduli.

shadow1 :  10838689
shadow2 :  121499449
base    :  1316894741382360
privkey :  900923299802569 1316894741382360
pubkey  :  56389746240577907081847078295741930609,
2283774347030095339404262922298287777443461960
adder   :  11
mbase   : 14485842155205960
borked? : mod 0
plaintext :  711
encrypted :  40093109577050891935193272668272512662999
decrypted :  711

In this example the plaintext is a factor of the ciphertext and the
private key is a factor of the public key, so it is totally insecure.
The exponentiation and addition trick doesn't work--it just shifts the
relationships of the common denominators into bigger composites. I don't
know why I didn't see that in the example in the paper, because it is
obvious to me now.

I will be checking my implementation for errors while trying to find
other ways to break it. I'll check back later and post more for anyone
else who wants to tinker, and maybe find additional breaks, or a way to
remedy them and cobble together a better toy cryptosystem to attack.

-- 
░░░█████░░░████░░░░████░░░░░ . . .    [chan] 711
░░░░░░██░░░░░██░░░░░░██░░░░░ . . .    spooky mart
░░░░░░██░░░░░██░░░░░░██░░░░░ . . .    always open
░░░░░░██░░░██████░░██████░░░ . . .    https://bitmessage.org

[toc] | [prev] | [next] | [standalone]

#50401 — Re: [BORKED] IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION

On Mon, 4 Oct 2021 16:25:30 -0500, 711 Spooky Mart <711@spooky.mart> wrote:
> On 10/2/21 10:34 AM, Peter Pearson wrote:
>
>> Is my description of the encryption and decryption processes wrong?
>> I took those two lines straight from the paper, but maybe I missed
>> some explanation about how this wasn't the real algorithm.
>> 
>> If my description of the algorithm is wrong, please present the
>> correct algorithm.  
>> 
>> If my description is correct, please provide sample values for
>> e, Sara, and Bra, and I will either tell you what M is, or
>> demonstrate that there is no unique decryption of e.
>> 
>
> O, snap! Now I must belay this exercise. The system is borked, as you
> said, Mr. Pearson. Secret and public values commute like a bus. Here is
> a sample output you will probably break fast. Enjoy:
>
> pubkey (Sara, Bra)  :
>    57333613759833334679914302455108124,
>    320632539812891314264995223041035707802067
>
> ciphertext (e) :
>    289609149406663016296773405950344946146989

So, the challenge is to find the secret message m such that
e = (m * Sara) mod Bra.

    $ python
    >>> import numbertheory
    >>> Sara = 57333613759833334679914302455108124
    >>> Bra = 320632539812891314264995223041035707802067
    >>> e = 289609149406663016296773405950344946146989
    >>> d = numbertheory.inverse_mod(Sara, Bra)
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
      File "numbertheory.py", line 226, in inverse_mod
        assert d == 1
    AssertionError

Oops!  Stubbed my toe.

Note that if Sara and Bra have a greatest common divisor greater than 1,
then there will be more than one plaintext in the range [0, Bra-1]
that encrypt to the same ciphertext.  For that reason, I assumed that
Sara and Bra were relatively prime.  But Sara and Bra having a common
factor is more of a problem for the users of the cipher than for the
attacker.  The attack continues:

    >>> g = numbertheory.gcd(Sara, Bra)
    >>> g
    3L
    >>> d = numbertheory.inverse_mod(Sara/g, Bra/g)
    >>> m = ((e/g)*d) % (Bra/g)
    >>> m
    33013301L
    >>> (Sara * m) % Bra
    289609149406663016296773405950344946146989L
    >>> (Sara * m) % Bra - e
    0L

So, m encrypts to the challenge's ciphertext.

And here are two more m's that encrypt to the same ciphertext:

    >>> m1 = m + Bra/g
    >>> (Sara * m1) % Bra
    289609149406663016296773405950344946146989L
    >>> m2 = m1 + Bra/g
    >>> (Sara * m2) % Bra
    289609149406663016296773405950344946146989L


-- 
To email me, substitute nowhere->runbox, invalid->com.

[toc] | [prev] | [next] | [standalone]

#50407 — Re: [BORKED] IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION

On 10/5/21 10:20 AM, Peter Pearson wrote:

>> pubkey (Sara, Bra)  :
>>    57333613759833334679914302455108124,
>>    320632539812891314264995223041035707802067
>>
>> ciphertext (e) :
>>    289609149406663016296773405950344946146989
> 
> So, the challenge is to find the secret message m such that
> e = (m * Sara) mod Bra.
> 
>     $ python
>     >>> import numbertheory
>     >>> Sara = 57333613759833334679914302455108124
>     >>> Bra = 320632539812891314264995223041035707802067
>     >>> e = 289609149406663016296773405950344946146989
>     >>> d = numbertheory.inverse_mod(Sara, Bra)
>     Traceback (most recent call last):
>       File "<stdin>", line 1, in <module>
>       File "numbertheory.py", line 226, in inverse_mod
>         assert d == 1
>     AssertionError
> 
> Oops!  Stubbed my toe.
> 
> Note that if Sara and Bra have a greatest common divisor greater than 1,
> then there will be more than one plaintext in the range [0, Bra-1]
> that encrypt to the same ciphertext.  For that reason, I assumed that
> Sara and Bra were relatively prime.  But Sara and Bra having a common
> factor is more of a problem for the users of the cipher than for the
> attacker.  The attack continues:
> 
>     >>> g = numbertheory.gcd(Sara, Bra)
>     >>> g
>     3L
>     >>> d = numbertheory.inverse_mod(Sara/g, Bra/g)
>     >>> m = ((e/g)*d) % (Bra/g)
>     >>> m
>     33013301L
>     >>> (Sara * m) % Bra
>     289609149406663016296773405950344946146989L
>     >>> (Sara * m) % Bra - e
>     0L
> 
> So, m encrypts to the challenge's ciphertext.
> 
> And here are two more m's that encrypt to the same ciphertext:
> 
>     >>> m1 = m + Bra/g
>     >>> (Sara * m1) % Bra
>     289609149406663016296773405950344946146989L
>     >>> m2 = m1 + Bra/g
>     >>> (Sara * m2) % Bra
>     289609149406663016296773405950344946146989L

'3301330' is the correct m. This replicates repeatedly with random inputs.

Although the exponentiation does seem to make computing inverse or
logarithm to the seed (Sa, Sb) values harder, it doesn't hide common
factors, and worse the plaintext becomes a divisor of the ciphertext. We
can guess the plaintext by randomly sampling and re-arranging the
ciphertext factors until we get one that works as a key to whatever
stream cipher would be packaged with the payload. Even with big keys a
GPU sort would crunch right through.

Since both the public key numbers are raised to the same power, subject
to the same modulus divisor, then incremented with the same additive,
they still share factors with the hidden key material and the plaintext.

Thanks for cracking at this. Do you notice any more ways to break this
system?

-- 
███████████████████████████████████
█░░░░░░░░░░░█░░░░░░░░███░░░░░░░░███
█░░███████░░█░░████░░███░░████░░███        [chan] 711
█░░░░░░░██░░█░░░░██░░███░░░░██░░███        spooky mart
██████░░██░░███░░██░░█████░░██░░███        always open
██████░░██░░███░░██░░█████░░██░░███        stay spooky
██████░░██░░█░░░░██░░░░█░░░░██░░░░█        https://bitmessage.org
██████░░██░░█░░██████░░█░░██████░░█
██████░░░░░░█░░░░░░░░░░█░░░░░░░░░░█
███████████████████████████████████

[toc] | [prev] | [next] | [standalone]

#50410 — Re: [BORKED] IACR eprint: SHADOW NUMBERS PUBLIC KEY ENCRYPTION

For reference sake, message m is encrypted to produce ciphertext e
by e = (m * Sara) mod Bra.


On Tue, 5 Oct 2021 14:26:32 -0500, 711 Spooky Mart <711@spooky.mart> wrote:
[snip]
>
> Thanks for cracking at this. Do you notice any more ways to break this
> system?
>

First, note that cryptologists use a much broader definition of "break"
than simply "I can find the plaintext from a single ciphertext."  One
demanding example, for example, is: given a paintext and two ciphertexts,
one of which will decrypt to that plaintext, it should be computationally
infeasible to guess, with probability greater than 1/2, which ciphertext 
works.  (Not all interesting ciphers meet that demand, but it illustrates
the neighborhood in which discussion takes place.)

Advice of a more practical nature: the field or ring in which your
encryption and decryption happen has far more "structure" than is
required to encrypt and decrypt, and that extra structure, while it
does nothing for you, is useful to the attacker.  The fact that
encrypt(m1+m2) = encrypt(m1) + encrypt(m2) mod Bra would worry me
a lot.

-- 
To email me, substitute nowhere->runbox, invalid->com.

[toc] | [prev] | [standalone]

Back to top | Article view | sci.crypt

csiph-web