Cryptography-Digest Digest #963, Volume #8 Mon, 25 Jan 99 20:13:02 EST
Contents:
Re: Random numbers from a sound card? (Paul Rubin)
Re: Metaphysics Of Randomness (Patrick Juola)
Re: The Performance of Meet-in-the-Middle ([EMAIL PROTECTED])
Re: Metaphysics Of Randomness (Patrick Juola)
Re: Random numbers from a sound card? (Nathan Kennedy)
Re: Random numbers from a sound card? (R. Knauer)
Would the gentleman with Mondex knowledge in the USA please contact me again.
("Simon Copsey")
Re: S-box cycles (Anthony)
Re: [req]:Cryptanalysis tool - word pattern table (©ú¥Õ)
Unicity, DES Unicity and Open-Keys ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Random numbers from a sound card?
Date: Mon, 25 Jan 1999 21:21:09 GMT
In article <[EMAIL PROTECTED]>,
David Ross <[EMAIL PROTECTED]> wrote:
> Has anyone had success using a sound card (like a Sound Blaster) to
>generate streams of random numbers?
Yes, see http://www.lila.com/nautilus/index.html and download the
source from one of the sites mentioned there.
> What sort of audio source would you suspect would be the best to use
>in generating random numbers?
We ask the user to blow into the microphone to make noise, IIRC.
> How would you test the 'quality' of the generated random number
>stream?
We just test the total amount of energy in the audio to make sure
the mic isn't dead. We expect that the raw audio will have lots
of correlation, so we run it through a hash function or block cipher;
I don't remember the details.
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Metaphysics Of Randomness
Date: 25 Jan 1999 09:07:36 -0500
In article <[EMAIL PROTECTED]>,
>> What is the actual likelihood of a readable text string
>> being output from an OTP? Most of the encrypted files
>> I've looked at contained very few readable strings of
>> even two characters. I would think that a readable
>> string output would be more likely to be the result of
>> an accidental transmission of plaintext or a zero key
>> than it would be the result of a readable string
>> encrypting to another readable string.
>
>To answer this precisely you need to provide a definition of "a readable
>text string". In terms of letters and spaces in ASCII the odds would be
>(65/265)^N where N is the length of the string of text. Of course this
>formula treats upper and lower case as similar so it includes WiErD
>STRingS liKE thiS One.
>
>> >(n.b. -- if the message I receive reads "attacd at
>> nown", and you use
>> >a stronger filter of never allowing six successive
>> zeros, then I can
>> >still unbutton your message. The reason being the pad
>> necessary to
>> >produce "attack at noon" would be an illegal pad --
>> and hence you're
>> >still attacking at dawn).
>>
>> Is this an indication of a "fatal flaw" in the OTP?
>> From what I've read in this newsgroup, it appears that
>> much of an analyst's work is discovering how plaintext
>> is leaked into the ciphertext. With the OTP, any byte
>> of zero in the key leaks a plaintext character, and
>> that would seem to make analysis possible. Or, as
>> described here, maybe easy. On the other hand, if I
>> knew that the only two possible messages were "attack
>> at noon" and "attack at dawn", I wouldn't bother
>> worrying about which the message specified. I'd already
>> know enough to prepare for an attack.
This isn't an indication of a fatal flaw in the OTP. The reason is,
bluntly, that the amount of "leakage" produced by a zero character
in the bad -- or even a zero bit in the pad -- is *exactly* balanced
by the amount of "false leakage" where something it put into the
pad. So if you see an 'E' in the cyphertext, you have no way of knowing
whether or not this is a leaked 'E' or a spurious 'E' created by
something else XORing to E.
And, in fact, if this "leakage" *weren't* there, then you would KNOW
every time you saw an 'E' that the plaintext letter COULDN'T be an 'E',
which would be a significant weakness..
>> >>
>> >>> As to whether or not the loss of entropy is
>> significant to make a
>> >>> practical difference -- that depends on the degree
>> of filtering.
>> >>> What you do really buy by doing the filtering? Not
>> much --- and
>> >>> every time the filter triggers introduces a
>> weakness.
>> >>
>> >>Among other things, a crypto system needs to inhibit
>> the identity operation on
>> >>plaintext. I.e., the idea of a crypto system that
>> includes the possibility that
>> >>ciphertext == plaintext has a flaw. Mathematically,
>> the system including the
>> >>possibility is infinitesimally "stronger" due to the
>> larger search space, but
>> >>that's not the unit of measure for crypto strength.
>>
>> See what I mean? Both paragraphs above make sense and
>> sound right. There are (simplistically) only four
>> possibilities:
>> The first is wrong and the second is right.
>> The first is right and the second is wrong.
>> Both are right.
>> Both are wrong.
>> However, if both are right, then both are also wrong,
>> if they actually contradict each other.
>>
>> Maybe they don't contradict each other and both are
>> right.
>
>I think the latter is true. The discussion above involves two
>conclusions: 1. any filtration reduces strength by some amount; and 2.
>Filtering out pathological patterns is not harmful to the security of
>an OTP.
Unfortunately, no. I gave the example earlier where a filtered OTP didn't
produce any security. More generally, if c is the (received) cyphertext,
and p is a potential plaintext, but p^c is KNOWN to be something that
would be filtered, then you can exclude p as being a potential plaintext.
This contradicts the requirements of perfect security.
>> I mean, theoretically, a TRNG could start up generating
>> a 2^1000 bit sequence of zeros, and that be a
>> legitimate output. I don't think that would be very
>> useful.
But the odds of this happening are, literally, one in 2^1000 if
the generator works. So for every time this happens, you'd get
millions or billions of false English-appearing cyphertext messages.
So a cryptographer would be misled millions of times more often if
he treated an English cyphertext message at face value.
>> My use or lack
>> of it has no effect on the output. Every bit will
>> continue to be generated completely independently of
>> every preceding bit. Does my lack of use of output
>> (between messages) constitute an unintentional form of
>> filtering?
>
>In theory yes. An attacker knowing your intention to avoid using "bad"
>patterns does not have to consider those keys. Thus his job is easier.
>However, the amount of reduction in the work he has to do is
>infinitesimal.
Absolutely. Intelligent filtering will not introduce other than
a purely theoretical and highly improbable break. A statistician
friend of mine likes to talk about "clinical significance" -- this
is a classic example of something with no clinical significance.
On the other hand, if you're going to be playing around with the OTP
*because of its perfect secrecy properties*, there's no room for
judgements about "clinical significance."
-kitten
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: The Performance of Meet-in-the-Middle
Date: Mon, 25 Jan 1999 20:59:50 GMT
In article <78gkfo$3si$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David Wagner) wrote:
>
> I don't think I believe the argument.
^^^^^^^^^^^^
Which argument? I think I am making 2 distinct points:
I. It is tempting to conclude from the standard descriptions of the
meet-in-the-middle (MITM) attack, that it always has time complexity
strictly bounded by O(2^(k+1)), regardless of how the plaintexts or
the ciphers are modeled. But that is not true in a variety of
different circumstances.
II. It is *very* tempting to conclude that MITM is always better than
exhaustive search O(2^(2k)), regardless of the *specific* choice of
cipher or plaintexts. I give a counterexample to that conclusion as
well.
In your attempt to dispute the latter you seem to confirm the former.
So, I will not attempt to defend (I) in this follow-up. In either
case, I stand by both points.
As far as (II) goes, a counterexample should be judged by its ability to
surprise, or even amuse. Any good counterexample is an instance of an
object or paradigm which occurs with relatively low frequency among some
collection. Otherwise, where is the surprise? My counterexample assumes a
fixed set of plaintext-ciphertext pairs, and a fixed cipher in the Shannon
model (that is, only the keyspace is a probability space). I don't treat
an ensemble of plaintexts, or an ensemble of ciphers, but apparently
neither do HAC or AC.
By averaging over all plaintexts and over all random ciphers, it is not
surprising that the extremely bad performance of the counterexample gets
washed away in the noise. The merit of a counterexample should
not be judged by the generality with which it applies. Ignoring the
fact that there are an uncountable infinity of such counterexamples,
I will always be forced to concede that these occur with relatively low
probability among an ensemble of all ciphers, over all groups, and
all numbers of plaintext-ciphertext pairs, averaged over all natural
languages, etc. I will lose *that* game every time!
> Therefore, we may conclude that a MITM attack (even in pathological
> cases) takes at most O(k * 2^k) time, which is only slightly worse than
> the O(2^k) workfactor expected for a random cipher.
You seem to be summarily dismissing the proof of the statement II. To do
that, you really must either work within the context of its premises or
find a flaw in its logic. I stand by the proof, and confess that at
least I was surprised by the existence of any such counterexample to the
general claim the MITM is always better than exhaustive search.
John Pliam
[EMAIL PROTECTED]
http://www.ima.umn.edu/~pliam
refs:
[1] John Pliam, Ciphers and their Products: Group Theory in Private Key
Cryptography, PhD in preparation, 1999.
URL: http://www.ima.umn.edu/~pliam/doc
[2] ___, section 6.5 of [3], "About the MITM Attack".
URL: http://www.ima.umn.edu/~pliam/doc/mitm.ps.Z
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Metaphysics Of Randomness
Date: 25 Jan 1999 13:16:58 -0500
In article <1999Jan25.095341.1@eisner>, <[EMAIL PROTECTED]> wrote:
>In article <78a72r$pth$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Patrick Juola)
>writes:
>> In article <1999Jan22.102105.1@eisner>, <[EMAIL PROTECTED]> wrote:
>>>Organization: DECUServe
>>>Lines: 39
>>>
>>>In article <[EMAIL PROTECTED]>, Darren New <[EMAIL PROTECTED]>
>writes:
>>>> You're kind of mixing up the mathematics of what things are with
>>>> possible implementations of what things are. For example, one possible
>>>> definition for an NDTM is one in which it always choses the state
>>>> transistion that is going to make it halt, if any will.
>>>
>>>No. That's an NDTM plus an oracle. In an NDTM, the set of available
>>>transitions is purely a function of current state and current tape
>>>symbol. You don't get to disallow certain transitions based on tape
>>>content not currently under the read/write head.
>>
>> No, that's an NDTM. Check out any of the basic texts; I recommend
>> Hopcroft and Ullman.
>>
>> The best (informal) definition I've seen for an NDTM is that it's
>> a lucky computer -- it has choke points where it can go in several
>> different guesses and it always guesses right. This is *NOT* simply
>> a DTM plus a random number generator unless you can guarantee that
>> the RNG will always "guess right"
>
>Ahhh. I see the formal definition that this informal definition tries
>to capture. For a machine that can halt on a given input, you only
>consider those executions which actually do halt. Informally, you then
>go back and look at this as having "guessed right" at each state
>transition.
Yup. The point, of course, being that for formal computational purposes
it's not really useful to examine the blind alleys that *might* be
gotten into.
>
>Back when I learned this stuff 20 years ago, we talked about NDTM's
>being the machines themselves, not sets of permissible execution paths
>on the machines.
Actually, one still discusses the machines themselves -- they are
simply defined as not taking impermissible paths. 8-) At this point,
I agree, it's down to a very minor semantic issue.
The part that *isn't* a minor semantic issue is this -- NDTMs aren't
realizable (with the possible exception of quantum machines, which
didn't even exist when the math was developed), any more than the
TMs themselves are realizable with their infinite tapes. There's a
formal proof of equivalence between DFA and NFA; that doesn't hold
at higher levels and is at the heart of the P == NP conjecture.
Oracular computation is a completely different subject studied
in its own right.
-kitten
------------------------------
From: Nathan Kennedy <[EMAIL PROTECTED]>
Subject: Re: Random numbers from a sound card?
Date: Tue, 26 Jan 1999 07:09:28 +0800
David Ross wrote:
>
> Has anyone had success using a sound card (like a Sound Blaster) to
> generate streams of random numbers?
Sure. My favorite (T)RNG method.
>
> What sort of audio source would you suspect would be the best to use
> in generating random numbers?
I tune a cheap AM radio to a loud static channel, and wire that into the
mic port.
> How would you test the 'quality' of the generated random number
> stream?
Of course, you can't test the 'quality' by looking at the random numbers
generated. You need to estimate the entropy of your source, and of course
it's always going to be an estimate, you can almost never prove it.
What I did, was compress it, multiply my hash size by the compression ratio
by a fudge factor of 10. Then I would hash that much data, and assumed
that the result was very close to 100% entropy. This is rather paranoid
and slow though. If you don't need 100% entropy just go ahead and
continually sample /dev/audio for data and use it as entropy for a PRNG,
and sample the PRNG as often as you like. The quality should still be
excellent... As long as you've got >128 bits of entropy total and the PRNG
does its job, the result should be quite secure as long as nothing gets
compromised.
Nate
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random numbers from a sound card?
Date: Tue, 26 Jan 1999 00:28:16 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 25 Jan 1999 20:11:33 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>> How would you test the 'quality' of the generated random number
>> stream?
>There are tests for statistical quality, e.g. Maurer's universal
>statistical test. I am ignorant of tests for crypto quality.
That's because there aren't any.
It is a fundamental precept of crytpography that randomness is a
property of how a number is generated, not a property of a number
itself.
>I guess the issue of cryptological strength is inherently fuzzy
Not really. The OTP system is proveably secure.
>and not entirely separable from subjectivity and concepts like
>confidence intervals, i.e. no security can be claimed on an absolute
>scale in practice. But experts might refute my un-knowledgeable
>assertions.
If someone tells you that he can demonstrate that a given number is
crypto-grade random without considering the way it is generated, he is
making a fundamental error, one of the most widespread errors in
cryptography.
Bob Knauer
"An honest man can feel no pleasure in the exercise of power over
his fellow citizens."
--Thomas Jefferson
------------------------------
From: [EMAIL PROTECTED] ("Simon Copsey")
Subject: Would the gentleman with Mondex knowledge in the USA please contact me again.
Date: Tue, 26 Jan 1999 00:28:29 GMT
We failed to touch base last time and now my off line reader has eaten
your details.
You know who you are!
Many thanks
Simon
------------------------------
From: Anthony <[EMAIL PROTECTED]>
Subject: Re: S-box cycles
Date: Tue, 26 Jan 1999 12:48:30 +1300
Could someone provide a definition of an S-box's "cycle length" please.
Thanks
Anthony.
[EMAIL PROTECTED] wrote:
> I have what I think is a simple question:
>
> How important, in terms of cryptographic strength, is whether or not
> an S-box's cycle length is equal to its size?
------------------------------
From: ©ú¥Õ <[EMAIL PROTECTED]>
Subject: Re: [req]:Cryptanalysis tool - word pattern table
Date: Tue, 26 Jan 1999 08:33:15 -0800
Reply-To: [EMAIL PROTECTED]
Darren New wrote:
>
> > > > It would list, for example, a pattern such as "ABACD" and then every
> > > > word in the English lang which fit that pattern (for the above example:
> > > > "every" fits).
> > > > Does anyone know where such a table can be obtained?
>
> It sounds like it would be very, very simple to write a program to do
> this if you could find a dictionary of English words. It sounds like a
> 10-line BASIC program to me, followed by "sort -u". The hard part would
> be to get an adequate dictionary.
Actually, I was thinking more along the lines of SNOBOL, ICON or Frogbit
(the later two being freeware).
But the problems are A] the dictionary, as you pointed out (I have
already written a dictionary compilation program in Frogbit) and B]
Time....as in I nowadays don't have the time to kick back on a computer
and hash out stuff like I used to (oh for the good ole days...) and what
time *is* available, I'd like to devote to getting directly back into
cryptanalysis....but then that's just me.
------------------------------
From: [EMAIL PROTECTED]
Subject: Unicity, DES Unicity and Open-Keys
Date: Tue, 26 Jan 1999 00:41:04 GMT
List:
The new version of the paper below is available at the MCG site, in
HTML. Comments are welcome.
===============================================================
Unicity, DES Unicity and Open-Keys
Ed Gerck
Archived at http://www.mcg.org.br/unicity.htm
Abstract
This exposition initially revisits the concept of "unicity" and shows
that key-length is not the most important parameter to evaluate the
security of cryptographic systems, discussing possible weakness in
current systems and alternatives as well. Applying the concepts
developed, the paper shows that DES English messages can be
brute-force attacked over a plaintext space of only 3 characters --
in an Identification Attack -- instead of the currently assumed limit
of 20 characters. This result immediately impacts the assumed
security of SSL, S/MIME and other protocols that may use DES in
cipher negotiation. The exposition also advances other topics to
motivate discussion of higher-security cipher systems, even when
short key-lengths need to be used. Specially, concrete examples show
the usefulness of "open trust" -- called Open-Keys -- to increase
security in addition to the currently exclusive use of "closed trust"
(i.e., secret-keys). Since Open-Keys are public, the concept may
afford a way to increase security even within secret-key bit-length
limitations, imposed export wise or by technical constraints. By
allowing the secure use of smaller secret-keys, the Open-Key concept
can have other applications, such as in smart-cards, digital
signatures, authentication, non-repudiation, etc. This should not be
confused with the usual resource of adding uncertainty (e.g., as a
"salt") in order to increase attack workload, which is classified as
"open ignorance".
=================================================================
Cheers,
Ed Gerck
______________________________________________________________________
Dr.rer.nat. E. Gerck [EMAIL PROTECTED]
http://novaware.com.br
--- Meta-Certificate Group member -- http://www.mcg.org.br ---
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
** 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
******************************
