Slashdot Mirror

...is provably collision-resistant.

http://senderek.de/SDLH/

'Proof' by Ron 'RSA' Rivest...

http://diswww.mit.edu/bloom-picayune/crypto/13190

SDLH is simple and secure to any number of bits of security desired once set up properly.

Factoring the modulus in SDLH is the only way to break it.

For that you need a state of the art number factoring algorithm (currently General Number Field Sieve or Shor's Algorithm).

Case closed.

Adi Shamir once proposed the following hash function:

          Let n = p*q be the product of two large primes, such that
          factoring n is believed to be infeasible.

          Let g be an element of maximum order in Z_n^* (i.e. an
          element of order lambda(n) = lcm(p-1,q-1)).

          Assume that n and g are fixed and public; p and q are secret.

          Let x be an input to be hashed, interpreted as a
          non-negative integer. (Of arbitrary length; this may be
          considerably larger than n.)

          Define hash(x) = g^x (mod n).

Then this hash function is provably collision-resistant, since
the ability to find a collision means that you have an x and
an x' such that

          hash(x) = hash(x')

which implies that

          x - x' = k * lambda(n)

for some k. That is a collision implies that you can find a
multiple of lambda(n). Being able to find a multiple of lambda(n)
means that you can factor n.

I would suggest this meets the specs of your query above.

                  Cheers,
                  Ron Rivest

Ronald L. Rivest
Room 324, 200 Technology Square, Cambridge MA 02139
Tel 617-253-5880, Fax 617-258-9738, Email

Adi Shamir once proposed the following hash function:

          Let n = p*q be the product of two large primes, such that
          factoring n is believed to be infeasible.

          Let g be an element of maximum order in Z_n^* (i.e. an
          element of order lambda(n) = lcm(p-1,q-1)).

          Assume that n and g are fixed and public; p and q are secret.

          Let x be an input to be hashed, interpreted as a
          non-negative integer. (Of arbitrary length; this may be
          considerably larger than n.)

          Define hash(x) = g^x (mod n).

Then this hash function is provably collision-resistant, since
the ability to find a collision means that you have an x and
an x' such that

          hash(x) = hash(x')

which implies that

          x - x' = k * lambda(n)

for some k. That is a collision implies that you can find a
multiple of lambda(n). Being able to find a multiple of lambda(n)
means that you can factor n.

I would suggest this meets the specs of your query above.

                  Cheers,
                  Ron Rivest

Ronald L. Rivest
Room 324, 200 Technology Square, Cambridge MA 02139
Tel 617-253-5880, Fax 617-258-9738, Email

These alternatives have been proven to be secure, likely just as secure as the 'big boys' like PGP and GPG.

Enjoy!

Tiny Encryption Algorithm

Pure Crypto Project

CipherSaber (CAUTION: uses RSA's 'cracked' RC4 algorithm)

Mathematics is not a crime. -- James Turpin (789479)

Mr. Turpin's signature was likely commenting on the right and ability to use 'strong encryption' to secure ones 'thoughts and posessions' at all times.

Here in America, encryption is treated like a weapon instead of a digital envelope. Added to that, 'real encryption' in its purest form is nothing more than grade-school math applied to very large numbers.

So I guess Mr. Turpin is 'asking':

Is it a crime to use math (via strong cryptography) to have privacy and security?

Just 'ask' PGP creator Phil Zimmerman about his experiences with cryptography and the United States Federal Government....

The relevant bit from:

Pure Crypto Project

which was 'cited' from:

http://diswww.mit.edu/bloom-picayune/crypto/13190

-- begin quote --
Adi Shamir once proposed the following hash function:

Let n = p*q be the product of two large primes, such that
factoring n is believed to be infeasible.

Let g be an element of maximum order in Z_n^* (i.e. an
element of order lambda(n) = lcm(p-1,q-1)).

Assume that n and g are fixed and public; p and q are secret.

Let x be an input to be hashed, interpreted as a
non-negative integer. (Of arbitrary length; this may be
considerably larger than n.)

Define hash(x) = g^x (mod n).

Then this hash function is provably collision-resistant, since
the ability to find a collision means that you have an x and
an x' such that

hash(x) = hash(x')

which implies that

x - x' = k * lambda(n)

for some k. That is a collision implies that you can find a
multiple of lambda(n). Being able to find a multiple of lambda(n)
means that you can factor n.

I would suggest this meets the specs of your query above.

Cheers,
Ron Rivest

Ronald L. Rivest
Room 324, 200 Technology Square, Cambridge MA 02139
Tel 617-253-5880, Fax 617-258-9738, Email
-- end quote --

My question is that does such a hash function live up to Shamir's and Rivest's claims? If so, such hash functions are a lot simpler to understand, use, and implement in software. Apart from the 'factoring n' bit, I can see no problems with this hash function as well but I am not a 'hardcore' mathematician like Rivest and Shamir are.

PS: Please help me decode the following:

0x0d0a (568518) 's signature line:

US War on Terror victories: an old chess champion, a student volunteer forum moderator, a US-planted mole. Proud?

old chess champion = Robert James 'Bobby' Fischer.

So who are the other two?

I cannot ask 0x0d0a by email, he/she won't give their email address out.

Bryan Taylor
iamcf13@hotpop.com
SpamByte code: 7
(see http://www.cf13.com/game-over-spammers.htm )
http://www.cf13.com/press-release.htm
All email containing unwanted content will be summarily deleted or reported as spam.

The Pure Crypto Project (based on Modular Exponentiation and RSA alone)

The source code is in Python but a savvy programmer can port it to the language of their choice. For example, I recoded the 'windowed exponentation' routine in the SDLH function in C for use in some software I wrote a while ago.

I've done lots of ad hoc research on prime numbers, primality proving, and whatnot.

I've come to the conclusion that using a symmetric cipher with a much smaller verifyable (I use the first handfull of prime numbers and one application of Fermat's Little Theorem) prime number (say 256 bits) and Diffie-Hellman as the 'key exchange' offers faster yet reasonable security over the monstrous sized 'primes' generated for RSA that's only likely gone through eight applications of the Miller-Rabin Test or so which is a probablistic test.

I wrote my own multiprecision integer package a while back and it generates 128-bit primes within 3 seconds in most cases. I've used UBASIC's ECM program to double check my work and found my resulting work to be correctly coded. The nice part about my package is that it is written in 100% C code (with help from VC++ CString) with no assembler trickery. The fun part is that my package makes it very easy (but drudgery for large tasks) to manually re-write standard C type integer computations and comparisons to the equivalent version using multiprecision intergers.

I've skimmed through other people's multiprecision code available on the Web and found them eminently verbose and somewhat confusing. I wrote mine with 'Keep It Simple, Stupid' in mind and searched the Web for the fastest, most straightforward algorithms possible to use to write it.

If you want to use crypto, and don't wan't to deal with the baggage and complexity of GPG/PGP give the handfull of code that is PCP a try. It advertises itself as:

Welcome to PCP
The Pure Crypto Project
based on Modular Exponentiation and RSA alone

It is written in PYTHON, but I was able to read it and translate one of it's routines into C for use with my multiprecision integer package.

Feel free to comment on this post. I am interested in reading what others have to say about the matters set forth in this post.

it's a simple fact that a hashing algorithm which creates a fixed-size hash will always have infinite collisions.

The second and "pure mode" will use Shamir's discrete logarithm hash function which will be used with moduli longer than 1024 bit, so that the hash values used in signatures will be that long as well.

Shamir's discrete logarithm hash function (SDLH)
The SDLH is base on a simple idea that once the message is converted into a long integer a hash of the message can be computed as follows:
hash(x) = g x (mod p*q)
given, that both p and q are large primes which are being kept secret so that factoring n = p*q is computationally infeasible.
This hash function is provably collision-resistant, I quote the prove Ronald L. Rivest presented in his posting:

Adi Shamir once proposed the following hash function:

Let n = p*q be the product of two large primes, such that
factoring n is believed to be infeasible.

Let g be an element of maximum order in Z_n^* (i.e. an
element of order lambda(n) = lcm(p-1,q-1)).

Assume that n and g are fixed and public; p and q are secret.

Let x be an input to be hashed, interpreted as a
non-negative integer. (Of arbitrary length; this may be
considerably larger than n.)

Define hash(x) = g^x (mod n).

Then this hash function is provably collision-resistant, since
the ability to find a collision means that you have an x and
an x' such that

hash(x) = hash(x')

which implies that

x - x' = k * lambda(n)

for some k. That is a collision implies that you can find a
multiple of lambda(n). Being able to find a multiple of lambda(n)
means that you can factor n.

I would suggest this meets the specs of your query above.

Cheers,
Ron Rivest

Ronald L. Rivest
Room 324, 200 Technology Square, Cambridge MA 02139
Tel 617-253-5880, Fax 617-258-9738, Email rivest@mit.edu

There are a number of issues to be addressed, especially when the SDLH is being used together with the RSA signature scheme and a full analysis of the SDLH's security can be found in the paper "A Discrete Logarithm Hash Function for RSA Signatures". The analysis shows, that SDLH can safely be used together with RSA once certain conditions are met with regard to the selection of the user's key material. For details I like to refer to the paper "A Discrete Logarithm Hash Function for RSA Signatures". about SDLH.

it's a simple fact that a hashing algorithm which creates a fixed-size hash will always have infinite collisions.

The second and "pure mode" will use Shamir's discrete logarithm hash function which will be used with moduli longer than 1024 bit, so that the hash values used in signatures will be that long as well.

Shamir's discrete logarithm hash function (SDLH)
The SDLH is base on a simple idea that once the message is converted into a long integer a hash of the message can be computed as follows:
hash(x) = g x (mod p*q)
given, that both p and q are large primes which are being kept secret so that factoring n = p*q is computationally infeasible.
This hash function is provably collision-resistant, I quote the prove Ronald L. Rivest presented in his posting:

Adi Shamir once proposed the following hash function:

Let n = p*q be the product of two large primes, such that
factoring n is believed to be infeasible.

Let g be an element of maximum order in Z_n^* (i.e. an
element of order lambda(n) = lcm(p-1,q-1)).

Assume that n and g are fixed and public; p and q are secret.

Let x be an input to be hashed, interpreted as a
non-negative integer. (Of arbitrary length; this may be
considerably larger than n.)

Define hash(x) = g^x (mod n).

Then this hash function is provably collision-resistant, since
the ability to find a collision means that you have an x and
an x' such that

hash(x) = hash(x')

which implies that

x - x' = k * lambda(n)

for some k. That is a collision implies that you can find a
multiple of lambda(n). Being able to find a multiple of lambda(n)
means that you can factor n.

I would suggest this meets the specs of your query above.

Cheers,
Ron Rivest

Ronald L. Rivest
Room 324, 200 Technology Square, Cambridge MA 02139
Tel 617-253-5880, Fax 617-258-9738, Email rivest@mit.edu

There are a number of issues to be addressed, especially when the SDLH is being used together with the RSA signature scheme and a full analysis of the SDLH's security can be found in the paper "A Discrete Logarithm Hash Function for RSA Signatures". The analysis shows, that SDLH can safely be used together with RSA once certain conditions are met with regard to the selection of the user's key material. For details I like to refer to the paper "A Discrete Logarithm Hash Function for RSA Signatures". about SDLH.

it's a simple fact that a hashing algorithm which creates a fixed-size hash will always have infinite collisions.

The second and "pure mode" will use Shamir's discrete logarithm hash function which will be used with moduli longer than 1024 bit, so that the hash values used in signatures will be that long as well.

Shamir's discrete logarithm hash function (SDLH)
The SDLH is base on a simple idea that once the message is converted into a long integer a hash of the message can be computed as follows:
hash(x) = g x (mod p*q)
given, that both p and q are large primes which are being kept secret so that factoring n = p*q is computationally infeasible.
This hash function is provably collision-resistant, I quote the prove Ronald L. Rivest presented in his posting:

Adi Shamir once proposed the following hash function:

Let n = p*q be the product of two large primes, such that
factoring n is believed to be infeasible.

Let g be an element of maximum order in Z_n^* (i.e. an
element of order lambda(n) = lcm(p-1,q-1)).

Assume that n and g are fixed and public; p and q are secret.

Let x be an input to be hashed, interpreted as a
non-negative integer. (Of arbitrary length; this may be
considerably larger than n.)

Define hash(x) = g^x (mod n).

Then this hash function is provably collision-resistant, since
the ability to find a collision means that you have an x and
an x' such that

hash(x) = hash(x')

which implies that

x - x' = k * lambda(n)

for some k. That is a collision implies that you can find a
multiple of lambda(n). Being able to find a multiple of lambda(n)
means that you can factor n.

I would suggest this meets the specs of your query above.

Cheers,
Ron Rivest

Ronald L. Rivest
Room 324, 200 Technology Square, Cambridge MA 02139
Tel 617-253-5880, Fax 617-258-9738, Email rivest@mit.edu

There are a number of issues to be addressed, especially when the SDLH is being used together with the RSA signature scheme and a full analysis of the SDLH's security can be found in the paper "A Discrete Logarithm Hash Function for RSA Signatures". The analysis shows, that SDLH can safely be used together with RSA once certain conditions are met with regard to the selection of the user's key material. For details I like to refer to the paper "A Discrete Logarithm Hash Function for RSA Signatures". about SDLH.

3) Keep up-to-date software. Remember the pgp 6.5.1 problem ? (I don't know if I have the right version, but it was something to do with not generating sufficient random numbers - although someone will probably correct me)

Not sure what you're refering to. "Recent" bugs in PGP include:

1. PGP 5.0 for Linux bug (random number generation seriously flawed. GnuPG users were not susceptible.
2. The recent OpenPGP implementation flaws in private key storage. Write-up here. GnuPG users were susceptible.
3. ADK packet in public keys not signed bug. Effects 5.5.x to 6.5.3 and allows an adversary to add an ADK to an arbitrary key. See write-up here. GnuPG users were not susceptible.

Hope this helps?

Consider the passphrase, for instance - much less entropy in a typical PGP pass phrase than in the key itself.

Or, how about advances in machine factoring a la TWINKLE.

If it's bugs you want, try the infamous ADK bug that went undetected for 3+ years, allowing third parties access to cleartext, a-la escrow.

Or the randpool bug of 1995?

I'd go on, but I'm bored of trying to pull heads out of sand.

-Isaac

Actually, ALL versions except "classic" pgp (pgp2.6.x) are vulnerable. Yes, this INCLUDES GnuPG.

The problem is with the V4 key sigs, and new keys. The "depreciated" V3 sigs & RSA keys are safe.

Plese, follow the link & read the article. It's well worth it.
The link is HERE as well for your convienience.

-Tod.