Cryptography-Digest Digest #184, Volume #14 Thu, 19 Apr 01 17:13:01 EDT
Contents:
Minimal Perfect Hashing ("Francois St-Arnaud")
Re: Reusing A One Time Pad ("M.S. Bob")
Re: DL blind signature (Ian Goldberg)
Required Reading For Junior Intelligence Officers (Frank Gerlach)
Re: "UNCOBER" = Universal Code Breaker (newbie)
Re: OTP breaking strategy (Mok-Kong Shen)
Re: Basic AES question (Frank Gerlach)
Re: "UNCOBER" = Universal Code Breaker ("Tom St Denis")
Re: OTP breaking strategy ("Joseph Ashwood")
Re: OTP breaking strategy ("Joseph Ashwood")
Re: I took the $5000 Goldman Challenge ("Tom Gutman")
Re: OTP breaking strategy ([EMAIL PROTECTED])
Re: A practical idea to reinforce passwords (Niklas Frykholm)
Re: newbie: cryptanalysis of pseudo-random OTP? ("M.S. Bob")
----------------------------------------------------------------------------
Reply-To: "Francois St-Arnaud" <[EMAIL PROTECTED]>
From: "Francois St-Arnaud" <[EMAIL PROTECTED]>
Subject: Minimal Perfect Hashing
Date: Thu, 19 Apr 2001 19:47:46 GMT
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?
Regards,
Francois :)
------------------------------
From: "M.S. Bob" <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Thu, 19 Apr 2001 20:46:41 +0100
Mark G Wolf wrote:
>
> Thanks for the history lesson but my real "question" or curiosity was the
> word origins. As best as I can tell "snake oil" came from "snake" for
> someone wicked and deceitful, and "oil" from the fact that many "real" cures
> of the time relied on varies natural oils and balms, like eucalyptus or
> evergreen oil.
Douglas has already answered your question. It comes from the peddling
of snake oil elixirs.
Just as the reference to "kid sister" is not Freudian at all, but a
crypto-slang for security against only the mythical "12 year old kid
sister". Example: monoalphabetic substitution is good only against your
kid sister.
It does not apply if your kid sister works for the NSA or GCHQ.
For other sci.crypt readers interest:
<http://groups.google.com/groups?q=mark.wolf%40prodigy.net&btnG=Search&meta=site%3Dgroups>
------------------------------
From: [EMAIL PROTECTED] (Ian Goldberg)
Subject: Re: DL blind signature
Date: 19 Apr 2001 19:54:48 GMT
[Note: I don't have the particular paper in front of me, so I'm basing
these answers on what usually happens with DL protocols in the subgroup
construction.]
In article <9bnb1s$27$[EMAIL PROTECTED]>,
Cristiano <[EMAIL PROTECTED]> wrote:
>In many systems (or perhaps in all) for the blind signature based on DL, one
>must choose a prime q that divides p-1 (also p is prime) and then a
>generator in the moltiplicative group Zq* (cfr Chaum-Pedersen from paper
>"Loyalty Program Scheme
>for Anonymous Payment Systems" by Arrianto Mukti Wibowo and Kwok Yan Lam).
Careful; g isn't supposed to be a generator for Zq*. g is supposed to
be a generator for the subgroup of Zp* which is of order q.
>Doing some trials with small numbers, when I compute the public key y=g^a
>mod p (a is my private key) for all a<p, the distribution of y may be very
>bad; on the contrary, if I compute y=g^a mod q for all a<q, the distribution
>is as expected: I get all the elements in Zq* (g is a generator!).
>Why this "strange" set up?
I think your g may be incorrect. The easiest way to choose g is:
o Let h be a random element of Zp*.
o Let g = h^((p-1)/q) mod p.
o Try again if g=1.
Clearly, g^q mod p = h^(p-1) mod p = 1, so g has order dividing q.
If g is not 1, then since q is prime, g has order exactly q, so g
generates the subgroup of order q of Zp*.
Then if you calculate y=g^a for all a<q, you'll get all of the elements
of that subgroup.
>My implementation of the algorithm in the above paper at page 13
>(Chaum-Pedersen blind signature) doesn't work. The modulo for all the
>calculations is not shown. Is it always mod p or mod q?
If you're calculating with group elements, it's mod p. If you're
calculating with exponents, it's mod q.
>A last question. At step 3 there is: choose u in Zq* and v in Zq. q is
>prime, what is the difference?
Zq* does not include 0.
- Ian
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Required Reading For Junior Intelligence Officers
Date: Thu, 19 Apr 2001 21:42:23 +0200
http://geocities.com/fgerlach.geo/buecher.txt
------------------------------
From: newbie <[EMAIL PROTECTED]>
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Thu, 19 Apr 2001 15:51:25 -0300
I use extra-information to select wich message I have to choose.
Suppose for every ciphertext concerning banking I can select in my 2^n
possible messages those related to banking.
My messages are equiprobable in absolute words.
Some messages are specific to banking.
Do you understand this?
Some messages can not be in certains positions.
Do you understand this?
You can not find "the" or "of" just as sample in the end of a sentence.
The first letter could be a, b, c, d, etc.....
But you can eliminate some letter no matter what is the random the
random key that the sender used.
When I cumulate sufficient possibles messages given the context I can
eliminate those with not truly random output.
And so on.
In every plain-text you will find some words or sentences that give to
the text its sense ( the keywords).
By using a progressive selection with two criterias : context and
syntax. You will eliminate a lot of messages.
And you can eliminate some output using statistical tests to select only
more truly random string, eliminating those not sufficiently random.
This test apply to large bit-string.
Joseph Ashwood wrote:
>
> You don't seem to fully understand this. There is a set of possible
> messages, each with it's own real probability. While the attacker can
> discard all messages that are not among that set, the attacker CANNOT
> determine which of that set the encrypted values maps to. That cannot is a
> mathematical statement, you cannot violate it. If you would like to try, I
> will even give you a better position than necessary, I'll give you a small
> PGP encrypted file, all you have to do is tell me what I said. To make it
> even more fair it begins with :
> The secret phrase is :
> the next part is a misquoting of a famous line followed by a simple
> statement. Both the secret phrase and the statement are from latin, one if
> the bad misquoting of Julius Ceaser, the second an actual quote. Because
> it's so small, I've attached it. I fell this is a fair system, after all
> there exists a OTP that translates it to what it was originally, so this can
> be no stronger than a OTP, and it is known to be much weaker. In case you're
> tempted to try to brute force the passphrase, don't bother it's got more
> entropy than could be used.
>
> Since I already know you won't be able to find the OTP to map the test
> encryption to the complete real text, I will take this opportunity to
> declare victory. Of course if you succeed there's always the fact that it's
> not even a full OTP. I suppose in fairness I should tell you exactly how
> many characters were in the original (since PGP does some compress and
> expansion), 63 bytes, all standard readable ASCII (except the <enter> and
> <space>).
> Joe
>
> "newbie" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > All the messages does not all have the same probability to be valid
> > given the context
> >
> > If you have as output any word out of context you can eliminate it.
> > You may decrypt it little by little.
> > You can eliminate 95% of the messages.
> > The goal is not to recover the key.
> > You have just to compute the probability that the output is random and
> > if it satisfies Maurer conditions or other statistical tests.
> >
> > If the message is 100101010
> > and the ouput 1111111111
> > you are quite sure to reject the "possible" key.
> >
> >
> > Tom St Denis wrote:
> > >
> > > "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
> > > news:[EMAIL PROTECTED]...
> > > > Tom St Denis wrote:
> > > > > An OTP is not possible to break since all messages are equally
> > > > > probable.
> > > >
> > > > No! No wonder the newbie is so confused.
> > >
> > > What? All solutions are equal probable since all keys are equal
> probable.
> > > That's why the OTP is secure.
> > >
> > > Tom
>
> Name: Text.txt.pgp
> Text.txt.pgp Type: unspecified type (application/octet-stream)
> Encoding: x-uuencode
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: OTP breaking strategy
Date: Thu, 19 Apr 2001 21:56:21 +0200
newbie wrote:
>
> Yuo have yet a plagiat's Nobel Prize. Did you read the article about
> Ideal homophonic system?
Take a mirror and look into it. I wrote an article with
a content that is o.k. Nobody of the group has commented
on that article at that time and evem if it turns out to
duplicate someone else's stuff (I have not yet checked
that fully, becase one paper is not yet available to me),
it does not contain anything wrong.
What do you do? You ignore other's hints to look into
literatures where it is explained that OTP cannot be
broken and stubbornly continue to claim the opposite. It
certainly could not be excluded from the beginning that
you might find something revolutionary. But you have at
least first to read and study the existing literature and
show that what is wrong there before putting up your
claim that OTP could be broken. Just ignoring these
existing knowldeges and nevertheless putting up your
claims is wasting the bandwidth of this group. How many
people have already patiently and gently give you the
advice to read a bit the existing stuffs (one person
even gives literature pointers in French) and learn a
mininum from that, at least some common terminology
to facilitate discussions, before continuing to post in
your style?
M. K. Shen
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Re: Basic AES question
Date: Thu, 19 Apr 2001 21:50:34 +0200
Lou Grinzo wrote:
> I'm just starting to learn about AES, and I was wondering:
> Why does the AES standard support only the key sizes of
> (I think) 128, 192, and 256 bits? Is it purely to keep
These are the magic numbers as defined by the Pope. Remember, the
algorithm was invented by a catholic university.
>
> the specification and logistical issues simple? Or is there
> a technical reason, such as increasing the key size doesn't
> make AES any more difficult to attack? (I know that last
> one sounds goofy, but in a world where PKI works, almost
> anything is possible. <g>)
>
> Lou
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Thu, 19 Apr 2001 20:02:36 GMT
"newbie" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I use extra-information to select wich message I have to choose.
>
> Suppose for every ciphertext concerning banking I can select in my 2^n
> possible messages those related to banking.
> My messages are equiprobable in absolute words.
> Some messages are specific to banking.
> Do you understand this?
> Some messages can not be in certains positions.
> Do you understand this?
> You can not find "the" or "of" just as sample in the end of a sentence.
> The first letter could be a, b, c, d, etc.....
> But you can eliminate some letter no matter what is the random the
> random key that the sender used.
> When I cumulate sufficient possibles messages given the context I can
> eliminate those with not truly random output.
> And so on.
> In every plain-text you will find some words or sentences that give to
> the text its sense ( the keywords).
> By using a progressive selection with two criterias : context and
> syntax. You will eliminate a lot of messages.
> And you can eliminate some output using statistical tests to select only
> more truly random string, eliminating those not sufficiently random.
> This test apply to large bit-string.
So you are using english to filter out invalid possible keys. WHOOPY.
Do you realize that all english sentences will be valid plaintexts provided
they are of the right length? What about *that* don't you get?
Tom
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: OTP breaking strategy
Date: Thu, 19 Apr 2001 12:33:35 -0700
"newbie" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> And every output is not necessarly (100 %) truly random.
Completely and totally WRONG!!!!!!!!!! There is a fundamental proof of the
output of XOR having at least the entropy of the maximum of the entropy of
it's inputs. Since one of the inputs to a OTP is purely entropic the output
of the XOR is purely entropic, or as you said 100% random.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: OTP breaking strategy
Date: Thu, 19 Apr 2001 12:38:49 -0700
"newbie" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> When you introduce the context factor all the messages are not
> equiprobable.
That is correct, although your reasoning from it is completely useless. The
result is that you have a set of possible decryptions of which you know that
the ones with "Dear" at the beginning are vastly more likely than ";ariu"
however I have sent myself e-mails and other encrypts messages that begin
with things that look very much like "el.Ifh;i.WSU;AIEb;AShvi;Avha:eiv"
although I can't be entirely sure, which I placed a semi-random length on.
> That is the way to try to find out the input.
No that is a way to find that you know nothing about the inputs except the
probabilities you knew before. I suggest you try my challenge, I think it
would be enlightening for you. I gave you more information than you'll know
about any other challenge, and is is provably no stronger than a OTP of the
same data, and that such a OTP exists, go ahead, have a go at it.
> If I analyse any output of 128 bits I will obtain 2^128 messages. I know
> that.
> But all the messages are not 100% in the context.
> And all the output are not 100% random.
> I have two ways to select : context factor and degree of randomness.
Doesn't matter, if you don't know the entire message then there is some
entropy that is unknown to you, you will not be able to remove that entropy
to find the original message, all you'll have is a guess based on the odds
of each message.
Joe
------------------------------
From: "Tom Gutman" <[EMAIL PROTECTED]>
Crossposted-To: comp.compression
Subject: Re: I took the $5000 Goldman Challenge
Date: Thu, 19 Apr 2001 13:10:40 -0700
Reply-To: "Tom Gutman" <[EMAIL PROTECTED]>
"Dror Baron" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Wed, 18 Apr 2001, Tom Gutman wrote:
>
> > > > Geometry he would get lost. Its hard to mix the two
geometres so
> > > > I try to be of the type uses which ever one fits the
problem.
> > > > One has to be flexable.
> > >
> > > Dude, I rest my case. That's like cheating whichever
> > > way works best for any given problem.
> > >
> > That's kind of weird! So you think it's like cheating for me to
> > decide whether I should use a hammer or a screwdriver after
> > examining the fastener?
>
> He isn't only changing his tools. He is changing his
> problem-definitions. Every time he adapts the rules,
> the operating system, the way he determines the length,
> every time he uses the most convenient set of rules.
>
Could you supply a more specific example? As far as I can tell, he
consistenly works with the concept of a file as a finite sequence of
bytes. He doesn't care how the sequence is delimited (a passed
length, a return code, an extension character) or how it is
externally stored.
--
Tom Gutman
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: OTP breaking strategy
Date: Thu, 19 Apr 2001 20:10:09 GMT
newbie <[EMAIL PROTECTED]> wrote:
: When you introduce the context factor all the messages are not
: equiprobable.
: That is the way to try to find out the input.
: If I analyse any output of 128 bits I will obtain 2^128 messages. I know
: that.
: But all the messages are not 100% in the context.
: And all the output are not 100% random.
: I have two ways to select : context factor and degree of randomness.
Okay, remember that you don't have access to the pad itself. Now, suppose I
have two different pads and I encrypt the following two messages:
SELL 750 SHARES
BUY 1000 SHARES
Since I am not reusing the OTP, I encode each message with a different
pad. By some bizarre coincidence, the pads happen to encrypt their
messages to exactly the same result: 5e8f128c65a30954371a7e494217ad
Now, given that the two messages are reasonably within the same context here,
how can you possibly tell which one I actually sent?
You might be able to guess which one I sent by analyzing my business and maybe
by planting spies in my office, but at that point, you haven't really broken
the OTP. In fact, you might figure out that I need to send the "BUY 1000 SHARES"
message, but because I made a mistake, I sent the "SELL 750 SHARES" message.
--
Mark Wutka
------------------------------
From: [EMAIL PROTECTED] (Niklas Frykholm)
Subject: Re: A practical idea to reinforce passwords
Date: Thu, 19 Apr 2001 07:53:20 +0000 (UTC)
In article <[EMAIL PROTECTED]>, Harald
Korneliussen wrote:
>My idea is that upon selecting a password, X bits of
>random data is added to the password. You are not
>informed of what these bits are, nor does the computer
>store them. The computer only stores how many bits
>there are, and brute-forces them every time you enter
>you password.
Yes, this is a good idea, we want to slow down the attacker
as much as possible. And if we can slow down the attacker
1000 times (which is easy to do without putting much strain
on your computer), it _does_ make a difference.
Methods similar to this one are employed in many encryption
system (see for example PKCS #5, that Jakob referred to),
however the slowdown is typically not done in this way.
Instead, a slow key derivation function (KDF) is used to
transform the password to a key
K = KDF(PW)
Usually, some parameter to the KDF controls the number of
iterations (the ammount of slowdown).
This gives a constant slowdown (rather than a random one,
which we get with your method), which might be preferrable.
However, I think the main reason that this method is
preferred is that we do not have to worry about related key
attacks.
With your method we want to compute H(PW || R_i) for all
possible R_i and compare it to a stored hash value. It is
possible that there are some weaknesses in the hash function
that allow us to do this faster than by trying all possible
R_i.
For strong hash functions, such as SHA, no such weaknesses
are known, AFAIK, and your method would work just as well.
However, to be on the safe side, it might be better to use a
KDF.
// Niklas
------------------------------
From: "M.S. Bob" <[EMAIL PROTECTED]>
Subject: Re: newbie: cryptanalysis of pseudo-random OTP?
Date: Thu, 19 Apr 2001 21:27:55 +0100
Osugi Sakae wrote:
>
> forgive me for what is prolly a newbie question, but ...
>
> I understand that a properly impliemented and used OTP is secure, and I
> understand that a simple polyalphabetic substitution with a keyword is
> not secure, and in fact almost (totally?) worthless if computers are used to
> attack it. Several of the intro to crypto books discuss this, right upto
> keywords as long as the plaintext. (Forget whose, but one book mentioned
> using a Carl Sagan book as the "keyword"). What they don't say is why
> this is not secure, just that the language of the keyword rubs off on the
> ciphertext. I can understand this, supposing that more of the plaintext
> will get enciphered with the letter 'e' than with the letter 'q'. But how
> would someone go about cryptoanalyzing this? The kappa test would tell
> them that it is a polyalphabetic cipher, but what next? None of the books
> I have read (and understood) goes into this.
Cryptanalysis by Helen Fouche Gaines (Dover Books less than $10 new)
It covers most "classic" (pre-computer) ciphers, and requires no higher
math knowledge.
Also read about the American Cryptogram Association
<http://www.und.nodak.edu/org/crypto/crypto/>
You determine the length of the key(word) by the Kasiski test or index
of coincidence. Then you solve it simply as x number of different
monoalphabetic substitutions ciphers using frequency analysis.
> The books also mention that a OTP is only as secure as the random number,
> but again don't mention how someone would break a pseudo-random cipher.
> Is it something to do with probabilities of subsequent numbers (for
> example, noticing that say 5 tends to follow 8 more often than 10% of the
> time? (assuming a cipher that displays as numbers 0-9))
8.10. Can I use pseudo-random or chaotic numbers as a key stream?
Chaotic equations and fractals produce an apparent randomness from
relatively compact generators. Perhaps the simplest example is a
linear congruential sequence, one of the most popular types of random
number generators, where there is no obvious dependence between seeds
and outputs. Unfortunately the graph of any such sequence will, in a
high enough dimension, show up as a regular lattice. Mathematically
this lattice corresponds to structure which is notoriously easy for
cryptanalysts to exploit. More complicated generators have more
complicated structure, which is why they make interesting pictures---
but a cryptographically strong sequence will have no computable
structure at all.
See [KNU81], exercise 3.5-7; [REE77]; and [BOY89].
from the sci.crypt FAQ <http://www.faqs.org/faqs/cryptography-faq/>
> Also, OTP's are hard to impliment, because of the amount of data and the
> need for secure exchange and storage. And they work best with a limited
> number of people.
>
> So, thinking about these long keywords, OTP, and pseudo-random stuff,
> I had an idea that I think i understand. (I am not suggesting this as a real
> system, I understand that I am not qualified to declare any system secure
> (of course, if I can break it, it is most likely very insecure). This is
> just a thought exercise).
>
> 1. Take any previously agreed upon text - one from project gutenberg
> would be good.
Book cipher, read about them in Kahn.
> 2. Just xor'ing with the text would not be secure, nor I gather would
> doing some sort of transformation add all that much security.
Book cipher with a unspecific twist. A bit more work, but not really a
big deal.
> 3. So, tally the letters' frequencies. Choose the two letters that
> account for the closest percentage of the text (4.021% and
> 4.074% for example).
You lose me from here to the end.
> 4. Keep those two and get rid of the others. If it helps security, do
> some simple transformation on the letters, either on the full text or on
> the modified text consisting of only two letters.
>
> 5. Convert the two letters to 1 and 0. You now have a large number of
> ones and zeros that can be used as binary input for xor'ing with the
> cleartext. (8 digits from the pseudo-random file for each ascii character
> in the plaintext).
>
> How secure would it be? How random would the resulting pseudo-
> random file be? How does one test this? How would one go
> about attacking it? Would it be easiest just to keep a database of
> stats for project gutenberg files?
It is fairly classical in design, I suspect it would put off casual
amateurs, perhaps delay more advanced, but ultimately would fall to
prying analysis.
> It is a long key but has lost most of the linguistic traits that would
> give it away, right? Aside from probable weak keys, would the fact that
> such a pseudo-random number is not mathematically generated be an
> advantage?
Not necessarily. A poor but long key x-or'ed does little to conceal the
message.
> I guess what it comes down to is, would anyone like to comment on the
> above and / or recommend some more advanced books or web sites dealing
> with cryptanalysis of pseudo-random OTP? Or for that matter a good book
> to help me get up to speed on the maths involved?
>
> I've read:
> The Code Breakers by Kahn (of course)
> Cryptology by Beutelspacher
> one or two other introductory books that I cannot recall at the moment
> Decrypted Secrets by Bauer
> Applied Cryptography by Schneier
>
> Some parts of Schneier's book were hard to follow, but the math in
> Bauer's book lost me. The others I think I understood properly.
Decrypted Secrets and Applied Cryptography are good books.
Many newcomers find they need to refresh or learn some additional
mathematics to understand more about cryptography. An idea of your
mathematical knowledge might help suggest some possible books at a level
you can understand.
> yoroshiku (japanese for "please be nice to me")
You appear to be making an effort to read, listen and learn. So I will
gladly be nice to anyone who wants to learn more.
------------------------------
** 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
******************************
