Cryptography-Digest Digest #859, Volume #8 Thu, 7 Jan 99 10:13:03 EST
Contents:
Re: Looking for pseudo-random number generators (Mok-Kong Shen)
Re: Chosen-Signature Steganography (Signatory)
Re: Birthday Attack calculations. ([EMAIL PROTECTED])
Re: What is left to invent? (Mok-Kong Shen)
Re: Looking for pseudo-random number generators (fungus)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: New Twofish Source Code Available (R. Knauer)
Re: What is left to invent? (R. Knauer)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Looking for pseudo-random number generators
Date: Thu, 07 Jan 1999 12:47:41 +0100
Mike DeTuri wrote:
>
> Basically what I want to do is create a stream cipher where the key seeds
> three to five PRNGs of different types. Then the program XORs the various
> outputs together to create a keystream which can then be XOR'd with the
> plaintext. I have read Applied Cryptography and saw this same thing
> suggested with LFSRs and implemented in A5. I was just wondering what would
> happen if someone tried the same thing with PRNGs instead of LFSRs.
In my compound PRNG the output of an arbitrary number of PRNGs is
first multiplexed and shuffled and then pairwise combined through
addition mod 1 (this is somewhat akin to XOR; the numbers are
real numbers in the range 0.0 - 0.999999). One can also choose to
combine more than two numbers through the addition mod 1 operation
with the purpose to get better security. See my Web page. If your
PRNGs deliver bit sequences (instead of real numbers as in my case),
you can do either XOR or addition mod 2^32. I personally prefer
the latter operation.
M. K. Shen
======================================================
M. K. Shen, Postfach 340238, D-80099 Muenchen, Germany (permanent)
+49 (89) 831939 (6:00 GMT)
[EMAIL PROTECTED] (subject to change)
http://www.stud.uni-muenchen.de/~mok-kong.shen/
(Last updated: 3rd January 1999. Origin site of
WEAK2-EX -- A Poorman's 56-bit Data Encryption Algorithm. (30 Dec 98)
WEAK3-EX -- A Layman's 56-bit Data Encryption Algorithm. (30 Dec 98)
WEAK4-EX -- Another Poorman's 56-bit Data Encryption Algorithm. (3 Jan
99)
Containing 2 mathematical problems with rewards totalling US$500.)
------------------------------
From: Signatory <[EMAIL PROTECTED]>
Subject: Re: Chosen-Signature Steganography
Date: Thu, 07 Jan 1999 04:14:07 -1000
Dr.Gunter Abend wrote:
>
> Signatory wrote:
> >
> > Two people share a secret 3 digit key and then they part company.
> > This key will enable them to recover 3 bits from a signature. Those
> > 3 bits form another digit in the key so 4 bits can be recovered in
> > the next signature. The 4 bits recovered form another new digit in
> > the key, so now the key is 5 digits long. This bootstrapping
> > continues until the key has 6 digits and then the private message
> > is recovered from all of the remaining signatures, with 6 bits
> > recovered from each DSA signatures.
>
> > ..... After these 4 (???) rounds are used to
> > establish the 6 digit key, there are much more than 10^6 possible
> > interpretations of the messages hidden in the signatures. There
> > are more like 10^(6+5+4) possible interpretations, as a rough
> > estimate. 10^15 is about 2^48 possible interpretations. This
> > level of uncertainty approaches a cryptographic quality level.
>
> If thousands of signed messages are transmitted routinely, you need
> two 10-bit numbers to specify
> - which message is the starting point, and
> - which bits of it should be used.
> Thus, the full set of signed messages must be tested with any one of
> 1000 keys applied to any one of, say, 1000 starting points in this
> stream of data items, until the decoding produces readable text. This
> is a rather weak cipher with a key space of only 1 million (2^20).
>
> Furthermore, if the first decoded text ends with garbage, it is highly
> feasible that this is just the start of another message, which can be
> decoded by testing only a few ten thousand possibilities (or much
> less, if the initial key is not changed).
>
> The only hope is, that the existence of a hidden message is obscured.
> However, the mechanism is rather complicated, and if it is used by
> many people, this hope would be illusory. This technique might be an
> attempt to create *deniable* cryptography, but for this purpose you
> also could simply send a lot of innocent messages which contain a few
> letters at specified positions, selected by a secret key number. This
> encoding may be done without a computer, so it is very unlikely and
> can be denied easily. Or, to avoid this kind of child�s play, use
> professional steganography.
>
> Ciao, Gunter
Thank you very much for answering this humble posting of an
idea which has been considered by other people before.
Perhaps a concrete example would be best to show how much
work would be done by a computer program before an
English plaintext would become recognizable. Here is a fake
example of a DSA signature (not verifiable):
r is 160 bits: C28D44CFB7 D8D84417FC A980F6A69C 0A05BD628E
1100001001001101010001001100111110111110
1101100011011000010001000001011111111100
1010100110000000111101101010011010011100
0000101000000101101111010110001010001110
s is 160 bits: 3283048A84 AD46DFABA4 35D64B4179 D4396CC485
0011001010000011000001001000101010000100
1010110101000110110111111010101110100100
0011010111010110010010110100000101111001
1101010000111001011011001100010010000101
If the 3 digit key is 927 the 3 bit message will be from positions
9 , 92 and 927 mod 320: so the message is 100 binary (4 decimal)
It would be easy to write a program to try all possible 3 digit
keys. There are 10*100*320 or a 320,000 combinations to check
using the protocol I described. Because of the bootstrapping for
a 6 digit key. The first 3 bit message is a random number, so it
is impossible to recognize a correct result.
The next step in this analysis is to continue the bootstrap method
to get the 4 digit key
(3 6 1 4)= (9+4 mod 10 2+4 7+4 mod 10 4).
There are 10*100*320*320 possible 4 bit random results (120 million).
Since the result is a random number, it is impossible to recognize
a correct result.
We continue the bootstrapped key generation to get the 5 digit key
(32*(10^9) calculations). And finally we get the 6 digit key that
will be used to point to the first English character of plaintext
(10^13 calculations) In the USA this is called ten trillion. This
is 2^42 calculations. This is like weak crypto so far. It gets worse.
But the analyst is not done yet. Suppose the plaintext is really
"my phone number is 1 212 783 8378". When the analyst has examined
ten trillion possible letters defined by the 6 bit positions, the
letter "m" will appear 1/64 of a trillion times, or 16 billion times.
But she can only guess that m is really the first letter. She also
needs to keep track of all 26 letters of the alphabet and their
possible keys in case m is not the right plaintext. So 416 billion
keysneed to be stored to keep track of possible first letters of
the plaintext.
Now we will consider how the analyst finds the second letter.
According to the protocol, she adds m=13 to each digit of the key,
mod 10 for 1/26 of the stored keys. She also adds a number to all
digits of the stored keys for all 25 of the other first letter
candidates. This is a total of 26*6*(416 billion) additions
(64 trillion additions) and she must store
this number of candidate keys.
The second letter in English will not come from 26 candidates, it
will be less. For the letter m, only n, a, e, i, o, u, y are
candidates for the second letter. For vowel first letters, there
can be more second letter candidates. For example, "i" can be
followed by about 22 candidates. Let's take an average of 14
second letter candidates that are meaningful.
For the 64 trillion stored keys, the analyst examines the resulting
6 bit result. This a 384 trillion operations (2^48 operations).
Since only 14/64 of the codes found are validcodes for English,
there are 14*(64 trillion) new keys to be calculated
(5.3 quadrillion additions). These keys are then stored as
possible keys. Now the word "my" has been found many times, along
with other Candidate 2 letter word fragments like , as, if, in, etc.
To get to this point, 2^51 calculations were done, and 5.3 million
gigabytes of storage are being used. As you can see, to get the
next letter of plaintext candidates will involve 6 times (2^51)
additions. Until the analyst can discard any of the candidates,
all of the disk drives in California will be full and a thousand
PCs will be busy for 8 weeks to get the third letter. The fourth
letter is even worse.
Conclusions
===========
It is possible to find a few letters of plaintext using all the
computing power in California for the protocol which was described
in the initial post. So a 6 digit key is barely secure. With this
in mind, an 8 digit key is now recommended. This increases the
work load from 2^53 additions to about 2^69 to get the first 2
letters of plaintext. I would trust my phone number to this
level of security.
When I post the 37 signatures needed to hold my mesage, the
plaintext that comes with each signature acts as a side channel
which is used to spell out the sequence of private message
fragments.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Birthday Attack calculations.
Date: Thu, 07 Jan 1999 12:28:17 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> > [EMAIL PROTECTED] wrote:
>
> > The reason for the needed precision is that I am designing a variable
> > length hash function and I want to test it for resistance to
> > collision. Since I don't have the resources to do a full test for a
> > 256 bit hash I am going to test 8, 16, 24, 32 and maybe 40 bit hashes
> > and search for trends. If the algorithm is resistant to collision in
> > the smaller sizes and there is no trend away from the "proper" value
> > then due to the nature of the algorithm I can be quite confidant that
> > the larger hashes are also resistant to collisions.
>
> [EMAIL PROTECTED] replied:
>
> > This is a very good idea. Since only if hash is any good will it
> >have the distribution predicticed by the bithday collision method.
> >However funny things do happen and though it is a very god idea
> >to check at the small lengths where more statisitics can be made.
> >You should always run tests on the final lenght your going to use
> >or you might get surprised.
>
> The whole point of testing on small hashes and extrapolating is that
> is computationally impossible to do a birthday attack on a large hash.
> For a 256 bit hash you will need to create more than 2^128 hashes
> before the odds of a collision reach 50%.
>
> Do You know how long that will take on my 486-66. Or even a planet
> full of computers for that matter. The indirect evidence is the ONLY
> indication of collision resistance.
>
> Fred Van Andel
>
>
Again you should run tests on the final length. I did not say
to run the number necessiary to get a 50% collision. It is more
than obvious you can't run that number of tests at your full
length. However it would be stupid not to run some tests in hopes
that no collision occur at long length. Since if some appear at
all then something is wrong. So if it passes the short lengths
test still are needed for finail length.
The indeirect evidence is NOT the ONLY indication you should
unless to irigant try the long case in hopes of no errors.
David Scott
P.S. Example I test scott16u very much. But I still had to
do a few tests on scott19u. And the upscaling produced a few
bugs that I would not have found and fixed if I smuggly
ignored testing all together on the longer version.
--
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://members.xoom.com/ecil/index.htm
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: What is left to invent?
Date: Thu, 07 Jan 1999 14:10:24 +0100
Darren New wrote:
>
> We already have
>
> provably-secure cryptography (OTP),
> public key cryptography based on known-hard math,
> anonymous key exchange,
> crypto requiring variable subsets of multiple keys,
> blind signatures, digital money you can make change for,
> lots and lots of other stuff.
>
> Other than user interfaces, efficiency, ubiquity, and trying to
> circumvent stupid politics, what's left to be invented?
I guess that good key management schemes would be of significant
practical value, now that key length for the common people is going
to be restricted to 56 bits.
M. K. Shen
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: Looking for pseudo-random number generators
Date: Thu, 07 Jan 1999 14:54:44 +0100
Mike DeTuri wrote:
>
> Basically what I want to do is create a stream cipher where the key seeds
> three to five PRNGs of different types. I was wondering what would
> happen if someone tried the same thing with PRNGs instead of LFSRs.
>
How will you know if the results are any good?
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 07 Jan 1999 14:14:16 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 07 Jan 1999 10:52:25 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>My point is that pseudo-OTP can be easily built, i.e. no softw
>generated,
But can it be shown that such a stream generator results in a
crypto-grade random number suitable for the OTP cryptosystem?
If it is less than totally secure, then by how much? Even the Venona
project took mountains of ciphertext to break the multiple use of
pads.
Bob Knauer
"The American Republic will endure, until politicians realize they
can bribe the people with their own money."
--Alexis de Tocqueville
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 07 Jan 1999 14:11:45 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 07 Jan 1999 11:32:31 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>I am not quite clear about your terminology point. PRNG is to TRNG
>just like pseudo-OTP is to OTP, in my humble opiniobn.
PRNG you know and TRNG means True Random Number Generator. We
discussed the concept of a TRNG a year ago and concluded that it was a
physical device capable of generating all sequences of a given finite
length with equal probability.
Note that under that definition even the sequence 111...1 is a
crypto-grade random number. The only redeeming feature is that for
sequences of any decent length, such a sequence is extremely unlikely
to be output.
We even discussed what would happen if you tried to filter such
"non-random" sequences from a TRNG - it would leak the slightest
amount of information making the OTP not totally secure.
>If a PRNG is
>very good, it approximates a TRNG.
I believe you are fundamentally wrong. A "Very Good PRNG" is not a
TRNG. They are completely different concepts. A PRNG is based on an
algorithmic procedure and a TRNG is based on a random physical
process.
>A side point, I was NOT claiming putting forward new ideas. See
>the '(Remark: ....)' in the original post. I just wanted to call
>attention to the utility of pseudo-OTP in light of the 56-bit
>export restriction.
My purposes in pointing out that this discussion took place a year ago
is to alert you to that fact in case you want to peruse the archives,
and to let you know that we came to certain conclusions which you seem
not to be aware of, at least not in the terms we stated them.
>Almost covered above. An ideal OTP is a theoretical concept, it
>does not exist in the world. (I mentioned this in the original post.)
I disagree. I believe that a TRNG can be constructed that produces a
crypto-grade random sequence. We also discussed several precautions
that must be taken in the construction of such a device. For example,
electromagnetic shielding is crucial, as any 50 or 60 cycle
alternating current noise pickup would introduce periodic patterns in
the output electronics.
>I didn't exclude mathematical constants (but to the contrary). But
>there are enomously more texts than (easily computable) mathematical
>constants to choose from.
I disagree. There are an infinity of transcendental constants to
choose from, such as ln(x), etc.
I would like to see this line of thought pursued more. Is the "digit
expansion" of a transcendental constant the same as a PRNG? For one
thing, supposedly some such expansions are not periodic. Or is that
incorrect?
>I think that what is important is how to
>obtain bit sequences that approximates OTP from all such easily
>available sources.
There is no formal way to prove that sequences generated by algorithms
are crypto-grade random numbers suitable for a totally secure OTP. At
best all you can show that a given sequence is not random for crypto
purposes.
That's why you must fall back on the concept of the TRNG, which is by
definition capable of generating crypto-grade random numbers based on
its underlying construction, e.g., random physical processes.
>That's why I recently proposed the paradigm 'security through
>inefficiency' to render brute force infeasible.
Now it's my turn to beg ignorance - I missed that. Can you restate it
in summary form.
Bob Knauer
"The American Republic will endure, until politicians realize they
can bribe the people with their own money."
--Alexis de Tocqueville
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: New Twofish Source Code Available
Date: Thu, 07 Jan 1999 14:15:17 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 07 Jan 1999 09:38:08 GMT, [EMAIL PROTECTED] (KloroX)
wrote:
>Just to know what to look for, what is the file name of the archive?
>File names should not be subjected to export restrictions.
They might be if they are greater than 40 bits in length.
Bob Knauer
"The American Republic will endure, until politicians realize they
can bribe the people with their own money."
--Alexis de Tocqueville
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: What is left to invent?
Date: Thu, 07 Jan 1999 14:23:44 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 07 Jan 1999 14:10:24 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>I guess that good key management schemes would be of significant
>practical value, now that key length for the common people is going
>to be restricted to 56 bits.
What is wrong with using a key of length greater than 56 bits that
changes each day, one that is constructed from items published world
wide such as daily closing market averages?
A few least significant bits from the DJIA, the S&P, currencies, etc,
plus the use of a hash algorithm should give you a nifty random key
for today's encryptions (or yesterday's to make sure all the numbers
have been propogated worldwide).
Bob Knauer
"The American Republic will endure, until politicians realize they
can bribe the people with their own money."
--Alexis de Tocqueville
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
