Cryptography-Digest Digest #471, Volume #14 Tue, 29 May 01 12:13:00 EDT
Contents:
Re: Discrete Log question (Mark Wooding)
Re: Good crypto or just good enough? (Mark Wooding)
Card Games (Nigel Smart)
Re: Card Games (Lorenz Franck)
Re: Random number generation. (jlcooke)
Crypto neophyte - programming question (edt)
Re: Uniciyt distance and compression for AES (jlcooke)
Re: Euroean commision will recommend all citizens to use encryption in email next
week, because of echelon. (Jan Panteltje)
Re: Discrete Log question (Lon Willett)
Re: Crypto neophyte - programming question (John Savard)
Re: Card Games (Richard Wash)
Re: Card Games (Bo Lin)
Re: Card Games (Charles Blair)
Re: Card Games (------)
Re: Uniciyt distance and compression for AES (Tom St Denis)
Re: Call for Beta Testers - HexEdit 2.1 (Tom St Denis)
Re: Crypto neophyte - programming question (edt)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Discrete Log question
Date: 29 May 2001 13:45:00 GMT
Lon Willett <[EMAIL PROTECTED]> wrote:
> Consider the following: if the range of H was larger, (e.g. if H took
> on values in the range 1 .. P-2), and you set x=H^3 mod P-1, then
> clearly the system is equivalent to using H (H^3 mod P-1 is an easily
> invertible permutation of the values 1 .. P-2).
Actually, the map x |-> x^3 is a permutation in Z/nZ precisely when
gcd(3, \phi(n)) = 1. Hence, whether this is a permutation or a
noninjective mapping (which would strictly weaken the security of the
scheme using a full-domain hash) depends on whether \phi(P - 1) is
indivisible by 3. This happens with probability 2^{-f} where f is the
number of odd prime factors of P - 1 (consider residues mod 6).
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Good crypto or just good enough?
Date: 29 May 2001 14:09:07 GMT
Eric Lee Green <[EMAIL PROTECTED]> wrote:
> On Tue, 29 May 2001 07:09:26 +0200, Stefan Lucks <[EMAIL PROTECTED]
> uni-mannheim.de> wrote:
>
> >I don't think so. Encrypting a key-independent hash value does not
> >necessarily provide a secure MAC. (Well, it depends on the choice of
> >encryption, but note that I mentioned using triple DES in OFB mode above.)
>
> Actually, it depends on the hash too. You'll note that this message, for
> example, is signed via SHA1.
Yes. And we know that digital signatures are vulnerable to offline
collision-finding attacks. This is often unacceptable for MACs.
The usual security notion for MACs, I believe, is to allow an adversary
to request a MAC for each of a (polynomially bounded) number of messages
of its choice and then measure its probability of successfully forging a
MAC on a new message (also of its choice) for which it didn't request a
MAC.
In this setting, an encrypted-hash scheme is no more secure than the
hash function is collision-resistant. (The adversary finds a collision,
requests a MAC for one of the preimages, and emits the other preimage
and the MAC.)
This is undesirable for MACs, because we'd like to be able to take
advantage of the keyed nature of a MAC function to make the output
small. Using a 64-bit encrypted-hash scheme is an instant failure.
> For that matter, with SHA1, it's arguable that
>
> X=(M XOR S) || ( H(M || K) )
>
> where K is some shared key value, is secure.
Why take half measures? We know
X = M xor S || H(K_0 || H(K_1 || M))
is strictly more secure. (Assume H is an iterated hash. Then a
postfix-key hash MAC can be broken if a collision can be found in the
compression function. Breaking HMAC -- the construction I've shown --
requires an adversary to find a collision *with random secret IV*.
> Or better yet, use public key encryption, and simply encrypt the hash
> with your private key. This does not require a shared secret (just a
> shared public key, exchanged somehow) and is thus a "better" guarantee
> of authenticity for some degrees of "better".
For *much* larger MACs, and *much* more processing time per message.
Asymmetric crypto is a no-no for this.
Use HMAC. You Know It Makes Sense.
-- [mdw]
------------------------------
From: Nigel Smart <[EMAIL PROTECTED]>
Subject: Card Games
Date: Tue, 29 May 2001 14:07:05 GMT
Hi All,
I am sure I once saw something about card games in a cryptographic
setting. But I cannot remember where.
Basically I would like to know is it possible for four people to
shuffle and deal 13 cards to each other
without either party knowing the cards of the other party
and
allowing each party to know that the cards have been dealt fairly
Basically this is some kind of multi-party computation but with a
shuffle.
Any pointers to the literature would be most helpful.
Yours
Nigel
--
Dr Nigel P. Smart | Phone: +44 (0)117 954 5163
Computer Science Department, | Fax: +44 (0)117 954 5208
Woodland Road, | Email: [EMAIL PROTECTED]
University of Bristol, BS8 1UB, UK | URL: http://www.cs.bris.ac.uk/~nigel/
------------------------------
From: Lorenz Franck <[EMAIL PROTECTED]>
Subject: Re: Card Games
Date: Tue, 29 May 2001 16:37:42 +0200
Nigel Smart schrieb:
> I am sure I once saw something about card games in a cryptographic
> setting. But I cannot remember where.
There was something in Neal Stephensons "Cryptonomicon" about the
Solitaire algorithm. AFAIR Bruce Schneier made it up.
Bye
L�r
--
"And God formed Eve out of Adams rib.." --
"Errmhh- Yes, sounds like cut and paste all useful
modules and build the stable beta from scratch."
------------------------------
From: jlcooke <[EMAIL PROTECTED]>
Subject: Re: Random number generation.
Date: 29 May 2001 14:45:21 GMT
In industry (with out an entropy device) you have a pool of data P
gathered from the environment. Heap, stack, instruction pointer,
network, keyboard (not much tough!) etc...
Define a mix operation which hashes H = hash(P), and appends this to the
start of P and the rest is thrown away.
After the initial data is collected, mix P until the entire poll has
been replaced twice.
Every time you want to get random data, memcpy() it from the end of P,
and mix() in at least as much data as you took out.
A modification of "H = hash(P cat K), K++" is top ensure the pool for
the PRNG doesn't get stuck in the loop. But this is rare in a well
designed PRNG.
JLC
Benjamin Johnston wrote:
>
> > > 2. have plenty of data, and prepend an integer to all of the data, and
> > > hash the whole lot to 160 bits. If I need more "random" data, I just
> > > increment the integer and hash it all again.
> > >
> /snip/
> > > So, what I'm asking, is:
> > >
> > > 1. is my approach (ie. the second one) silly?
> >
> > Generally yes. The idea is not to reuse seed material. Why not
> > consider this instead?
> >
> > Hash the lump of seed material into a 160 bit symmetric key and use a
> > cipher in CTR mode. (Ahem, afaik that's Yarrow)
>
> The idea was to use it as a "general purpose" random number source across
> my entire project; which includes prime number generation.
>
> For this reason I need a more general-purpose source of random data -- so
> that I can retreive variable amounts of data.
>
> I didn't want to have to, for example, "use up" lots of random data to
> generate some value (say, a candidate prime) only to discover that I have
> to discard it (sure -- for things to be random, you'd want this event to
> be partially "random"... but it seems a bit wasteful).
>
> I figured that with a large semi-random source, I could keep hashing the
> same data over and over again (making small, linear changes), and this
> would be fine provided that I didn't try to "extract" more "randomness"
> than was present in the original, collected data.
>
> Hmmm... I can already see a slight cause for concern... but part of the
> reason I suggested the second variation was that if I break up my
> semi-random data into "chunks"... I may be in danger of having some
> "chucks" which have very low entropy... but by hashing the whole file at
> once, then I reduce the danger of encountering a "bad block".
>
> > > 2. what is standard practice for this kind of problem?
> >
> > I actually don't know off hand.
>
> -Benjamin Johnston
> [EMAIL PROTECTED]
------------------------------
Date: Tue, 29 May 2001 10:52:54 -0400
From: edt
Subject: Crypto neophyte - programming question
I'm just getting into crypto (as of yesterday), and I'm coding a very
simple script to XOR a textfile with a passphrase.
After doing all the XORs, I get ASCII values between 1 and 127. I want
to convert these to display-friendly ASCII (i.e. values between 32 and
126).
How can I munge the values to get them printable, but in a way that can
be decrypted later?
This may be a dumb question for this group, but some of you must have
done this before. Thanks...
-eric
------------------------------
From: jlcooke <[EMAIL PROTECTED]>
Subject: Re: Uniciyt distance and compression for AES
Date: 29 May 2001 14:51:19 GMT
Agreed, if the cipher input has a known structure, this can be
exploited.
Input without structure is preferable.
And your shameless plug for BICOM is noted.
JLC - note: I've alterd the text below.
"SCOTT19U.ZIP_GUY" wrote:
> Well your right in the fact differnt langues have a different
> reduncacny so the unicity diestance would be different. Thats why
> when creaking a encryptin you need to know the language used.
> but if you BelIve Shannon and i think most who read him do. COMmpression
> does increase the unicity distance. If you had language with no
> measurable redunancy I guess you could encypt it with most anything.
------------------------------
From: [EMAIL PROTECTED] (Jan Panteltje)
Subject: Re: Euroean commision will recommend all citizens to use encryption in email
next week, because of echelon.
Date: Tue, 29 May 2001 15:01:30 GMT
On a sunny day (Tue, 29 May 2001 13:28:39 +0100) it happened "John Niven"
<[EMAIL PROTECTED]> wrote in
<eCMQ6.13200$[EMAIL PROTECTED]>:
>> I cannot stand for the accuracty of this news report, especially as I
>think
>
>http://news.bbc.co.uk/hi/english/world/europe/newsid_1357000/1357264.stm
>
>It's MEPs calling for encryption, not the Parliament or Commission, but it's
>true nevertheless.
>
>John
>
>--
>John Niven
>(Reply through newsgroup)
OK, I have read the URL.
Nice picture too of those 2 domes.
I knew about the UK spy centre, and demon.uk seems to have a direct
link to it (=demon.nl) my ISP....
So I already complained to them a year ago...
Now the question should perhaps become, what encryption will have to be the
'accepted standard' between individuals.
Probably most have PGP installed.
But I believe in obscurity :-)
Hey how about selling floppies or CDROMS with OTP keys on it hehe,
guaranteed random.
LOL
Seriously, I wonder where it will go.
Regards
Jan
>
>
>"Jan Panteltje" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> Sort of amazed me, this was leaked and I include the original message as
>> it reached me from NOS TV in teletext, with translation.
>>
>> It seems Echelon is used by the US and GB for industrial espionage,
>> I suppose they (the commision) thinks that by everyone encrypting their
>> email Echelon will become rather useles.
>>
>> Here is the message:
>...msg snipped...
>>
>> I cannot stand for the accuracty of this news report, especially as I
>think
>> encryption is not allowed in France, and GB is a member of the EEC.
>> So it may be a hoax.
>> We will have to wait and see....
>> One could also ask: Does Wiersma have shares in companies making
>encryption
>> software... or anyone in that committee...
>> or were they just testing if my keyword search program in teletext works?
>> hehehe
>> Regards
>> Jan
>
>
>
------------------------------
From: Lon Willett <[EMAIL PROTECTED]>
Subject: Re: Discrete Log question
Date: 29 May 2001 16:19:16 +0100
[EMAIL PROTECTED] (Mark Wooding) writes:
> Lon Willett <[EMAIL PROTECTED]> wrote:
>
> > Consider the following: if the range of H was larger, (e.g. if H took
> > on values in the range 1 .. P-2), and you set x=H^3 mod P-1, then
> > clearly the system is equivalent to using H (H^3 mod P-1 is an easily
> > invertible permutation of the values 1 .. P-2).
>
> Actually, the map x |-> x^3 is a permutation in Z/nZ precisely when
> gcd(3, \phi(n)) = 1. Hence, whether this is a permutation or a
> noninjective mapping (which would strictly weaken the security of the
> scheme using a full-domain hash) depends on whether \phi(P - 1) is
> indivisible by 3. This happens with probability 2^{-f} where f is the
> number of odd prime factors of P - 1 (consider residues mod 6).
You are correct in general (i.e. for arbitrary primes). But the
proposed system wasn't using arbitrary primes. Quoting from the
original message:
> I made a prime P such that P-1/2 is a big prime and P-1/2 is not 3
> (duh....).
Let Q = (P-1)/2. Q is a large prime. If P mod 6 is 1, then 3|Q (a
contradiction). So P mod 6 must be 5. Therefore Q mod 3 is 2. So
phi(P-1) = Q-1 is indivisible by 3 (Q-1 mod 3 = 1).
While I'm taking the opportunity to re-read the message, I notice that
I had said:
> (And, BTW, you really should iterate the application of the hash
> function, or otherwise do something that slows down dictionary
> attacks).
But I had forgotten that the dictionary attack requires calculating
g^(trial-x) mod P, so it is already slowed down significantly
(although slowing it even more might not hurt).
/Lon
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Crypto neophyte - programming question
Date: Tue, 29 May 2001 15:24:57 GMT
On Tue, 29 May 2001 10:52:54 -0400, edt
<[EMAIL PROTECTED]>
wrote, in part:
>I'm just getting into crypto (as of yesterday), and I'm coding a very
>simple script to XOR a textfile with a passphrase.
>After doing all the XORs, I get ASCII values between 1 and 127. I want
>to convert these to display-friendly ASCII (i.e. values between 32 and
>126).
>How can I munge the values to get them printable, but in a way that can
>be decrypted later?
>This may be a dumb question for this group, but some of you must have
>done this before. Thanks...
Values between 0 and 127 contain seven bits each. So if you take six
of them, and repackage the bits so that you have seven groups of six
bits, you can encode that into characters.
Of course, for such a simple (and of course, insecure) cipher as you
propose, since you are combining two streams of display-friendly
ASCII, you really should use this rule:
(( text character - 32 ) + ( passphrase character - 32 ))mod 95 + 32
to get display-friendly ASCII directly, without introducing additional
redundancy. (Since your input characters are from 32 to 126, if the
output ranges from 0 to 127, for any given output character, only
certain plaintext and passphrase characters are possible, not all of
them.)
John Savard
http://home.ecn.ab.ca/~jsavard/frhome.htm
------------------------------
From: Richard Wash <[EMAIL PROTECTED]>
Subject: Re: Card Games
Date: 29 May 2001 11:25:55 -0400
Lorenz Franck <[EMAIL PROTECTED]> writes:
> Nigel Smart schrieb:
>
> > I am sure I once saw something about card games in a cryptographic
> > setting. But I cannot remember where.
>
> There was something in Neal Stephensons "Cryptonomicon" about the
> Solitaire algorithm. AFAIR Bruce Schneier made it up.
http://www.counterpane.com/solitaire.html
Rick
------------------------------
From: Bo Lin <[EMAIL PROTECTED]>
Subject: Re: Card Games
Date: Tue, 29 May 2001 16:10:33 +0100
Hi, Nigel,
I think you are talking about "Mental Poker" which you can find in the
book:
D. E. Denning, "Cryptography and Data Security", Addison-Wesley, 1982.
Yes, it is about secure protocol design.
I hope the above helps.
Bo Lin
Networking and Computing Systems Group
Motorola Limited
Nigel Smart wrote:
>
> Hi All,
>
> I am sure I once saw something about card games in a cryptographic
> setting. But I cannot remember where.
>
> Basically I would like to know is it possible for four people to
> shuffle and deal 13 cards to each other
> without either party knowing the cards of the other party
> and
> allowing each party to know that the cards have been dealt fairly
>
> Basically this is some kind of multi-party computation but with a
> shuffle.
>
> Any pointers to the literature would be most helpful.
>
> Yours
>
> Nigel
> --
> Dr Nigel P. Smart | Phone: +44 (0)117 954 5163
> Computer Science Department, | Fax: +44 (0)117 954 5208
> Woodland Road, | Email: [EMAIL PROTECTED]
> University of Bristol, BS8 1UB, UK | URL: http://www.cs.bris.ac.uk/~nigel/
------------------------------
Subject: Re: Card Games
From: [EMAIL PROTECTED] (Charles Blair)
Date: Tue, 29 May 2001 15:29:32 GMT
Nigel Smart <[EMAIL PROTECTED]> writes:
>Hi All,
> I am sure I once saw something about card games in a cryptographic
>setting. But I cannot remember where.
> Basically I would like to know is it possible for four people to
>shuffle and deal 13 cards to each other
> without either party knowing the cards of the other party
>and
> allowing each party to know that the cards have been dealt fairly
Isn't this the "Mental Poker" problem? Goldwasser and Micali
gave a protocol in the first version of their Probabilistic Encryption
paper STOC 1982, pages 365-377. Curiously, the journal version of
this paper omitted this section.
They were dealing with two players, not four. I'm pretty sure
there has been a lot of later work on this kind of thing.
------------------------------
From: ------ <[EMAIL PROTECTED]>
Subject: Re: Card Games
Date: Tue, 29 May 2001 16:36:48 +0100
> There was something in Neal Stephensons "Cryptonomicon" about the
> Solitaire algorithm. AFAIR Bruce Schneier made it up.
But Solitaire is just an encryption algorithm, not what Nigel is looking
for. I think what he's refering to is something called "mental poker"
probably described in Applied Cryptography 2nd ed. IIRC it uses
properties of raising n to a power mod a prime, perhaps a bit like some
of the blind signature schemes?
------------------------------
From: [EMAIL PROTECTED] (Tom St Denis)
Subject: Re: Uniciyt distance and compression for AES
Date: 29 May 2001 08:44:42 -0700
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote in message
news:<[EMAIL PROTECTED]>...
> [EMAIL PROTECTED] wrote in <[EMAIL PROTECTED]>:
>
> >"SCOTT19U.ZIP_GUY" wrote:
> >>
> >> Uncity distance is a concept found by Shannon that is valid even
> >> today. It has to do with the amount of cipher text needed to be
> >> looked at in a ciphertext only attack to determine the key and
> >> the rest of a secret message.
> >[snip]
> >
> >
> >Unicity distance can be interpreted as the smallest number of
> >of ciphertext letters which must be intercepted in order to
> >expect a unique, *meaningful* decipherment. It
> >is a function of both keyspace entropy and the redundancy of the
> >"language". Language redundancy arises from the fact that not
> >all possible messages are meaningful.
> >
> >I don't see how compression makes a difference. Compression reduces
> >the redundancy (a message in a language that contains no redundancy
> >cannot be compressed), but since the redundancy is a property
> >of the *language* then not all decompressions will be meaningful.
> >
> >I don't think you can get around this. It seems to me that all you're
> >doing is adding another step, i.e. decrypt and then decompress to
> >determine
> >whether or not the message is meaningful, rather than just decrypting as
> >the case would be if no compression were used.
> >
> >Simply put, redundancy is a feature of the language. You can't change
> >the redundancy without changing the language. Without changing the
> >redundancy you can't change the unicity distance (assuming no
> >change in the entropy of the keyspace).
> >
> >Am I overlooking something?
>
> Well your right in the fact differnt langues have a different
> reduncacny so the unicity diestance would be different. Thats why
> when breaking a encryption you need to know the language used.
> But if you belive Shannon and I think most who read him do. Compression
> does increase the unicity distance. If you had language with no
> measurable redunancy I guess you could encypt it with most anything.
I have to start by saying my knowledge of information theory is not
extensive .... however ...
The original reply does make sense. You are not switching languages
just the representation. I.e I will swap A with B, B with C, C with
D, etc... The words look different but it's basically the same
language.
Afaik all I have todo is guess a key, see if the decompression is
valid then check if the message decoded looks valid. Too me I think
adding more layers gives more chances to filter out bad keys.
You could use your bijective compressors to solve the first problem
but the resulting plaintext (from guessed keys) will not always
resemble grammatical english.
There really is no way around the second problem.
Tom
------------------------------
From: [EMAIL PROTECTED] (Tom St Denis)
Subject: Re: Call for Beta Testers - HexEdit 2.1
Date: 29 May 2001 08:47:01 -0700
[EMAIL PROTECTED] (Andrew Phillips) wrote in message
news:<[EMAIL PROTECTED]>...
> HexEdit 2.1 is almost ready for release and we are looking for a small
> number of beta testers.
>
> For more information on HexEdit see "About HexEdit" below.
>
> After carefully reading the requirements below, if you're interested please
> answer the questions and forward your response to [EMAIL PROTECTED]
> Please send your reply before June 8th. We will reply to you by June 10th.
> All information and software will be available by June 15th.
<snip>
Questions.
1. Who would pay for a hex editor? I could write one in all of 20
minutes.
2. What does this have todo with sci.crypt?
3. Why are you using a windows platform? Why not go portable and
make it work under linux, etc... too?
Tom
------------------------------
Date: Tue, 29 May 2001 12:04:31 -0400
From: edt <[EMAIL PROTECTED]>
Subject: Re: Crypto neophyte - programming question
John Savard wrote:
> >How can I munge the values to get them printable, but in a way that can
> >be decrypted later?
>
> Values between 0 and 127 contain seven bits each. So if you take six
> of them, and repackage the bits so that you have seven groups of six
> bits, you can encode that into characters.
>
Wow, neat-o.
>
> Of course, for such a simple (and of course, insecure) cipher as you
> propose, since you are combining two streams of display-friendly
> ASCII, you really should use this rule:
> (( text character - 32 ) + ( passphrase character - 32 ))mod 95 + 32
That's the one I was looking for - it was on the tip of my brain.
I'm still struggling with the decryption of ciphertext "encrypted" this way,
though. Should I add 32 to the ciphertext character and the passphrase
character before XORing, and subtract 32 from the result? How do I account
for the mod-ing?
Of course, I'm just messing around here. It's my first lesson in
cryptography, and I hope my first lesson in cryptanalysis, too - I hope to
break it after it's done (without reverting to published methods). So, would
this cipher be vulnerable to frequency counts? I can't think of a way that
it could be; it seems to me that only the stupidest substitution cipher would
be broken this way.
Many thanks...
-eric
------------------------------
** 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
******************************
