Cryptography-Digest Digest #497, Volume #14 Sat, 2 Jun 01 15:13:01 EDT
Contents:
Re: Stream Cipher combiners ("Henrick Hellström")
Luby-Rackoff Theorems? ("Tom St Denis")
Re: Question about credit card number (Anne & Lynn Wheeler)
Re: Uniciyt distance and compression for AES (SCOTT19U.ZIP_GUY)
Re: A Newbie Question (David Formosa (aka ? the Platypus))
Re: Luby-Rackoff Theorems? (Nicol So)
Re: Luby-Rackoff Theorems? ("Tom St Denis")
Re: A Newbie Question ("Tom St Denis")
Re: Luby-Rackoff Theorems? (David Wagner)
Re: Question about credit card number (Anne & Lynn Wheeler)
Re: Luby-Rackoff Theorems? ("Matt Timmermans")
Re: Luby-Rackoff Theorems? ("Tom St Denis")
----------------------------------------------------------------------------
From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: Stream Cipher combiners
Date: Thu, 31 May 2001 19:44:20 +0200
"Nigel Smart" <[EMAIL PROTECTED]> skrev i meddelandet
news:[EMAIL PROTECTED]...
> Z/nZ is always "Integers modulo n under addition"
>
> (Z/nZ)^* is what "Math" people would use for the group of
> "Integers modulo n under multiplication"
Hmm. There is also an ontological issue. The elements of Z/nZ are, by the
definition of quotinent groups, equivalence classes (nZ, nZ+1,
nZ+2,..,nZ+n-1). Picturing the elements of "integers under addition modulo
n" as equivalence classes is coherent with the concept of "modulo" as an
equivalence relation, like in the expression 10 = 6 (mod 4). But this
ontological picture is not coherent with the "mod" operator implemented in
most programming languages, which outputs an unequivocal residue from
integer division. This operator will give you (6 mod 4) = 2 all of the time,
and never (6 mod 4) = 10. I believe that the same of true of the mod
functions in most bignum libraries. In this case you identify the elements
of "integers under addition modulo n" with the least non-negative members of
each equivalence class in Z/nZ. That's why I prefer Z_n over Z/nZ.
--
Henrick Hellström [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Luby-Rackoff Theorems?
Date: Sat, 02 Jun 2001 13:21:46 GMT
If I understand correctly one of the LR theorems is about making a random
permutation out of a three round feistel. It involves truly random
functions as F functions where one of them (at least) is not a bijection.
If I get this correctly isn't this theorem recursive?
I.e take three random eight bit functions. Now you have a 16 bit PRF, etc..
This is the Turtle design (Matt Blaze) right?
I wonder.... other than the obvious efficiency issue why don't people
consider these? They are provably random permutations and are generally
easy to design...?
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
Subject: Re: Question about credit card number
Reply-To: Anne & Lynn Wheeler <[EMAIL PROTECTED]>
From: Anne & Lynn Wheeler <[EMAIL PROTECTED]>
Date: Sat, 02 Jun 2001 14:28:43 GMT
Chenghuai Lu <[EMAIL PROTECTED]> writes:
>
> Even if the CC numbers are stored in an encrypted form in the back ends,
> they are easy to break since all of CC numbers are encrypted using the
> same master key. Isn't it right?
note that a master file of CC transactions containing CC numbers is
likely to be in constant use ... adding new transactions, various
administration operations against transactions in progress, other
types of transaction reference operations. bulk encrypting/decrypting
such a file on every operation would quickly become cumbersome. Even
two level file where transaction level detail has an obfuscated CC
number with CC-mapping in 2nd bulk encrypted file also becomes
cumbersome (basically the file exists because a lot of business
processes are using it).
part of the issue goes to authentication and access control
... similar to the medical data thread in this n.g.
an alternative is the financial industry's electronic payment object
for all account-based transactions standard ... X9.59 (various refs:
at http://www.garlic.com/~lynn/) where account numbers used in
(authenticated) x9.59 transactions are defined to not be useable in
non-authenticated transactions (i.e. harvesting of "x9.59-related"
account numbers doesn't provide a lot of fraud benefit since they
can't be used in non-authenticated, non-x9.59 transactions).
--
Anne & Lynn Wheeler | [EMAIL PROTECTED] - http://www.garlic.com/~lynn/
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Uniciyt distance and compression for AES
Date: 2 Jun 2001 14:38:21 GMT
[EMAIL PROTECTED] (John A. Malley) wrote in
<[EMAIL PROTECTED]>:
>We don't need to compress s1, s2, s3 or s4 before encipherment with a
>cipher with perfect secrecy. Shannon's perfect secrecy is that perfect
>- compression prior to its application does nothing to increase security
>of the ciphertext against ciphertext-only cryptanalysis.
From the model you have shown compression not needed since its already
a perfect bijection. When viewed from an attackers point of view.
That is you only have 4 cipher texts. Pick one. Then no matter
what key the attacker uses it they all go back to a possible
input message. The problem is if you had used a nonbijective compression
and then exaimed the cipher text and checked all the keys you would
lose your bijection and thus perfect security.
>
>In the bijective compression model, as I understand past posts, Alice
>and Bob would compress s1, s2, s3 and s4 to m1, m2, m3 and m4 and then
>encrypt the resulting m_i using the shared secret key k_i:
>
>s1 <-> m1
>s2 <-> m2
>s3 <-> m3
>s4 <-> m4
>
>followed by encipherment of m_i using the transformation tables for m_i
>way back up in this post.
>
>So s1 compresses to m1, s2 compresses to m2, s3 compresses to m3 and s4
>compresses to m4. What exactly s1, s2 ,s3 and s4 are in exact value is
>known to Alice and Bob but not Eve. And since any set S of four finite
>strings where P(s1) = 1/2, P(s2) = 1/4, P(s3) = P(s4) = 1/8 can be
>represented by M, even if Eve gets the message m_i she doesn't know what
>s_i value it corresponds to since Eve doesn't have the compression
>mapping.
But in the model I've been assuming Eve does know the compression
routine. The compression routine is assumed known.
Eve does know it. So in this case Alice and Bob have a perfect
ecryption method that is known to Eve for some 4 messages.
But ALice and Bob are communicateing some other 4 messages so
they do a bijective mapping from this new set bijective compression
if you will. And Eve also knows what those four messages are.
>This threat model is not the same one used in Shannon's paper for his
>example of perfect secrecy. In Shannon's model, Eve knows everything BUT
>the secret key value - and still there is perfect secrecy.
I anwsered this above
>
>The Shannon example of a cipher with perfect secrecy does not require
>compression at all and does not use the same threat model as that
>assumed for bijective compression (as I understand it). Shannon's paper
>does not readily support any argument for bijective compression.
Look at it this way instead of 4 message think of 16 states.
I have a curent encryption system that is not perfect. But uses
a two bit key. WHen I use key one for example
it maps message 1 to a 1 bit cipher text. And like wise maps
message 2 to 3 bit cipher text and message 3 to 4 bit cipher
text and message 4 to 5 bit cipher text. Key two map message one
to 6 bits and so on so that message 4 goes to 9 bits. And so
So that when done each Meassage key combination you want to send
maps to a different bit combinaion. This clearly is not a perfect
cipher. Also notice the 2 bit cipher out is not in the set of possible
out ciphers at this time since no used message maps to it.
Example you get three bits outs you know it was message #2
encrypted with key 1.
When you test the other keys they map back if at all to sequences of
symbols that are not messages. If you exaimed in this system
the 2 bit cipherout which could not have been used for any of the
messages. It just so happens they decrypt to 4 sequences just like
your example. Know I could bijective compress the input messages
so that my 4 message map to that speaical set of 4 sequences that
exsit when I happened to notice the 2 bit case maps back to 4 sequennces
in a exact manner as your example. When this bijective compression is
done. And you know encrypt with the same encryption system for the
message you use each key now maps it to 2 bits and in a why when
EVE reads the output now she is in trouble since this bijective
compress made this weak system a perfect system.
But I claim its bijective you may have noticed that it wasn't
really bijective to whole symbol space. But only to the set of
possbile sequences used before encryption. So that the bijection
really only had to hold for the possbile space where message lie
so that when each key tested it leads back to a possible input.
In the real world of block ciphers this means each key when tested
has to lead back to a possible valid input. In other words a
compressor that is bijective to binary files. Could even be used
for a ECB mode of encryption if each real message compressed to
a multiply of the block size. This may be hard to do but it shows
bijective compressors can turn a not perfect encryption system
into a perfect one at least for case above. You also never
mentioned how compression increases the entropy per bit.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: [EMAIL PROTECTED] (David Formosa (aka ? the Platypus))
Subject: Re: A Newbie Question
Reply-To: [EMAIL PROTECTED]
Date: Sat, 02 Jun 2001 15:01:55 GMT
On Fri, 01 Jun 2001 13:10:05 GMT, Tom St Denis <[EMAIL PROTECTED]> wrote:
[...]
> Again I answered this question yesterday (um you really should read the
> posts here).
>
> Look for digraphs, etc... if you decrypt and it's ascii and has TZ or PM in
> it, it's probably not the key.
Its 12:30PM in the Easten TZ
--
Please excuse my spelling as I suffer from agraphia. See
http://dformosa.zeta.org.au/~dformosa/Spelling.html to find out more.
Free the Memes.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Luby-Rackoff Theorems?
Date: Sat, 02 Jun 2001 11:20:32 -0400
Reply-To: see.signature
Tom St Denis wrote:
>
> If I understand correctly one of the LR theorems is about making a random
> permutation out of a three round feistel. It involves truly random
> functions as F functions where one of them (at least) is not a bijection.
The Luby-Rackoff results are about constructing *pseudo*random
permutations from *pseudo*random functions, not exactly as you stated.
The definition of pseudorandomness has many nuances and important but
unobvious implications; it's difficult to explain in a few words.
I don't have the paper with me right now, but I remember the gist of it.
The function F in general is not bijective, but permutations are not
excluded.
If the application is secure encryption, you probably want to use a
4-round Feistel structure (to obtain a "super pseudorandom invertible
permutation generator"). See the Luby-Rackoff paper for more details.
> If I get this correctly isn't this theorem recursive?
Yes, you can apply the result recursively.
> I.e take three random eight bit functions. Now you have a 16 bit PRF, etc..
No. Pseudorandomness is a property of a scalable scheme. You cannot talk
about pseudorandomness when the security parameter is fixed at a given
value.
> This is the Turtle design (Matt Blaze) right?
I don't know--I'm not familiar with Turtle.
> I wonder.... other than the obvious efficiency issue why don't people
> consider these? They are provably random permutations and are generally
> easy to design...?
Of course people have considered it, it's such as obvious idea. What a
recursive application of the Luby-Rackoff results yield is not a
"provably random permutation", it is just another "pseudorandom
invertible permutation generator" to use the author's terminology. You
have to be *extremely* careful about what is proved. The devil is in the
details.
--
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Luby-Rackoff Theorems?
Date: Sat, 02 Jun 2001 16:06:58 GMT
"Nicol So" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >
> > If I understand correctly one of the LR theorems is about making a
random
> > permutation out of a three round feistel. It involves truly random
> > functions as F functions where one of them (at least) is not a
bijection.
>
> The Luby-Rackoff results are about constructing *pseudo*random
> permutations from *pseudo*random functions, not exactly as you stated.
> The definition of pseudorandomness has many nuances and important but
> unobvious implications; it's difficult to explain in a few words.
>
> I don't have the paper with me right now, but I remember the gist of it.
> The function F in general is not bijective, but permutations are not
> excluded.
>
> If the application is secure encryption, you probably want to use a
> 4-round Feistel structure (to obtain a "super pseudorandom invertible
> permutation generator"). See the Luby-Rackoff paper for more details.
>
> > If I get this correctly isn't this theorem recursive?
>
> Yes, you can apply the result recursively.
>
> > I.e take three random eight bit functions. Now you have a 16 bit PRF,
etc..
>
> No. Pseudorandomness is a property of a scalable scheme. You cannot talk
> about pseudorandomness when the security parameter is fixed at a given
> value.
>
> > This is the Turtle design (Matt Blaze) right?
>
> I don't know--I'm not familiar with Turtle.
>
> > I wonder.... other than the obvious efficiency issue why don't people
> > consider these? They are provably random permutations and are generally
> > easy to design...?
>
> Of course people have considered it, it's such as obvious idea. What a
> recursive application of the Luby-Rackoff results yield is not a
> "provably random permutation", it is just another "pseudorandom
> invertible permutation generator" to use the author's terminology. You
> have to be *extremely* careful about what is proved. The devil is in the
> details.
Thanks, I had a hunch I was missing a slight detail.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: A Newbie Question
Date: Sat, 02 Jun 2001 16:09:19 GMT
===== Original Message =====
From: "David Formosa (aka ? the Platypus)" <[EMAIL PROTECTED]>
Newsgroups: sci.crypt
Sent: Saturday, June 02, 2001 11:01 AM
Subject: Re: A Newbie Question
> On Fri, 01 Jun 2001 13:10:05 GMT, Tom St Denis <[EMAIL PROTECTED]>
wrote:
>
> [...]
>
> > Again I answered this question yesterday (um you really should read the
> > posts here).
> >
> > Look for digraphs, etc... if you decrypt and it's ascii and has TZ or PM
in
> > it, it's probably not the key.
>
> Its 12:30PM in the Easten TZ
I won't continue this except to say the # of times TZ occurs throughout
english is much less than other digraphs.
Note I said "probably not the key". You guys (wait this includes me too)
jump to quickly to retort. Had you actually read my post you would realize
that "Easten TZ" [sic] would have passed through my sieve, as would "TZ MN
OP QR TU ZZ". But I would feel "Easten TZ" [sic] would pass higher than "TZ
MN .." which is how my method works. (well it's not "my" method, but the
method I was discussing).
Tom
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Luby-Rackoff Theorems?
Date: Sat, 2 Jun 2001 16:23:35 +0000 (UTC)
Nicol So wrote:
>> If I get this correctly isn't [the Luby-Rackoff] theorem recursive?
>
>Yes, you can apply the result recursively.
But beware: The guaranteed security level drops dramatically
each time you apply it. Remember, these security theorems
say "the construction is secure against adversaries using at
most q queries"; and the q will go down by the square root
for each extra level of recursion.
------------------------------
Subject: Re: Question about credit card number
Reply-To: Anne & Lynn Wheeler <[EMAIL PROTECTED]>
From: Anne & Lynn Wheeler <[EMAIL PROTECTED]>
Date: Sat, 02 Jun 2001 16:39:37 GMT
Anne & Lynn Wheeler <[EMAIL PROTECTED]> writes:
> an alternative is the financial industry's electronic payment object
> for all account-based transactions standard ... X9.59 (various refs:
> at http://www.garlic.com/~lynn/) where account numbers used in
there is some class of current unauthenticated transactions that
depend on account numbers and/or other customer related information
.... effectively turning those items into "shared secrets" ... aka
just knowing such a "shared secret" allows fraudulent transactions to
be performed ... the attraction in harvesting of CC#s is just one
example.
--
Anne & Lynn Wheeler | [EMAIL PROTECTED] - http://www.garlic.com/~lynn/
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Luby-Rackoff Theorems?
Date: Sat, 2 Jun 2001 14:16:17 -0400
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:KL5S6.9000$[EMAIL PROTECTED]...
> I.e take three random eight bit functions. Now you have a 16 bit PRF,
etc..
The term "psuedo-random" applies to lots of things you wouldn't like.
(256^256)^3 is much less than 65536!, so most permutations of 16 bit numbers
can't be constructed this way. To randomly select such a permutation will
take about 1000000 random bits.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Luby-Rackoff Theorems?
Date: Sat, 02 Jun 2001 18:36:05 GMT
"Matt Timmermans" <[EMAIL PROTECTED]> wrote in message
news:F2aS6.22838$[EMAIL PROTECTED]...
>
> "Tom St Denis" <[EMAIL PROTECTED]> wrote in message
> news:KL5S6.9000$[EMAIL PROTECTED]...
> > I.e take three random eight bit functions. Now you have a 16 bit PRF,
> etc..
>
> The term "psuedo-random" applies to lots of things you wouldn't like.
> (256^256)^3 is much less than 65536!, so most permutations of 16 bit
numbers
> can't be constructed this way. To randomly select such a permutation will
> take about 1000000 random bits.
Actually that would be (256!)^3 or about 2^5051, wheras a 65536 element set
can have about 2^954036.863550 possible orders.
I agree they are diff #'s but does LR specifically say it must be randomly
selected from the set of all perms?
Tom
------------------------------
** 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
******************************
