Cryptography-Digest Digest #608, Volume #14 Thu, 14 Jun 01 04:13:01 EDT
Contents:
Re: Sophie-Germain Primes for sale ("Ben Hamilton")
Re: Alice and Bob Speak MooJoo ("Paul Pires")
Re: Yarrow PRNG (Anton Stiglic)
Re: Alice and Bob Speak MooJoo ("Robert J. Kolker")
Re: Timer chip (Anton Stiglic)
Re: Looking for Mitsuru Matsui paper ("Scheidsrechter")
Re: Alice and Bob Speak MooJoo ("Paul Pires")
Re: Looking for Mitsuru Matsui paper ("Tom St Denis")
Re: Yarrow PRNG (Eric Lee Green)
Re: Yarrow PRNG (Eric Lee Green)
Re: Alice and Bob Speak MooJoo ([EMAIL PROTECTED])
Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY (wtshaw)
Re: Alice and Bob Speak MooJoo ("Paul Pires")
Re: Alice and Bob Speak MooJoo ("John A. Malley")
Re: Uniciyt distance and compression for AES ([EMAIL PROTECTED])
Re: When the signer is trusted do birthdays matter? ("Jakob Jonsson")
----------------------------------------------------------------------------
From: "Ben Hamilton" <[EMAIL PROTECTED]>
Subject: Re: Sophie-Germain Primes for sale
Date: Thu, 14 Jun 2001 10:15:33 +1000
Nice link, thanks,
Ben Hamilton
Anton Stiglic <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Just go to google, type "Sophie Germain Prime", the first hit
> you get will be:
> http://www.utm.edu/research/primes/glossary/SophieGermainPrime.html
> read the definition of Sophie Germain Prime.
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Alice and Bob Speak MooJoo
Date: Wed, 13 Jun 2001 17:11:41 -0700
Robert J. Kolker <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> David A Molnar wrote:
>
> >
> > I think the issue here is in the model, then. Normally we say Eve has
> > access only to the communication between Alice and Bob. As you point out,
> > given these assumptions about language, this means Eve gets noise as long
> > as she cannot observe Alice and Bob's referents.
>
> How would Eve know whether A/B are discussing the weather,
> the stockmarket or the war de jour? Is Eve in a position to
> force a topic of discussion on A/B. If so, some kind of referrent
> could be teased out, otherwise no. Is there any thing corresponding
> to the chosen plaintext attack here? I don't think so.
The outside world could force a topic which would be known
to Eve and provocative enough that Eve could guess that A&B
were commenting on it. An 8.7 earthquake might elicit a short
message between Alice and Bob which Eve could guess was
the equivalent of "Holy S**T Batman!!!"
>
> In the case of the Navajo Code Talkers, the Japanese who were
> evesdropping on their communication had some idea of what
> the Code Talkers were talking about, but were unable to tease
> out any specific words and meanings.
<snip>
That case was even more complicated. The Navajo language
is a not technological language and to suit wartime needs
the talkers got together and agreed on easily remembered
euphemisms for technical terms so there was actually a
three way conversion going on. (4 for the japanese)
American war tech jargon > euphemism > Navajo
& back. The poor japanese needed to compensate for
the know cultural difference between American and
Japanese and the unknown culture of Navaho. A
culture that brought us the concept of "walking in beauty"
and one which sees cyclic wheels rather than begining to
end paths.
It must have mucked their (The Japanese interceptors) brains
up pretty badly.
Paul
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Yarrow PRNG
Date: Wed, 13 Jun 2001 20:11:57 -0400
[EMAIL PROTECTED] wrote:
>
> Anton,
>
> thanks for the inputs ... do you have a version of Yarrow that is not dependent
> on SSL? It would be nice to have one that is standalone, that one can
> incorporate into other apps.
Maybe someone else does, we don't. You can always go and write your own
hash function and block cipher functionality to get what you want.
I think the code only includes openssl/des.h and openssl/sha.h
(and other block ciphers and hash functions, depending on what you
want, but you only need one of each).
>
> Also, does the link given below include the latest Yarrow paper?
It just includes a link to the site on counterpane that has the Yarrow
paper that was used.
--Anton
------------------------------
From: "Robert J. Kolker" <[EMAIL PROTECTED]>
Subject: Re: Alice and Bob Speak MooJoo
Date: Wed, 13 Jun 2001 20:20:02 -0400
Paul Pires wrote:
>
> It must have mucked their (The Japanese interceptors) brains
> up pretty badly.
Precisely! Ignorance (of the language) is bliss for the users of
that language. The interesting thing about the MooJoo scenario
is the Alice and Bob are conversing in the clear.
Bob Kolker
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Timer chip
Date: Wed, 13 Jun 2001 20:22:59 -0400
This works with my red-hat linux:
#ifndef _TIMER_H
#define _TIMER_H
#define TICKS 450000000.0 /* replace this by your CPU speed */
/*** Timing code ***/
typedef union ctrval {
struct {
unsigned int l; /* least significant word */
unsigned int h; /* most significant word */
} w32;
unsigned long long w64;
} ctrval;
/* Should take 11 cycles at user-level. */
static inline void
counter (union ctrval *v)
{
__asm __volatile ("rdtsc"
: "=a" (v->w32.l), "=d" (v->w32.h) :);
}
ctrval start, end;
void start_timer( void ) {
counter( &start );
}
/*
* return the difference from the time this
* function is called and the time when
* start_timer was called
*/
unsigned long long stop_timer( void /*const char* note*/ )
{
unsigned long val;
counter( &end );
val = end.w64 - start.w64;
/* fprintf( stderr, "%s took %ld clock ticks\n", note, val ); */
return val;
}
#endif
------------------------------
From: "Scheidsrechter" <[EMAIL PROTECTED]>
Subject: Re: Looking for Mitsuru Matsui paper
Date: Thu, 14 Jun 2001 00:42:10 GMT
I am not sure if this the paper you are looking for:
http://search.ieice.or.jp/1999/pdf/e82-a_1_117.pdf
--
Scheidsrechter
Despam for correct email
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> A while back Matsui did a paper on a new feistel design and had some
> analysis of cubic and inverse functions in GF(2^x).
>
> Does anyone know where I can find that paper? Matsui doesn't have a
> website!
>
> Tom
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Alice and Bob Speak MooJoo
Date: Wed, 13 Jun 2001 17:50:24 -0700
Robert J. Kolker <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Paul Pires wrote:
>
> >
> > It must have mucked their (The Japanese interceptors) brains
> > up pretty badly.
>
> Precisely!
Ehr..no. That wasn't my point. The lack of or unexpected
cultural referents was what I was getting at. Take it to extremes.
Dolphins & Humans. Manual, sinister, upward bound, dexterous,
digit, put your best foot forward, prestidigitation, indicate. All
of these have to do with the self-perception of someone with hands
and feet.
>From the other side.What would be the weird outlook (and thinking)
of a being that can routinely do 3d sonic scanning that makes our most
Sophisticated instruments trivially coarse.
It's not the different language of a being; it's the different being
and his language.
Paul
>Ignorance (of the language) is bliss for the users of
> that language. The interesting thing about the MooJoo scenario
> is the Alice and Bob are conversing in the clear.
No Bob. IMHO, the key is the inability to empathise with a different
kind of mind. If Bob Eve and Alice are all silicon valley yuppies
And Bob and alice "Invent" a new language, I'll put money on
Eve figuring it out in no time if she has any chance to observe
those things common to Alice and Bob.
Paul
>
> Bob Kolker
>
>
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Looking for Mitsuru Matsui paper
Date: Thu, 14 Jun 2001 01:17:32 GMT
"Scheidsrechter" <[EMAIL PROTECTED]> wrote in message
news:CLTV6.4093$[EMAIL PROTECTED]...
> I am not sure if this the paper you are looking for:
>
> http://search.ieice.or.jp/1999/pdf/e82-a_1_117.pdf
Exactly right paper.
Thanks a lot :-)
Tom
------------------------------
From: [EMAIL PROTECTED] (Eric Lee Green)
Subject: Re: Yarrow PRNG
Reply-To: [EMAIL PROTECTED]
Date: Thu, 14 Jun 2001 01:56:51 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
On 13 Jun 2001 14:41:56 GMT, Mark Wooding <[EMAIL PROTECTED]> wrote:
>Eric Lee Green <[EMAIL PROTECTED]> wrote:
>guess a 128-bit key for some `perfect' cipher, but you know that the key
>was generated using Yarrow-160. You `only' need to search 2^{128} -
>2^{64} keys -- that's a whole 2^{64} fewer than if you didn't know
>Yarrow had been used. (2^{64} is a tiddly tiny number compared to
>2^{128}.)
>
>> 2. Could this have been fixed by the simple step of adding yet another
>> SHA-1 to the algorithm, at the output, to further "stir" the values
>> being given to the user?
>
>Possibly. This isn't really the `right fix', though. It adds a load of
>complexity and makes it slower and harder to analyse.
So what *is* the "right fix"? Dumping the block cipher and, as with the
Linux /dev/urandom, using a MDA instead? (/dev/urandom is re-seeded
whenever possible with "true" random values from /dev/random fed into
its MD5 hash, but if random values aren't available, it increments
a counter and feeds the counter value into the MD5 hash).
As for the "harder to analyse", presumably that also means it's harder
for the attacker to analyse too. Though security through obscurity is
hardly a reassuring thing here :-(.
=====BEGIN PGP SIGNATURE=====
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org
iD8DBQE7KBhg3DrrK1kMA04RAmfsAKDGYEZcwJIOTbtS00P0qgjRQkifVACgz+i2
ZB4cnwifBQ9/BoYx5np3Kh0=
=sacJ
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Eric Lee Green)
Subject: Re: Yarrow PRNG
Reply-To: [EMAIL PROTECTED]
Date: Thu, 14 Jun 2001 01:59:12 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
On Wed, 13 Jun 2001 14:51:09 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote:
>However, hash functions are not known for their speed. If you find
You can say that again :-). I once saw someone decide they were going
to add an md5 checksum to each block of data put onto disk. It turned
out that on the equipment available at the time (Pentium 200 and such),
this limited performance to under 250K/sec, once all the other overhead
in the program was added in :-(. This from a program that could handle
several megabytes/sec on that same hardware without the md5.
>the need to slap a hash function over the outputs the question
>arises as to why you didn't put it at the heart of the algorithm
>in the first place.
So you like the design of the Linux /dev/urandom ?
=====BEGIN PGP SIGNATURE=====
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org
iD8DBQE7KBju3DrrK1kMA04RAg4uAKCbPtKAntIKwR0EUF1kTYE85fNZSgCg1L//
ynt8Azw9bfQkmeSGbmbs200=
=khwN
=====END PGP SIGNATURE=====
------------------------------
Subject: Re: Alice and Bob Speak MooJoo
From: [EMAIL PROTECTED]
Date: 13 Jun 2001 22:03:37 -0400
"Paul Pires" <[EMAIL PROTECTED]> writes:
>
> ...the talkers got together and agreed on easily remembered euphemisms
> for technical terms so there was actually a three way conversion going
> on. (4 for the japanese) American war tech jargon > euphemism > Navajo
> & back.
Except, of course, for the fact that the code-talkers' system was nothing
like what you describe.
(1) The system was devised by the Dept. of the Navy; it was not worked out
by the code talkers themselves.
(2) The code talkers were *not* conversing in Navajo. Message transmission
through a code talker worked as follows:
a. The message was written in English.
b. Each letter was replaced by an English word starting with that letter.
c. Each English word was translated directly into Navajo.
d. The resulting Navajo ``message'' was transmitted.
The Japanese tortured a captured Navajo, Sgt. Joe Kieyoomia, because he
claimed he couldn't understand the messages at all. Trouble is, he was
telling the truth: he was not a code talker, and could not figure out
the messages.
The code talker program was successful--but it shouldn't have been. The
Japanese captured a living, breathing dictionary, and then squandered a
perfect opportunity. The facts of the case illustrate the achilles heel
of such a system, and how close the Japanese actually did come to breaking
it.
Len.
--
You're repeating the same old ``forks are bad and execs are
disastrous'' litany without _profiling_ where your time is actually
going.
-- Dan Bernstein
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY
Date: Wed, 13 Jun 2001 20:34:00 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
> Mark Wooding wrote:
> >
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > > But measures should have adquate (intuitionally reasonable)
> > > interpretations, I suppose. If a security measure
> > > says 0 security, then one would 'very naturally' think
> > > that that means no protection at all, isn't it?
> >
> > This is why we have different notions of security. There is a
> > difference between the information-theoretic security provided by the
> > one-time pad (and perfect secret-sharing systems) and the computational
> > security provided (by assumption) by most commonly-used symmetric and
> > asymmetric ciphers.
>
> The problem is whether one has a 'common' measure of
> security that could be applied to all sorts of encryptions.
Note that some ciphers are outside of both of these categories. The
strength of them ranges from stupidly simple to GOK.
There is no and can't be one common measure of security. Without
repeating them, I had to create that which some saidcould not be, a way to
variously describe comparitive security of different ciphers in several
ways. I can't ignore Shannon, even as he did not cover all the relative
factors and did not know and therefore could not include new aspects of
recent ciphers in his thinking.
>
--
In trying to get meaning from the TmV-OK saga, remember that
those who do not learn from history are apt to repeat it.
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Alice and Bob Speak MooJoo
Date: Wed, 13 Jun 2001 20:30:00 -0700
<[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> "Paul Pires" <[EMAIL PROTECTED]> writes:
> >
> > ...the talkers got together and agreed on easily remembered euphemisms
> > for technical terms so there was actually a three way conversion going
> > on. (4 for the japanese) American war tech jargon > euphemism > Navajo
> > & back.
>
> Except, of course, for the fact that the code-talkers' system was nothing
> like what you describe.
My description was not from any knowledge of the official system
It was the description of how it worked from an interview of a
code talker. My apologoies if it is an inaccurate rendition
but that is what I got from the narration. This fellow seemed to
think that it worked that way. I guess I have to stop watching the
History Channel :-(
>
> (1) The system was devised by the Dept. of the Navy; it was not worked out
> by the code talkers themselves.
>
> (2) The code talkers were *not* conversing in Navajo. Message transmission
> through a code talker worked as follows:
>
> a. The message was written in English.
> b. Each letter was replaced by an English word starting with that letter.
> c. Each English word was translated directly into Navajo.
> d. The resulting Navajo ``message'' was transmitted.
>
> The Japanese tortured a captured Navajo, Sgt. Joe Kieyoomia, because he
> claimed he couldn't understand the messages at all. Trouble is, he was
> telling the truth: he was not a code talker, and could not figure out
> the messages.
>
> The code talker program was successful--but it shouldn't have been. The
> Japanese captured a living, breathing dictionary, and then squandered a
> perfect opportunity. The facts of the case illustrate the achilles heel
> of such a system, and how close the Japanese actually did come to breaking
> it.
>
> Len.
>
>
> --
> You're repeating the same old ``forks are bad and execs are
> disastrous'' litany without _profiling_ where your time is actually
> going.
> -- Dan Bernstein
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Alice and Bob Speak MooJoo
Date: Wed, 13 Jun 2001 20:38:31 -0700
"Robert J. Kolker" wrote:
> >
> >
> > Before getting into nasty philosophy of language issues, one thing pops to
> > mind. If Eve cannot observe the referents for MooJoo - if these referents
> > are inaccessible to her - then *why* would she *want* to listen to Alice
> > and Bob? and if she *can*, doesn't that destroy the claimed
> > "security-through-inaccessible-referent" ?
>
> If Eve listned in she has no way of knowing what Alice and
> Bob are saying to each other. So the communication between
> Alice and Bob is secure. From Eve's p.o.v. she is getting
> noise from the A/B link.
>
What Eve gets is not _noise_ in the electrical
engineering/communications systems point of view, though. Eve detects
correlations between portions of the stream of signal over time. She'll
detect similar or identical modulations of signal characteristics
(amplitudes of frequencies, phases of frequencies ) in different
portions of the stream of signal over time. Time-varying modulation of
signal characteristics is indicative of communication between
intelligent creatures.
Eve can learn a lot about the "meaning" of the signal from their
responses with respect to the context dictated by events common to
Alice, Bob and her. She can correlate events, the signal patterns
following immediately after the events and any observable actions of
Alice or Bob and assign a rough "meaning" to the patterns.
Eve can build up a code book of patterns appearing the signal stream,
frequencies of occurrence and correlations with one another. Eve can
assign meanings (observed actions (if any) of Alice or Bob) to the
patterns. She can even build up a Markov model to produce strings of
these signal patterns. Then Eve has fun with Alice or Bob by playing
previous patterns or new patterns from the Markov model to them to gauge
their reactions. :-)
Eve *should* be able to carry out replay attacks or man-in-the-middle
attacks. (Duck calls and turkey calls spring to mind. They are a form
of replay attack. We make sounds these animals "understand" and act on
with measurable behavioral change. We are not to the best of my
knowledge actually speaking "duck" or "turkey" )
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Uniciyt distance and compression for AES
Date: Wed, 13 Jun 2001 22:14:46 -0800
Tim Tyler wrote:
>
> [EMAIL PROTECTED] wrote:
> : Tim Tyler wrote:
>
> :> Here is the model I think you should have adopted:
> :>
> :> Alice -> [encrypt] -> ...eve... -> [decrypt] -> Bob
> :>
> :> Unicity distance is as measured by Eve.
> :>
> :> We are interested in the effect of replacing [encrypt] and [decrypt]
> :> by [compress encrypt] and [decrypt decompress] respectively.
> :>
> :> What you have done is not /just/ make changes to the stages represented
> :> inside square brackets.
>
> :> You have made fundamental changes to the set of messages which are sent
> :> and their probabilities.
>
> : How is this avoidable if messages are compressed from n=4 to n=3?
> : There are 16 possible messages before compression and 8 possible after
> : compression.
>
> That is not how compression programs function. I'm talking about
> conventional compression programs, like zip, huffman, arithmetic, etc.
> These allow you to compress a file, decompress it again and wind up with
> the same result.
You misunderstood my example. The example compressor *encodes* 0000 as
000, 0001 as 001, etc. It doesn't just throw away the leading zero. The
decoder would reverse
the mapping so that 000 would decode into 0000, etc. So, all values that
compress
would decompress into exactly the same value. Anyway, I'm not trying to
understand specific compressor algorithms at this point. I'm trying to
understand the fundamentals of what *any* compressor does. Compressors
map m-bit values into n-bit values where n < m.
> :> Your system after the compressor is added can't even transmit some
> :> messages that were transmitted before - and *all* the probabilities of
> :> the messages occurring are changed!
>
> : This isn't surprising. [...]
>
> It was suprising to me. How you could think comparing the resulting
> systems had any meaning was most puzzling.
>
> : Can *any* compressor compress *all* possible messages in the original
> : message space?
>
> Of course not - but that is not how compressors operate either. They
> compress some files, and expand others.
My example allows for the expansion of the values that don't compress.
In fact, they don't affect the results in any way because I only
considered
the compressed message space.
> :> Why should putting in a compressor affect the frequency of the messages
> :> being sent? It should not.
> :>
> :> If you /must/ use a lossy compressor at least set the probability of
> :> messages it can't handle to be 0 initially, or you are comparing different
> :> systems with different message spaces.
>
> : Again, doesn't one *have* to compare different message spaces since the
> : value of n is different after compression??
>
> No, you should be comparing the same message spaces, otherwise the
> comparison is completely nonsensical.
How can the message spaces be the same when there are 2^m values in the
original message space and 2^n values in the compressed message space?
> :> Also, do not change the probabilities of the messages occurring, or else
> :> you are comparing entropies in very different systems - and it is no
> :> suprise that your unicity distances are all over the map.
>
> : The probabilities in the original message space are what they are. If
> : they are non-zero then assigning them zero probability isn't an option;
> : *that* would be altering the message space.
>
> Of course. But *don't* apply a compressor that can't accept these
> messages as inputs and pretend that nothing has changed.
How can a compressor accept all inputs if it is mapping values from
a larger message space into a smaller message space?
> : All the probabilities in my compressed message spaces sum to one [...]
>
> No they don't. Add up the probabilities in your second column, and you
> will find they exceed one. A minor arithmetic error on your part.
> I ignored it until now because there were other far more important errors
> to address.
The point is that they are supposed to sum to one, and since the
compressed
message space is smaller than the original message space the original
message
probabilities can't be used because then they don't sum to one.
> : Propose other probabilities.
>
> Leave the probabilities completely alone, you you are not comparing
> equivalent systems.
The message spaces can't be equivalent since n < m.
------------------------------
From: "Jakob Jonsson" <[EMAIL PROTECTED]>
Subject: Re: When the signer is trusted do birthdays matter?
Date: Thu, 14 Jun 2001 09:59:50 +0200
Here is an outline of a possible attack. An adversary wants to forge a
signature of a message M. To succeed, she takes another message N that she
knows that the legitimate signer will accept and sign. If the messages are
English text, the adversary can alter the messages in many ways (e.g., add
and delete spaces, switch between ";" with " -", switch between synonyms,
etc.). In this manner she will be able to create many (say 2^80) different
versions M1, M2, ..., N1, N2, ... of each of the messages with exactly the
same meaning as the original messages M and N, respectively. Now the
adversary applies a birthday attack to these two sets of messages. When a
collision (Mi,Nj) is found, she asks the signer to sign the harmless message
Nj. If the signer accepts, the adversary will obtain a forged signature of
Mi.
This construction is included in some paper, but I don't remember where.
Jakob
"Fat Phil" <[EMAIL PROTECTED]> skrev i meddelandet
news:[EMAIL PROTECTED]...
> I understand the birthday coincidence problem. (i.e. only ~22 random
> people is enough for a 50/50 chance of a birthday coincidence).
>
> However, if your document _originator_and_signer_ is Trusted Trent, and
> signatures are done on the document hash, then why do you need to
> consider the birthday attack. He's not going to be creating many
> documents in order to try to find two that hash together?
> In fact being a single person/company, he's only going to be releasing
> 'small' numbers of documents (few/day, say).
> Does that mean that in this situation hashes only need to be half as
> wide as one would normally recommend as they don't need to consider the
> birthday problem?
> Or have I missed something?
> Phil
------------------------------
** 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
******************************
