info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Post Quantum Cryptography Scheme - Quarkz
115 views
Skip to first unread message
Tavian Robertson
May 17, 2021, 3:38:19 PM5/17/21
to
I have created a cryptographic scheme that I believe to be quantum secure. I have a technical write up describing how the algorithm works here:
https://docs.google.com/document/d/1lkPAdd-AOcos1G1m9SIPzCQeUe4DH5eviVi7iuLOt2s/edit?usp=sharing
I also have an implementation of the library written here:
https://github.com/quarkz-encryption/Quarkz
I would love to receive some feedback. Do you guys see any vulnerabilities or mishaps?
-Tavian
https://docs.google.com/document/d/1lkPAdd-AOcos1G1m9SIPzCQeUe4DH5eviVi7iuLOt2s/edit?usp=sharing
I also have an implementation of the library written here:
https://github.com/quarkz-encryption/Quarkz
I would love to receive some feedback. Do you guys see any vulnerabilities or mishaps?
-Tavian
Stefan Claas
May 17, 2021, 3:43:41 PM5/17/21
to
NIST documents, regarding this topic and see what the finalists have
to offer in this regard.
Maybe useful for you.
<https://csrc.nist.gov/News/2020/pqc-third-round-candidate-announcement>
Regards
Stefan
--
When the phone was tied with a wire, humans were free.
Message has been deleted
Tavian Robertson
May 17, 2021, 3:52:25 PM5/17/21
to
Thank you for your response. I am aware of the NIST competition, but it was too late to get in. My algorithm hits a sweet spot as the key sizes are not too big, but can be applied to any algorithm like ECC or RSA that uses modulo to reduce the problem. It may even be able to work with lattice based crypto schemes that apply modular arithmetic. The current implementation is designed around RSA.
Thanks,
Tavian
Stefan Claas
May 17, 2021, 4:04:50 PM5/17/21
to
peer review your implementation.
Best regards
Stefan Claas
May 17, 2021, 4:12:12 PM5/17/21
to
ah, ok. Thanks for pointing this out. Hopefully some people like to
peer review your implementation.
Best regards
Best regards
Max
May 17, 2021, 6:31:41 PM5/17/21
to
just a question: As c, e and o are publicly known, shouldn't Shor's
algorithm give you m from c = m**e mod o?
What am I missing here?
Cheers,
Max
Tavian Robertson
May 17, 2021, 6:40:05 PM5/17/21
to
Thank you for your question. Shor's algorithm is capable of finding factors of large numbers in polynomial time as well as discrete logarithms in polynomial time. c = m**e mod o uses modular arithemetic. This means that you are simply finding the remainer of (m**e) / o. Thus if you say o = 7 and m**e = 121 then the remainder or c = 2. But once again there are other numbers for m**e that would produce 2. This includes 9, 16, ect. Thus the attacker would need to guess the correct message. Shor's algorithm has no hand in this as it is not capable of telling you what the correct value of m**e is to decrypt the information.
Thank you,
Tavian
Chris M. Thomasson
May 17, 2021, 7:18:09 PM5/17/21
to
https://en.wikipedia.org/wiki/Q_Sharp
?
Max
May 17, 2021, 7:26:38 PM5/17/21
to
right? So the sender has to include count by means of offset.
Interesting. I'll dig deeper into this when I find the time.
Cheers,
Max
Tavian Robertson
May 17, 2021, 7:31:14 PM5/17/21
to
I have not heard of Q#. It is simply used to create quantum algorithms correct?
Tavian Robertson
May 17, 2021, 7:34:05 PM5/17/21
to
That is correct. It is an interesting equation I have found. I am not a complete expert, and thus I cannot say with complete certainty that Shor's algorithm can apply to m**e mod o in terms of the period. As far as my understanding of Shor's algorithm goes, it would only be useful for finding the factors of o, not m itself. Finding factors of o does no good as it is impossible for one to create a keypair with e and o considering phi(o) and e are not relatively prime.
-Tavian
wizzofozz
May 29, 2021, 7:15:35 AM5/29/21
to
Op 17-5-2021 om 21:38 schreef Tavian Robertson:
Your googledocs has a typo in section 2.1. first sentence.
"Based on the key generation in section 1.2 we can determine that n and
ratio are both known values to an attacker as they are in the public
key". You mean "o and ratio" because n is secret. This may sound
pedantic, but it is complicated enough as it is, and I have to be sure
that's everything is correct in order to try to understand it (which I
don't yet).
Also, you state in 2.1.; "Not only that, the attacker would then have to
use a quantum computer with Shor’s algorithm to find the value of d in
the private key in order to fully decrypt the ciphertext.". But isn't
the point of all of this, that the attacker has a quantum computer with
Shor's algorithm? I think that should be the premise, so we have "only
that", iiuc.
In RSA, the message length is bounded by the size of n (p*q). Is in your
scheme the message length bounded by o? Is that a problem?
RSA has some special values for m (0,1) to deal with. Is that a problem
for your algorithm?
Your ciphertext also contains 'offset', which is pretty huge. So the
plaintext is transformed in a much larger message. Maybe that's
acceptable when only encrypting the key of some symmetric cipher, but
just saying (I think you would need to address that in your paper).
Is the "ratio" really a ratio, as in the rational numbers? (if so, don't
you get into trouble with rounding errors and such?)
Like I said, I find it tricky to follow the rationale behind your
scheme. If I find the time, maybe I post a followup but don't count to
much on it.
Ozz
"Based on the key generation in section 1.2 we can determine that n and
ratio are both known values to an attacker as they are in the public
key". You mean "o and ratio" because n is secret. This may sound
pedantic, but it is complicated enough as it is, and I have to be sure
that's everything is correct in order to try to understand it (which I
don't yet).
Also, you state in 2.1.; "Not only that, the attacker would then have to
use a quantum computer with Shor’s algorithm to find the value of d in
the private key in order to fully decrypt the ciphertext.". But isn't
the point of all of this, that the attacker has a quantum computer with
Shor's algorithm? I think that should be the premise, so we have "only
that", iiuc.
In RSA, the message length is bounded by the size of n (p*q). Is in your
scheme the message length bounded by o? Is that a problem?
RSA has some special values for m (0,1) to deal with. Is that a problem
for your algorithm?
Your ciphertext also contains 'offset', which is pretty huge. So the
plaintext is transformed in a much larger message. Maybe that's
acceptable when only encrypting the key of some symmetric cipher, but
just saying (I think you would need to address that in your paper).
Is the "ratio" really a ratio, as in the rational numbers? (if so, don't
you get into trouble with rounding errors and such?)
Like I said, I find it tricky to follow the rationale behind your
scheme. If I find the time, maybe I post a followup but don't count to
much on it.
Ozz
Tavian Robertson
May 29, 2021, 9:20:20 PM5/29/21
to
To answer a few of your questions.
The size of the plaintext input is bounded by the size of n as per usual with RSA. The reason for this is because the algorithm is still working with n, that is the purpose for the offset.
The algorithm is very unprofessional at the moment and I have not fixed a lot of very bug problems. This algorithm as of now would only be practical for transferring symmetric keys between endpoints.
I have also found ways to break the algorithm itself, As the decimal values produced as the ratio are irrational numbers. This means it is possible for an attacker to find the values used to create that number in polynomial time. I am looking at using modular arithemitic to solve this similar to this alternative diffie hellman method: https://billatnapier.medium.com/an-alternative-diffie-hellman-method-and-what-is-mod-1-55d0c4b9d0.
Thank you,
Tavian
Max
May 30, 2021, 12:26:49 PM5/30/21
to
On 30.05.21 03:20, Tavian Robertson wrote:
> I am looking at using modular arithemitic to solve this similar to this alternative diffie hellman method: https://billatnapier.medium.com/an-alternative-diffie-hellman-method-and-what-is-mod-1-55d0c4b9d0.
Am I getting it right that this "alternate Diffie-Hellman-algorithm"
> I am looking at using modular arithemitic to solve this similar to this alternative diffie hellman method: https://billatnapier.medium.com/an-alternative-diffie-hellman-method-and-what-is-mod-1-55d0c4b9d0.
1. suggests using DH over the multiplicative group of integers modulo n
with multiplication (instead of exponentiation) and poorly tries to veil
this by talking about "real numbers" with "some specified finite number
of digits of accuracy"?
2. thus, completely ignores that the multiplicative inverse can be
efficiently calculated via the extended Euclidean algorithm?
3. takes a power of 10 as the modulo, thus, not even a prime number?
4. gets all its secrecy from an initially shared secret between Alice
and Bob, namely the base and/or the (length of) the modulo?
If I got this right, this is just a terrible idea on top of a fog
machine, if not, this might be an opportunity for me to learn something.
In the past and recently, there have been several algorithms suggested
on this forum based on the mathematics of real numbers that all made the
same mistake:
Computers (and any other digital representation of information) don't do
real numbers. They only do integers that may be disguised as "real
numbers with finite precision". Best those algorithms can do, is using
very high precision, aka tons of bits of key-length. But long key
lengths are inconvenient plus, if the security of the algorithm is
significantly lower than the key length, it just isn't a good algorithm.
Chris M. Thomasson
Jun 1, 2021, 8:42:15 PM6/1/21
to
On 5/30/2021 9:26 AM, Max wrote:
> On 30.05.21 03:20, Tavian Robertson wrote:
>> I am looking at using modular arithemitic to solve this similar to
>> this alternative diffie hellman method:
>> https://billatnapier.medium.com/an-alternative-diffie-hellman-method-and-what-is-mod-1-55d0c4b9d0.
>>
>
> Am I getting it right that this "alternate Diffie-Hellman-algorithm"
>
> 1. suggests using DH over the multiplicative group of integers modulo n
> with multiplication (instead of exponentiation) and poorly tries to veil
> this by talking about "real numbers" with "some specified finite number
> of digits of accuracy"?
>
> 2. thus, completely ignores that the multiplicative inverse can be
> efficiently calculated via the extended Euclidean algorithm?
>
> 3. takes a power of 10 as the modulo, thus, not even a prime number?
>
> 4. gets all its secrecy from an initially shared secret between Alice
> and Bob, namely the base and/or the (length of) the modulo?
>
> If I got this right, this is just a terrible idea on top of a fog
> machine, if not, this might be an opportunity for me to learn something.
>
> In the past and recently, there have been several algorithms suggested
> on this forum based on the mathematics of real numbers that all made the
> same mistake:
[ot, no hijack intended!]: Indeed! Btw, do you know of a good JavaScript
> On 30.05.21 03:20, Tavian Robertson wrote:
>> I am looking at using modular arithemitic to solve this similar to
>> this alternative diffie hellman method:
>> https://billatnapier.medium.com/an-alternative-diffie-hellman-method-and-what-is-mod-1-55d0c4b9d0.
>>
>
> Am I getting it right that this "alternate Diffie-Hellman-algorithm"
>
> 1. suggests using DH over the multiplicative group of integers modulo n
> with multiplication (instead of exponentiation) and poorly tries to veil
> this by talking about "real numbers" with "some specified finite number
> of digits of accuracy"?
>
> 2. thus, completely ignores that the multiplicative inverse can be
> efficiently calculated via the extended Euclidean algorithm?
>
> 3. takes a power of 10 as the modulo, thus, not even a prime number?
>
> 4. gets all its secrecy from an initially shared secret between Alice
> and Bob, namely the base and/or the (length of) the modulo?
>
> If I got this right, this is just a terrible idea on top of a fog
> machine, if not, this might be an opportunity for me to learn something.
>
> In the past and recently, there have been several algorithms suggested
> on this forum based on the mathematics of real numbers that all made the
> same mistake:
lib that has trig functions with arbitrary precision? If so, start a new
thread for any suggestions you may have. Thanks.
Piergiorgio Sartor
Jun 2, 2021, 12:48:55 PM6/2/21
to
On 30/05/2021 18.26, Max wrote:
[...]
Computation in FP are strictly order dependent.
So, things like a+b+c can have different result
than b+a+c.
Since compilers do not require to preserve order,
the same program, in FP, can deliver different
results depending on the conditions it was
generated (compiler, optimization, ...) or in
which HW runs (different CPU can decide to
re-order differently).
In integer, on the other hand, the order is not
relevant, even in certain overflow / underflow
(particular) cases.
So, one should create "reals" by means of
integers, which is pointless (usually).
bye,
--
piergiorgio
[...]
> In the past and recently, there have been several algorithms suggested
> on this forum based on the mathematics of real numbers that all made the
> same mistake:
> Computers (and any other digital representation of information) don't do
> real numbers. They only do integers that may be disguised as "real
> numbers with finite precision". Best those algorithms can do, is using
> very high precision, aka tons of bits of key-length. But long key
> lengths are inconvenient plus, if the security of the algorithm is
> significantly lower than the key length, it just isn't a good algorithm.
There is also an other issue.
> on this forum based on the mathematics of real numbers that all made the
> same mistake:
> Computers (and any other digital representation of information) don't do
> real numbers. They only do integers that may be disguised as "real
> numbers with finite precision". Best those algorithms can do, is using
> very high precision, aka tons of bits of key-length. But long key
> lengths are inconvenient plus, if the security of the algorithm is
> significantly lower than the key length, it just isn't a good algorithm.
Computation in FP are strictly order dependent.
So, things like a+b+c can have different result
than b+a+c.
Since compilers do not require to preserve order,
the same program, in FP, can deliver different
results depending on the conditions it was
generated (compiler, optimization, ...) or in
which HW runs (different CPU can decide to
re-order differently).
In integer, on the other hand, the order is not
relevant, even in certain overflow / underflow
(particular) cases.
So, one should create "reals" by means of
integers, which is pointless (usually).
bye,
--
piergiorgio
wizzofozz
Jun 5, 2021, 5:42:01 AM6/5/21
to
Op 30-5-2021 om 18:26 schreef Max:
from the quoted article)
>
> Am I getting it right that this "alternate Diffie-Hellman-algorithm"
>
> 1. suggests using DH over the multiplicative group of integers modulo n
> with multiplication (instead of exponentiation) and poorly tries to veil
> this by talking about "real numbers" with "some specified finite number
> of digits of accuracy"?
>
> 2. thus, completely ignores that the multiplicative inverse can be
> efficiently calculated via the extended Euclidean algorithm?
>
> 3. takes a power of 10 as the modulo, thus, not even a prime number?
The only context, where I have read about "a power of 10 as the modulo"
is in the attack on the algorithm (described by the author himself and
not ignored as you state in point 2). You multiply everything by a large
enough power (to make it integers), and then you can use the extended
Euclidean algorithm to find the secrets. "Not even a prime number"
mitigates the attack somewhat, since in this case an inverse does not
always exists.
I played with some numbers to test this:
s=0.414213561 (public)
a=31 (secret by Alice)
n=10**9 (calced by Eve, based on s)
gcd(s*n,n) = gcd(414213561,10**9) = 1
mi = 683004041 ( mod_inverse(n*s,n), mod_inverse() stolen from OP's github)
s*a%1 = 0.840620391 (intercepted by Eve, rounded by me (here we go already))
int(round((s*a%1)*n))*mi%n => 31 (Eve found a, and will now intercept Bob)
However if s had been 0.414213562, then there is no inverse.
>
> 4. gets all its secrecy from an initially shared secret between Alice
> and Bob, namely the base and/or the (length of) the modulo?
>
The author describes two "versions", where in one version there are no
shared secrets (except for the usual DH params). The modulo is always 1.
Keeping the base secret is an extra layer of security.
> If I got this right, this is just a terrible idea on top of a fog
> machine, if not, this might be an opportunity for me to learn something.
I would expect that if this was a good idea, someone (maybe even DH
themselves) would have proposed it a long time ago.
Cheers,
Ozz
> On 30.05.21 03:20, Tavian Robertson wrote:
>> I am looking at using modular arithemitic to solve this similar to
>> this alternative diffie hellman method:
>> https://billatnapier.medium.com/an-alternative-diffie-hellman-method-and-what-is-mod-1-55d0c4b9d0.
>>
The actual paper is here: https://www.mdpi.com/2410-387X/4/1/5/pdf (link
>> I am looking at using modular arithemitic to solve this similar to
>> this alternative diffie hellman method:
>> https://billatnapier.medium.com/an-alternative-diffie-hellman-method-and-what-is-mod-1-55d0c4b9d0.
>>
from the quoted article)
>
> Am I getting it right that this "alternate Diffie-Hellman-algorithm"
>
> 1. suggests using DH over the multiplicative group of integers modulo n
> with multiplication (instead of exponentiation) and poorly tries to veil
> this by talking about "real numbers" with "some specified finite number
> of digits of accuracy"?
>
> 2. thus, completely ignores that the multiplicative inverse can be
> efficiently calculated via the extended Euclidean algorithm?
>
> 3. takes a power of 10 as the modulo, thus, not even a prime number?
is in the attack on the algorithm (described by the author himself and
not ignored as you state in point 2). You multiply everything by a large
enough power (to make it integers), and then you can use the extended
Euclidean algorithm to find the secrets. "Not even a prime number"
mitigates the attack somewhat, since in this case an inverse does not
always exists.
I played with some numbers to test this:
s=0.414213561 (public)
a=31 (secret by Alice)
n=10**9 (calced by Eve, based on s)
gcd(s*n,n) = gcd(414213561,10**9) = 1
mi = 683004041 ( mod_inverse(n*s,n), mod_inverse() stolen from OP's github)
s*a%1 = 0.840620391 (intercepted by Eve, rounded by me (here we go already))
int(round((s*a%1)*n))*mi%n => 31 (Eve found a, and will now intercept Bob)
However if s had been 0.414213562, then there is no inverse.
>
> 4. gets all its secrecy from an initially shared secret between Alice
> and Bob, namely the base and/or the (length of) the modulo?
>
shared secrets (except for the usual DH params). The modulo is always 1.
Keeping the base secret is an extra layer of security.
> If I got this right, this is just a terrible idea on top of a fog
> machine, if not, this might be an opportunity for me to learn something.
themselves) would have proposed it a long time ago.
Cheers,
Ozz
wizzofozz
Jun 6, 2021, 5:30:11 AM6/6/21
to
Op 5-6-2021 om 11:41 schreef wizzofozz:
it turns out we can divide out the common factor 2 in the case of s =
0.414213562 (the modulus becomes 10**9/2). We then find two solutions,
namely a=31 (the secret of alice) and a=500000031. Eve would probably
also get 2 solutions for b, and so should probably check 4 candidate
keys. Still better than bruteforce I suppose.
I wonder what we're missing here. The paper looks decent, and the author
seems to know what he's talking about. Probably my numbers are just too
small.
Ozz
> Op 30-5-2021 om 18:26 schreef Max:
>>
>>
>> 2. thus, completely ignores that the multiplicative inverse can be
>> efficiently calculated via the extended Euclidean algorithm?
>>
>> 3. takes a power of 10 as the modulo, thus, not even a prime number?
>
> The only context, where I have read about "a power of 10 as the modulo"
> is in the attack on the algorithm (described by the author himself and
> not ignored as you state in point 2). You multiply everything by a large
> enough power (to make it integers), and then you can use the extended
> Euclidean algorithm to find the secrets. "Not even a prime number"
> mitigates the attack somewhat, since in this case an inverse does not
> always exists.
> I played with some numbers to test this:
>
> s=0.414213561 (public)
> a=31 (secret by Alice)
> n=10**9 (calced by Eve, based on s)
> gcd(s*n,n) = gcd(414213561,10**9) = 1
> mi = 683004041 ( mod_inverse(n*s,n), mod_inverse() stolen from OP's github)
> s*a%1 = 0.840620391 (intercepted by Eve, rounded by me (here we go
> already))
> int(round((s*a%1)*n))*mi%n => 31 (Eve found a, and will now intercept Bob)
>
> However if s had been 0.414213562, then there is no inverse.
After googling some more (I should have paid more attention in school),
>> efficiently calculated via the extended Euclidean algorithm?
>>
>> 3. takes a power of 10 as the modulo, thus, not even a prime number?
>
> The only context, where I have read about "a power of 10 as the modulo"
> is in the attack on the algorithm (described by the author himself and
> not ignored as you state in point 2). You multiply everything by a large
> enough power (to make it integers), and then you can use the extended
> Euclidean algorithm to find the secrets. "Not even a prime number"
> mitigates the attack somewhat, since in this case an inverse does not
> always exists.
> I played with some numbers to test this:
>
> s=0.414213561 (public)
> a=31 (secret by Alice)
> n=10**9 (calced by Eve, based on s)
> gcd(s*n,n) = gcd(414213561,10**9) = 1
> mi = 683004041 ( mod_inverse(n*s,n), mod_inverse() stolen from OP's github)
> s*a%1 = 0.840620391 (intercepted by Eve, rounded by me (here we go
> already))
> int(round((s*a%1)*n))*mi%n => 31 (Eve found a, and will now intercept Bob)
>
> However if s had been 0.414213562, then there is no inverse.
it turns out we can divide out the common factor 2 in the case of s =
0.414213562 (the modulus becomes 10**9/2). We then find two solutions,
namely a=31 (the secret of alice) and a=500000031. Eve would probably
also get 2 solutions for b, and so should probably check 4 candidate
keys. Still better than bruteforce I suppose.
I wonder what we're missing here. The paper looks decent, and the author
seems to know what he's talking about. Probably my numbers are just too
small.
Ozz
Max
Jun 6, 2021, 10:16:27 AM6/6/21
to
I'm still digesting your yesterday's answer. I dug myself in a hole
there by pointing out the weakness of the modulo not being prime and
then coming up with the Extended Euclidean Algorithm, right?
Thanks for digging deeper here. Yes, if the modulo isn't prime we get
those sub-rings with shorter periods giving Bob (and Eve) more than one
result they have to check and Eve a faster way to find a as the
different possible keys are always a period length apart.
I agree, the paper looks decent, but I really cringe at some of its
general ideas:
1. "layers of security"
Slapping together 2 half-assed security measures to get to your desired
security level is, at least in cryptography, highly dubious to me.
2. mixing up two such completely different approaches (no-shared-secret
key exchange vs shared-key enhancement) in one paper with one underlying
algorithm.
Just look at 3. (page 4):
"If the transcendental x is distributed via a secure channel, why not
use this number directly as the encryption key?
[...]
using the transcendental x as the encryption key would, of course, be a
possibility. A problem though is one of robustness; if the secrecy of
this number was to be compromised, the encryption would be completely
broken if this was the actual key. However, with this protocol, the rest
of the procedure would then serve as an additional layer of security."
That's reasonable thinking, but that's what one might use a salted
decent hash for or something and it has definitely nothing to do with
Diffie-Hellman and thus with the title of the paper. That's why I only
consider thinking about this with "the transcendental x" being in the open.
3. Trying to solve the EEA-attack with a longer key
Then again, in the additional explanation at the original link of the OP
(https://billatnapier.medium.com/an-alternative-diffie-hellman-method-and-what-is-mod-1-55d0c4b9d0)
the author says:
"[...] one can make an attack simply based on the Euclidean algorithm.
So the keys have to be so long that it would take this attack the
desired amount of time to break."
This is a fallacy in itself. The EEA is efficient (it runs in polynomial
time,
https://en.wikipedia.org/wiki/Time_complexity#Strongly_and_weakly_polynomial_time),
so if it is applicable to an algorithm, this simply is no
one-way-function and no key-length will really save you. Either Eve can
break it or Bob has a hard time decrypting it himself.
4. Making the key-length part of the key
Then, in 3.1 the author writes:
"there is an additional element of difficulty for the cryptanalyst
provided by not knowing how many digits of accuracy in the
transcendental are needed for the actual encryption key."
So the length of the key is also part of the key? How long could it be?
65.000 bits? So I get 16 extra-bits of key max out of this? For the
price of a ridiculously long key?
Ozz, could this be a "pet project" of a professional mathematician with
just not that much of a cryptography background?
Apologies, if I offend anyone or sound cocky by writing this. It just
bothers me (a little). Especially, as at first glance the paper looks so
neat.
Cheers,
Max
wizzofozz
Jun 6, 2021, 11:26:56 AM6/6/21
to
Op 6-6-2021 om 16:16 schreef Max:
when a modulus is required to be prime (or relatively prime to
something), the requirements are there to ensure that the algorithm
works in the first place (otherwise "unique" decryption is not possible
for example).
I don't think it applies here that the modulo is required to be prime,
since "mod 1" is the only modulo operation throughout the entire
algorithm. When we attack the algorithm, we are forced to use modulo's
of powers of 10, so that's at least an advantage (for Alice and Bob) in
this case.
> Thanks for digging deeper here. Yes, if the modulo isn't prime we get
> those sub-rings with shorter periods giving Bob (and Eve) more than one
> result they have to check and Eve a faster way to find a as the
> different possible keys are always a period length apart.
I don't think that Bob would ever need to check anything (*); He just
multiplies 'whatever he got from Alice' with his own random 'b', and
then has established the key (Alice does the same on her end).
But now you mention it, there may be fewer possible keys because of
that. On the other hand, the modulus is 1, so not sure if it applies
here.
(*): according to the paper, they need to check that a != b and retry if
a == b. (makes sense, because Eve would notice that they both sent the
same number).
>
> I agree, the paper looks decent, but I really cringe at some of its
> general ideas:
>
>
> 1. "layers of security"
> Slapping together 2 half-assed security measures to get to your desired
> security level is, at least in cryptography, highly dubious to me.
>
>
> 2. mixing up two such completely different approaches (no-shared-secret
> key exchange vs shared-key enhancement) in one paper with one underlying
> algorithm.
>
> Just look at 3. (page 4):
> "If the transcendental x is distributed via a secure channel, why not
> use this number directly as the encryption key?
> [...]
> using the transcendental x as the encryption key would, of course, be a
> possibility. A problem though is one of robustness; if the secrecy of
> this number was to be compromised, the encryption would be completely
> broken if this was the actual key. However, with this protocol, the rest
> of the procedure would then serve as an additional layer of security."
>
> That's reasonable thinking, but that's what one might use a salted
> decent hash for or something and it has definitely nothing to do with
> Diffie-Hellman and thus with the title of the paper. That's why I only
> consider thinking about this with "the transcendental x" being in the open.
Yes, I agree with that. In my number example, I assumed that we know
what's also known in 'regular' DH.
> 3. Trying to solve the EEA-attack with a longer key
> Then again, in the additional explanation at the original link of the OP
> (https://billatnapier.medium.com/an-alternative-diffie-hellman-method-and-what-is-mod-1-55d0c4b9d0)
> the author says:
> "[...] one can make an attack simply based on the Euclidean algorithm.
> So the keys have to be so long that it would take this attack the
> desired amount of time to break."
>
> This is a fallacy in itself. The EEA is efficient (it runs in polynomial
> time,
> https://en.wikipedia.org/wiki/Time_complexity#Strongly_and_weakly_polynomial_time),
This is what I had troubles with as well. I suppose the author is saying
"if someone can break the numbers, use bigger numbers". But since we
don't need to bruteforce anything, the numbers would need to be very large.
> so if it is applicable to an algorithm, this simply is no
> one-way-function and no key-length will really save you. Either Eve can
> break it or Bob has a hard time decrypting it himself.
But Bob does not need to decrypt anything, he just needs to multiply his
'b' with Alice's 'a'.
> 4. Making the key-length part of the key
> Then, in 3.1 the author writes:
> "there is an additional element of difficulty for the cryptanalyst
> provided by not knowing how many digits of accuracy in the
> transcendental are needed for the actual encryption key."
>
> So the length of the key is also part of the key? How long could it be?
> 65.000 bits? So I get 16 extra-bits of key max out of this? For the
> price of a ridiculously long key?
Yes, valid point.
>
> Ozz, could this be a "pet project" of a professional mathematician with
> just not that much of a cryptography background?
I realy don't know. But I think any mathematician would have enough
crypto background to not publish very naive algorithms. So I give him
the benefit of the doubt for now that we're missing something.
> Apologies, if I offend anyone or sound cocky by writing this. It just
> bothers me (a little). Especially, as at first glance the paper looks so
> neat.
I don't think anyone is offended. At least it's on-topic, and if I were
the author of the paper, I would be happy that it was being discussed.
Ozz
> I'm still digesting your yesterday's answer. I dug myself in a hole
> there by pointing out the weakness of the modulo not being prime and
> then coming up with the Extended Euclidean Algorithm, right?
Well, I was a bit confused by it actually. As I understand it, normally
> there by pointing out the weakness of the modulo not being prime and
> then coming up with the Extended Euclidean Algorithm, right?
when a modulus is required to be prime (or relatively prime to
something), the requirements are there to ensure that the algorithm
works in the first place (otherwise "unique" decryption is not possible
for example).
I don't think it applies here that the modulo is required to be prime,
since "mod 1" is the only modulo operation throughout the entire
algorithm. When we attack the algorithm, we are forced to use modulo's
of powers of 10, so that's at least an advantage (for Alice and Bob) in
this case.
> Thanks for digging deeper here. Yes, if the modulo isn't prime we get
> those sub-rings with shorter periods giving Bob (and Eve) more than one
> result they have to check and Eve a faster way to find a as the
> different possible keys are always a period length apart.
multiplies 'whatever he got from Alice' with his own random 'b', and
then has established the key (Alice does the same on her end).
But now you mention it, there may be fewer possible keys because of
that. On the other hand, the modulus is 1, so not sure if it applies
here.
(*): according to the paper, they need to check that a != b and retry if
a == b. (makes sense, because Eve would notice that they both sent the
same number).
>
> I agree, the paper looks decent, but I really cringe at some of its
> general ideas:
>
>
> 1. "layers of security"
> Slapping together 2 half-assed security measures to get to your desired
> security level is, at least in cryptography, highly dubious to me.
>
>
> 2. mixing up two such completely different approaches (no-shared-secret
> key exchange vs shared-key enhancement) in one paper with one underlying
> algorithm.
>
> Just look at 3. (page 4):
> "If the transcendental x is distributed via a secure channel, why not
> use this number directly as the encryption key?
> [...]
> using the transcendental x as the encryption key would, of course, be a
> possibility. A problem though is one of robustness; if the secrecy of
> this number was to be compromised, the encryption would be completely
> broken if this was the actual key. However, with this protocol, the rest
> of the procedure would then serve as an additional layer of security."
>
> That's reasonable thinking, but that's what one might use a salted
> decent hash for or something and it has definitely nothing to do with
> Diffie-Hellman and thus with the title of the paper. That's why I only
> consider thinking about this with "the transcendental x" being in the open.
what's also known in 'regular' DH.
> 3. Trying to solve the EEA-attack with a longer key
> Then again, in the additional explanation at the original link of the OP
> (https://billatnapier.medium.com/an-alternative-diffie-hellman-method-and-what-is-mod-1-55d0c4b9d0)
> the author says:
> "[...] one can make an attack simply based on the Euclidean algorithm.
> So the keys have to be so long that it would take this attack the
> desired amount of time to break."
>
> This is a fallacy in itself. The EEA is efficient (it runs in polynomial
> time,
> https://en.wikipedia.org/wiki/Time_complexity#Strongly_and_weakly_polynomial_time),
"if someone can break the numbers, use bigger numbers". But since we
don't need to bruteforce anything, the numbers would need to be very large.
> so if it is applicable to an algorithm, this simply is no
> one-way-function and no key-length will really save you. Either Eve can
> break it or Bob has a hard time decrypting it himself.
'b' with Alice's 'a'.
> 4. Making the key-length part of the key
> Then, in 3.1 the author writes:
> "there is an additional element of difficulty for the cryptanalyst
> provided by not knowing how many digits of accuracy in the
> transcendental are needed for the actual encryption key."
>
> So the length of the key is also part of the key? How long could it be?
> 65.000 bits? So I get 16 extra-bits of key max out of this? For the
> price of a ridiculously long key?
>
> Ozz, could this be a "pet project" of a professional mathematician with
> just not that much of a cryptography background?
crypto background to not publish very naive algorithms. So I give him
the benefit of the doubt for now that we're missing something.
> Apologies, if I offend anyone or sound cocky by writing this. It just
> bothers me (a little). Especially, as at first glance the paper looks so
> neat.
the author of the paper, I would be happy that it was being discussed.
Ozz
Tavian Robertson
Sep 10, 2021, 11:13:29 PM9/10/21
to
Thank you,
Tavian
711 Spooky Mart
Sep 24, 2021, 5:07:01 PM9/24/21
to
--
███████████████████████████████████
█░░░░░░░░░░░█░░░░░░░░███░░░░░░░░███
█░░███████░░█░░████░░███░░████░░███ [chan] 711
█░░░░░░░██░░█░░░░██░░███░░░░██░░███ spooky mart
██████░░██░░███░░██░░█████░░██░░███ always open
██████░░██░░███░░██░░█████░░██░░███ stay spooky
██████░░██░░█░░░░██░░░░█░░░░██░░░░█ https://bitmessage.org
██████░░██░░█░░██████░░█░░██████░░█
██████░░░░░░█░░░░░░░░░░█░░░░░░░░░░█
███████████████████████████████████
Tavian Robertson
Oct 3, 2021, 9:41:28 PM10/3/21
to
Chris M. Thomasson
Oct 3, 2021, 11:30:54 PM10/3/21
to
functions, like HMAC.
0 new messages