Cryptography-Digest Digest #188, Volume #14 Fri, 20 Apr 01 03:13:00 EDT
Contents:
Re: Minimal Perfect Hashing ("Scott Fluhrer")
Re: Crypto question ("Joseph Ashwood")
Re: OTP breaking strategy ("Alexis Machado")
Re: Any unbroken knapsack cryptosystem? (Frank Gerlach)
Re: Minimal Perfect Hashing (SCOTT19U.ZIP_GUY)
ERRATA: Adenauer said that (Frank Gerlach)
Churchill for (P)Russians (Frank Gerlach)
The Vatican Is Now Enligthened (Frank Gerlach)
ANOTHER REASON WHY AES IS BAD (SCOTT19U.ZIP_GUY)
NON SECRET ENCRYPTION (AKA RSA) (Frank Gerlach)
Re: Crypto question (David A Molnar)
Re: ANOTHER REASON WHY AES IS BAD (John Savard)
Re: OTP breaking strategy ("Alexis Machado")
Re: A practical idea to reinforce passwords (Paul Crowley)
Re: AES poll (Paul Crowley)
Re: Minimal Perfect Hashing (Anders Thulin)
"I do not feel secure using your program any more." (Anthony Stephen Szopa)
Re: Reusing A One Time Pad ("Alexis Machado")
----------------------------------------------------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Minimal Perfect Hashing
Date: Thu, 19 Apr 2001 17:54:32 -0700
David Formosa (aka ? the Platypus) <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Thu, 19 Apr 2001 19:47:46 GMT, Francois St-Arnaud
> <[EMAIL PROTECTED]> wrote:
>
> [...]
>
> > I'm looking for a simple C algorithm for a function y = f(x) that would
take
> > a 48-bit number x and return another 48-bit number y. f should map x to
y in
> > a one-to-one fashion. f should be one-way, or at least, it should not be
> > trivial to calculate x knowing y and the algorithm used.
>
> The Discrete Logarithm Problem can be used for this.
>
> y = a ^ x mod p
At 48 bits, the Discrete Log problem is hardly "one way"...
--
poncho
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Crypto question
Date: Thu, 19 Apr 2001 18:28:23 -0700
To be precise:
The Exact Security of Digital Signatures - How to Sign with RSA and Rabin
Bellare and Rogaway
Appears in "Advances in Cryptology - Eurocrypt 96 Proceedings", Lecture
Notes in Computer Science Vol 1070, U Maurer ed., Springer-Verlag, 1996.
The paper introduces PSS, PSS-R, and 2 other signing methods.
Joe
"Robert M Best" <[EMAIL PROTECTED]> wrote in message
news:9bnp1c$5sie$[EMAIL PROTECTED]...
> > The best advice I can give is to use OAEP for encryption
> > and PSS for signing.
>
> I did a google.com search on "PSS signing" and found:
>
> PSS = Probabilistic Signature Scheme
> PSS = Private Secure Store
> PSS = Provably Secure Signatures
> PSS = EMSR3
>
> Which one are you referring to?
>
>
------------------------------
From: "Alexis Machado" <[EMAIL PROTECTED]>
Subject: Re: OTP breaking strategy
Date: Thu, 19 Apr 2001 22:48:22 -0300
Reply-To: "Alexis Machado" <[EMAIL PROTECTED]>
"newbie" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
[snip]
> My strategy have to be improved. I know that.
> OTP is not unbreakable.
>
Hi,
Let
Y = X xor K
where
X is the plaintext
Y is the ciphertext
K is the *random* pad.
Let
1) Ai be the bit i of a text A.
2) P(Ai) be the probability of "Ai = 1".
Since K is random, P(Ki) = 1/2.
The probability of each Yi :
P(Yi) = P(Xi xor Ki)
= P(Xi) + P(Ki) - 2 * P(Xi and Ki)
= P(Xi) + P(Ki) - 2 * P(Xi) * P(Ki)
= P(Xi) + 1/2 - 2 * P(Xi) * 1/2
= P(Xi) + 1/2 - P(Xi)
= 1/2
Note that P(Yi) don't depend on P(Xi). ;-)
---
Alexis
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Re: Any unbroken knapsack cryptosystem?
Date: Fri, 20 Apr 2001 04:01:58 +0200
Rucksack systems *must* fail. Better use Non-Secret Encryption. As the term
states, the encryption will yield no confidentiality at all, But, Hey Who Cares
?
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Minimal Perfect Hashing
Date: 20 Apr 2001 02:09:08 GMT
[EMAIL PROTECTED] (Francois St-Arnaud) wrote in
<ChHD6.599615$[EMAIL PROTECTED]>:
>First, not that I am not at all versed in the math involved in
>sophisticated cryptography, so please bear with me...
>
>I have been looking at Minimal Perfect Hashing algorithms
>(http://burtleburtle.net/bob/hash/perfect.html in particular) in a
>attempt to find an algorithm that fulfills the following requirements.
>Note that MPH is probably overkill for what I need to do, but this was
>my starting point. The fact that Bob's algorithm above requires a list
>of all the keys to hash as a input is not viable for my application.
>
>I'm looking for a simple C algorithm for a function y = f(x) that would
>take a 48-bit number x and return another 48-bit number y. f should map
>x to y in a one-to-one fashion. f should be one-way, or at least, it
>should not be trivial to calculate x knowing y and the algorithm used.
>
>Any thoughts, code snips, links?
>
Actually scott16u in the mode where no random data is used for
padding would map a 48 bit number to 48 bit number. Based on
some secret key. There would be no collisions.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: ERRATA: Adenauer said that
Date: Fri, 20 Apr 2001 04:09:33 +0200
Sorry, this was of course a statement of that great Statesman named
Adenauer.
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Churchill for (P)Russians
Date: Fri, 20 Apr 2001 04:06:57 +0200
As you know, Winston once stated that you should creep into the mind of
your opponent. As a russian, the following statement is very
enlightening: "Dass die westliche Welt nun in Frieden lebt, ist eins von
Churchills unschaetzbaren Verdiensten."
Use dict.LEO.org to translate.
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: The Vatican Is Now Enligthened
Date: Fri, 20 Apr 2001 04:32:26 +0200
They are now a little more sophisticared than just saying SEX SEX SEX
:-)
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: ANOTHER REASON WHY AES IS BAD
Date: 20 Apr 2001 02:45:35 GMT
I don't think I mentioned this. This way but I feel another
reason that the AES method has lead to a poor security solution
is as follows.
If one looks at the ideas in Kolmogov Complexity thoery
where one tries to determine how random a string is by the
length of shortest "program" that can generate the string.
I think one can apply the same thoery to crypto. Since
the idea is to take a low entropy string and make it appear
to be random. It should take a fairly long program it achive
this. But the goal of AES is to make a short program that can
even be used on smartcards. I believe one measure of the
potential worth of an encrytion program is the length of the
smallest program to do the required encryption.
What this means is that after one weeds out all the weak
programs. The theroritc smallest length of code in some
abstract langauge to represent the encryption program should
be used to determine its strenth. If a long low entropy message
is encoded to a long random looking string the result can't be
very complex by the very facts used to measure the Kolmogov
complexity of the encrypted ouput string.
What this means for scott16u and scott19 is when one generates
the real key before its stored encrypted in "keyenc.key" one should
make sure its as random as possible in the Kolmogov sense. Because
it would be condsidered part of the program to do the encryption
and if that file is not compressable that you automatically have
a fairly long program. Thus a better chance of having a more
secure cipher text output since the resulting output string
should have as high a Kolmogov Complexity as possible.
I also think this means that for data which is compressable
then it must be compressed since that alone would increase the
complexity of the output sting. Since the same information is
in a smaller space. So this alone is another reasom why compression
is needed especailly if ones stuck using a cipher that can't add
much complexity to the output string due to its small size to
start with. And naturely I mean bijective compression. Such
as in Matt BICOM which uses the FULA AES cipher.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: NON SECRET ENCRYPTION (AKA RSA)
Date: Fri, 20 Apr 2001 05:30:39 +0200
see www.cesg.gov.uk
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Crypto question
Date: 20 Apr 2001 03:40:01 GMT
Joseph Ashwood <[EMAIL PROTECTED]> wrote:
> To be precise:
> The Exact Security of Digital Signatures - How to Sign with RSA and Rabin
> Bellare and Rogaway
> Appears in "Advances in Cryptology - Eurocrypt 96 Proceedings", Lecture
> Notes in Computer Science Vol 1070, U Maurer ed., Springer-Verlag, 1996.
Also online at Bellare's web page, I think. Yes, here it is:
http://www-cse.ucsd.edu/users/mihir/papers/exactsigs.html
-David
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: ANOTHER REASON WHY AES IS BAD
Date: Fri, 20 Apr 2001 04:54:30 GMT
On 20 Apr 2001 02:45:35 GMT, [EMAIL PROTECTED]
(SCOTT19U.ZIP_GUY) wrote, in part:
> If one looks at the ideas in Kolmogov Complexity thoery
>where one tries to determine how random a string is by the
>length of shortest "program" that can generate the string.
>I think one can apply the same thoery to crypto. Since
>the idea is to take a low entropy string and make it appear
>to be random. It should take a fairly long program it achive
>this. But the goal of AES is to make a short program that can
>even be used on smartcards. I believe one measure of the
>potential worth of an encrytion program is the length of the
>smallest program to do the required encryption.
Actually, from the information-theoretic point of view - and
Kolmogorov complexity has to do with information theory, not
complexity theory - the complexity of the algorithm is irrelevant if
the description of the algorithm is public.
Of course, a simple algorithm *does* reflect on the work factor, but
even if your conclusions are valid, using Kolmogorov complexity in the
argument is incorrect.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Alexis Machado" <[EMAIL PROTECTED]>
Subject: Re: OTP breaking strategy
Date: Fri, 20 Apr 2001 02:35:42 -0300
Reply-To: "Alexis Machado" <[EMAIL PROTECTED]>
"Alexis Machado" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> "newbie" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
>
> [snip]
> > My strategy have to be improved. I know that.
> > OTP is not unbreakable.
> >
>
> Hi,
>
> Let
> Y = X xor K
> where
> X is the plaintext
> Y is the ciphertext
> K is the *random* pad.
>
> Let
> 1) Ai be the bit i of a text A.
> 2) P(Ai) be the probability of "Ai = 1".
>
> Since K is random, P(Ki) = 1/2.
>
> The probability of each Yi :
>
> P(Yi) = P(Xi xor Ki)
> = P(Xi) + P(Ki) - 2 * P(Xi and Ki)
> = P(Xi) + P(Ki) - 2 * P(Xi) * P(Ki)
> = P(Xi) + 1/2 - 2 * P(Xi) * 1/2
> = P(Xi) + 1/2 - P(Xi)
> = 1/2
>
> Note that P(Yi) don't depend on P(Xi). ;-)
>
Note:
If we reuse K, the attacker may "guess" something about Ki by analyzing the
plaintexts xor. In this case, P(Ki) is not 1/2 anymore and P(Yi) equation
will depend on P(Xi).
------------------------------
Subject: Re: A practical idea to reinforce passwords
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Fri, 20 Apr 2001 05:32:11 GMT
Thomas Wu <[EMAIL PROTECTED]> writes:
> This isn't really a good idea. The problem is, you slow down
> a legitimate login by the same factor that you slow down an
> attack. It's easy to come up with slow hashes that make
> everything slower, the real innovation is with methods that
> make a brute force attack exponentially harder while having
> less of an impact on legitimate users, say a linear workfactor
> difference.
I'm surprised you say this; what he proposes is essentially key
strengthening, which under some circumstances is a good idea. Of
course, for network logons key stretching doesn't play well with
protocols such as your SRP, which is I guess why you're coming out in
favour of key stretching here. I'm not sure under what circumstances
strengthening is clearly better than stretching, but it's sometimes at
least as good.
> It's impractical in the sense that it doesn't offer any improvement
> to the existing state-of-the-art in terms of security/convenience
> tradeoffs.
Well, given that it exactly mirrors an existing proposal that's not so
surprising!
--
__ Paul Crowley
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
Subject: Re: AES poll
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Fri, 20 Apr 2001 05:32:11 GMT
[EMAIL PROTECTED] (David Wagner) writes:
> For what it's worth, the "polls" of the research community showed
> a significant leaning towards Rijndael even before it was selected
> by NIST. I, for one, think they made a fine choice, and I'm very
> pleased with the results of the standards process.
...and remember, this is one of the Twofish authors writing. In fact,
the extended Twofish team officially endorsed three of the final five
(Rijndael, Serpent, Twofish) in their final presentation. They are
the people who did the most cryptanalysis of the AES candidates.
--
__ Paul Crowley
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: Anders Thulin <[EMAIL PROTECTED]>
Subject: Re: Minimal Perfect Hashing
Date: Fri, 20 Apr 2001 06:25:37 GMT
Francois St-Arnaud wrote:
>
> I'm looking for a simple C algorithm for a function y = f(x) that would take
> a 48-bit number x and return another 48-bit number y. f should map x to y in
> a one-to-one fashion. f should be one-way, or at least, it should not be
> trivial to calculate x knowing y and the algorithm used.
Your subject says *Minimal*, but that requirement is not repeated in
the body. Is the minimality criterion important?
--
Anders Thulin [EMAIL PROTECTED] 040-661 50 63
Telia ProSoft AB, Carlsgatan 6, SE-201 20 Malm�, Sweden
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,alt.hacker
Subject: "I do not feel secure using your program any more."
Date: Thu, 19 Apr 2001 23:27:43 -0700
"I do not feel secure using your program any more."
You sure jumped to a hasty conclusion.
I certainly appreciate your effort in arriving at this noteworthy
observation.
But if you think about it this approach to generating random digits
is essentially a finite step function on a row to row basis. Thus
for a set of 3 permutations you give me I can give you another that
will produce the same random digit output. But it is finite. This
is obvious from direct observation.
Have you thought about this: You could have guessed forever if you
did not already know the random digit sequence.
So you are somewhat correct in that there are many other possible
permutations sequences that will generate the same output. But
there are practicably an infinite number of others that won't.
But let us not stop there.
As you are aware, the random digit sequences are not the OPTs. The
random digit sequences are only the starting point for generating the
OTPs.
For instance, one could suggest: "Why even generate these random
digit sequences using the OAP-L3 methods. I will just generate a
file containing nothing but the digit sequence 0123456789 repeated
until I have created a file of 18,144,000 bytes in length then I
will use the other methods from OAP-L3 to scramble these up to create
a random digit sequence."
You surely know that it won't take very many of these processes to
scramble up THIS file before the odds of guessing the final sequence
becomes practicably impossible to guess or analyze because there will
simply not be enough computing power available or time or energy to
accomplish this.
Again, using the methods of OAP-L3 to generate your random digit
sequences is just the first step of creating your OTPs. And since I
believe you would agree that even if you started with a known file
containing the sequences of 0123456789 of length 18,144,000 bytes
and this becoming very quickly practicably impossible to guess
using the methods from OAP-L3, then by actually generating the random
digit files using OAP-L3 makes this impossibility that much more
impossible.
This is because if you have gone to ciphile.com and looked up the
Sterling Approximation web page you would know that there are about
1E66,000,000 possible sequences to arrange three permutation files.
Of course there may be trillions and trillions of useable sequences.
How lucky are you at guessing one in 1E24 or 1E48 or 1E96, etc.
sequences from 1E66,000,000. Not even incredible Chinese gamblers
think they are this lucky.
Now you may feel that the problem is greatly simplified (as if
anything could simplify a problem with 1E66,000,000 possible
outcomes) if you just had some plaintext and encrypted text. How
so?
The random number sequence you determine from having these two data
sources has so little relationship with the random digit file(s)
generated from using the OAP-L3 methods as to be worthless for
attacking subsequent numbers from the OTPs because this original
random digit file has been further processed using all the methods
available with OAP-L3, where above I hope you agreed, even
if you knew this file and its sequences, it would make no
difference.
OAP-L3 is not meant to provide security for the random digit files
its methods can generate. OAP-L3 looks through this sequence of
steps to arrive at the security level obtained from using its methods
in the creation of the OTP files.
Practicably, the process leading to the final OTP files is a one way
process.
Look back from the vantage point of the OTP files, all the way back
back to the three files of permutations sequences and consider
recreating these from just some cyphertext and corresponding
plaintext.
Still a little shaky, then simply assume that someone knows (which
they cannot possibly know from figuring it out as I just pointed
out but let's just assume) that the cracker actually knows the random
digits you have generated from the methods from OAP-L3.
Continuing to process this file(s) as I am sure you realize will soon
make it impossible for this cracker to gain any headway. The
computations may be simple but their probabilities soon become
unmanageable.
14! = about 87,000,000,000. So a cracker guessing will have to guess
this many possible outcomes for just this one process assuming the
cracker even knows this was the process run. Set's assume the
cracker does.
Just running this process 10 times makes the possible outcomes
(87E9)^10 = 87E90. How can a hacker increasingly keep track of all
this? This is why OAP-L3 is so powerful. It allows the user to
effectively determine the security level by how many processes run.
Here is a real problem for the cracker. Let's say a cracker does
guess a short length of the random number sequence or OTP used to
encrypt a message or messages. Is this any different than guessing
the sequence of any other encryption software or any other encryption
method? Your premise is "by guessing." If a guess is made and is
good then does this necessarily imply subsequent guesses are correct
as well.
You suggest that if a cracker guesses the three permutation sequences
that they will be able to break the encryption. How? Or more
specifically how will the cracker even know that the original or
useable three permutation sequences are valid?
The cracker has nothing to verify this with. ABSOLUTELY NOTHING.
The nature of OAP-L3 and many other encryption schemes is that even
if you guess and obtain a readable plaintext message you need to ask
yourself if this is the correct plaintext message.
You can essentially see this entire argument by reading the Help
Files at ciphile.com.
Thanks for allowing me to refresh my memory.
I hope this helps in your considered deliberations.
AS
PS I assume you were using OAP-L3 according to instructions and
recommendations.
------------------------------
From: "Alexis Machado" <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Fri, 20 Apr 2001 03:49:50 -0300
Reply-To: "Alexis Machado" <[EMAIL PROTECTED]>
"Mark G Wolf" <[EMAIL PROTECTED]> wrote in message
news:9bl4od$5qgq$[EMAIL PROTECTED]...
> > Let K be a bitstring of length n, which is the key. This is securely
> > exchanged between both parties (Alice and Bob of course). To encipher a
> > message M of length p, where p <= n, randomly selected bits of K are
> > used to encipher message M by
> > for i = 1 to p
> > c_i = m_i ^ k_rand[i]
> >
> > ^ means exclusive-or
> > and the ciphertext is C.
> >
> > I don't see how Bob can decrypt the message without knowing the which
> > key bits Alice used to encipher the message.
> >
> > If this "random selection" is based on a function, then it is not
> > random, and we can analysis this unspecified function for weaknesses.
>
>
> Let's just call it the secret sauce.
>
Before patenting CryptoSauce, be sure you are not using Dynamic
Substitution.
---
Alexis
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
