Cryptography-Digest Digest #507, Volume #14 Sun, 3 Jun 01 19:13:01 EDT
Contents:
Re: Def'n of bijection (Tim Tyler)
Re: Def'n of bijection ("Tom St Denis")
Re: Def'n of bijection ("M.S. Bob")
Re: UK legislation on cryptographic products ("M.S. Bob")
Re: Uniciyt distance and compression for AES (Tim Tyler)
Re: Sv: Top Secret Crypto (John Savard)
Re: Uniciyt distance and compression for AES (Tim Tyler)
Re: Def'n of bijection (John Savard)
Re: Best, Strongest Algorithm (gone from any reasonable topic) ("Scott Fluhrer")
Re: PRP vs PRF (was Luby-Rackoff Theorems) ("Scott Fluhrer")
Re: S-Boxes ("Yashar Alishenas")
Re: S-Boxes ("Tom St Denis")
Re: S-Boxes ("Scott Fluhrer")
Re: PRP vs PRF (was Luby-Rackoff Theorems) ("Tom St Denis")
Re: Uniciyt distance and compression for AES ("Tom St Denis")
benefits of compression for security ("Tom St Denis")
Re: Dynamic Transposition Revisited Again (long) ([EMAIL PROTECTED])
Re: PRP vs PRF (was Luby-Rackoff Theorems) (David Wagner)
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Reply-To: [EMAIL PROTECTED]
Date: Sun, 3 Jun 2001 21:50:47 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: "Nicol So" <[EMAIL PROTECTED]> wrote in message
:> Tom St Denis wrote:
:> > That means it's invertible and closed right (i.e from set A to set B,
:> > A=B)?
:>
:> Invertible? yes. Domain = range? No.
: It said "all bijections have a function f' such that f'(f(x)) = x" and "for
: every element of the codomain there is some element of the domain which maps
: to it"
: This means in the case of TimTyler's argument about 1 byte => 3 byte is a
: bijection [...]
You'd better quote what I actually said if you're going to do this.
A /particular/ one-byte value mapped to a three byte value in the
bijection I was discussing.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Date: Sun, 03 Jun 2001 22:03:25 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : "Nicol So" <[EMAIL PROTECTED]> wrote in message
> :> Tom St Denis wrote:
>
> :> > That means it's invertible and closed right (i.e from set A to set B,
> :> > A=B)?
> :>
> :> Invertible? yes. Domain = range? No.
>
> : It said "all bijections have a function f' such that f'(f(x)) = x" and
"for
> : every element of the codomain there is some element of the domain which
maps
> : to it"
>
> : This means in the case of TimTyler's argument about 1 byte => 3 byte is
a
> : bijection [...]
>
> You'd better quote what I actually said if you're going to do this.
>
> A /particular/ one-byte value mapped to a three byte value in the
> bijection I was discussing.
Correct me if i am wrong but the whole point of the BICOM stuff was that all
inputs map to an output and all elements on the output side map to an input.
Scott said that he could make a compressor where inputs mapped to outputs of
different length (i.e 1 => 3). This would mean that all 3's must map to 1
bytes. Violation of terms.
He should have said some of the 3 bytes goto 1 byte (i.e 256 of them) and
the other 3 byte messages map to other lengths...
Tom
------------------------------
From: "M.S. Bob" <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Date: Sun, 03 Jun 2001 22:59:00 +0100
Tom St Denis wrote:
>
> http://www.dictionary.com/cgi-bin/dict.pl?term=bijection
>
> Aha. One-to-one and onto.
>
> That means it's invertible and closed right (i.e from set A to set B, A=B)?
Consider from Z to 2Z under the mapping y = 2x.
------------------------------
From: "M.S. Bob" <[EMAIL PROTECTED]>
Subject: Re: UK legislation on cryptographic products
Date: Sun, 03 Jun 2001 23:03:16 +0100
demon news wrote:
>
> Hello!.
>
> Could anybody let me know what the current legislation is for
> cryptographic products in the UK?.
Hire a lawyer or talk to the DTI to be certain. But general interest:
See http://www.fipr.org/ Foundation for Information Policy Research
Also check ukcrypto mailing list.
http://www.chiark.greenend.org.uk/mailman/listinfo/ukcrypto
Followups directed to talk.politics.crypto.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Uniciyt distance and compression for AES
Reply-To: [EMAIL PROTECTED]
Date: Sun, 3 Jun 2001 22:09:03 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: "Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
:> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> : You're argument is only valid if we are trying to find randomly
:> : compressed data streams.
:>
:> The conclusion holds no matter what type of data you are dealing with.
:>
:> If you have a compressor that succeeds in compressing your target data,
:> then compression before encryption will increase the unicity distance of
:> the resulting system.
: That's not true [...]
Yes it is.
Recall the unicity distance is how much cyphertext you need before you
have a unique correct decrypt.
Compression reduces the redundancy in the inputs to the cipher.
Consequently you need more ciphertext to be able to identify
whether you have a correct decrypt, because a larger proportion
of decrypts look like plausible messages.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Sv: Top Secret Crypto
Date: Sun, 03 Jun 2001 22:21:29 GMT
On Sun, 3 Jun 2001 23:18:54 +0200, "Peter Nielsen" <[EMAIL PROTECTED]>
wrote, in part:
>The comments which have appeared up
>to now indicate arrogance and lack of interest in learning a new and
>exciting program to know.
Lack of interest is right. But lack of interest is to be expected.
People are more likely to be interested in a new program if they have
reason to believe that the people behind it knew what they were doing.
Using the term "one-time pad" loosely is one of those things that
quickly inspires suspicions otherwise.
That which is new has to work to be taken seriously. That is a natural
consequence of the fact that there are only so many hours in the day.
John Savard
http://home.ecn.ab.ca/~jsavard/frhome.htm
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Uniciyt distance and compression for AES
Reply-To: [EMAIL PROTECTED]
Date: Sun, 3 Jun 2001 22:18:18 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: "Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
:> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
:> :> So what are you going to do if the compression is so good that *all*
:> :> the messages appear to be in English?
:>
:> : How is that possible? [...]
:>
:> Like this (for example):
:>
:> 0 <-> It is raining in Spain.
:> 1 <-> All quiet on the western front.
[...]
:> 65534 <-> No hope of remission for the patient.
:> 65535 <-> Burn everything as soon as possible.
:>
:> Messages are restricted to a set of 65536 possible ones. A subset of the
:> English language - but enough for weather reports, status reports, etc.
: This is wholly impractical. Its not very versatile and requires me to lug
: around a dictionary...
This was an /example/ - designed to demonstrate your error as clearly and
concisely as possible, to assist you in understanding the issue.
To object that the result is not very useful misses the point.
:> : That form of compression would not be practical. [...]
:>
:> Well, the example of all possible English text messages is not
:> really the subject of this discussion. We are talking about whether
:> compression before encryption increases the unicity distance
:> of the resulting system. The existence of "perfect" text compressors
:> is neither here nor there [...]
:>
:> In my example, a perfect compressor increased the unicity distance to
:> infinity. A less-than-perfect compressor will still increase the unicity
:> distance, but not by so great a degree.
: I don't see compression as helping [...]
...but your thinking on the issue is clearly faulty - since you've just
spent half a dozen messages defending the thesis that compression doesn't
increase the unicity distance of the resulting system.
The unicity distance affects whether a computationally unbounded attacker
can solve the system to get a unique result.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Def'n of bijection
Date: Sun, 03 Jun 2001 22:23:53 GMT
On Sun, 03 Jun 2001 22:03:25 GMT, "Tom St Denis"
<[EMAIL PROTECTED]> wrote, in part:
>Correct me if i am wrong but the whole point of the BICOM stuff was that all
>inputs map to an output and all elements on the output side map to an input.
The point is, though, that in a bijection, the domain need not equal
the range.
A - 1
B - 2
C - 3
is bijective, and its inverse is
1 - A
2 - B
3 - C
So there exists an inverse mapping - _from_ the range _to_ the domain
of the original bijective mapping.
John Savard
http://home.ecn.ab.ca/~jsavard/frhome.htm
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Sun, 3 Jun 2001 15:14:20 -0700
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] (Scott Fluhrer) wrote in
> <9fe878$r73$[EMAIL PROTECTED]>:
>
> >
> >Tom St Denis <[EMAIL PROTECTED]> wrote in message
> >news:UyuS6.17399$[EMAIL PROTECTED]...
> >>
> >> "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
> >> news:[EMAIL PROTECTED]...
> >> > Tom St Denis <[EMAIL PROTECTED]> wrote:
> >> > :[D. Scott wrote:]
> >> >
> >> > :> If you encrypt one byte with BICOM you most likely will
> >> > :> get several bytes out. However if you did get one byte
> >> > :> out the input file could be far more than one byte. This
> >> > :> is beacuse if the key is not known many many thousands of
> >> > :> different possible input files could have mapped to that
> >> > :> single one byte output file.
> >> >
> >> > : Ok bud, there is more to the world than "encryption". BICOM as I
> >> pointed
> >> > : out earlier is vastly inefficient as compared to CTR modes and as
> >> > : you
> >> have
> >> > : failed to point out not any more secure.
> >> >
> >> > He explained it - you just didn't understand the explanation.
> >>
> >> What explanation? All he does is flame me.
> >>
> >> > : Besides BICOM can't be a "bijection" if one input maps to several
> >bytes.
> >> >
> >> > Yes it can. Indeed it is.
> >> >
> >> > : Let's say a 1 byte file maps to 3 bytes.
> >> >
> >> > OK.
> >> >
> >> > : Now to be fully bijective you must map all 3 byte files to 1 byte.
> >> >
> >> > A false statement on your part - bijectivity in no way requires such
> >> > a
> >map
> >> > to exist. Want to try again?
> >>
> >> Um wrong. A bijection is where the domain and range are the same set.
> >I.e
> >> a permutation of 0..255 is a bijection. Squaring modulo a prime is
> >> not a bijection, etc.. (since not all roots have roots, etc..)
> >
> >Tom, no. A bijection is a function that is both an injection and a
> >surjection. That is, a function F is a bijection iff both of the
> >following are true:
>
> In BICOM there are 2**256 differnt F's one for each key,
Or, in other words, BICOM is a keyed set of 2**256 bijections. Not really a
crucial distinction, however, you're been stating so long that BICOM is a
bijection that I assumed it was unkeyed.
> >
> >For any i!=j, F(i)!=F(j)
>
> in BICOM i and j come from the set of 8-bit binary files.
>
> >
> >For any x, there exists an i s.t. F(i) = x
>
> likewise x and Fwhateverkey(i) are also members of the
> 8-bit binary file set.
>
> >
> >(where i, j are members of the domain of F, and x is a member of the
> >range of F)
>
> In BICOM case the domain and range are the possible 8-bit byte
> files that are in common use in most computer systems.
I suspected as much, but I'm glad to hear that confirmed.
> .
> >
> >
> >In addition, for BICOM, (I believe) that the domain and the range are,
> >in fact, identical: all possible bitstrings (limited to lengths a
> >multiple of 8? I never examined it, so I am unclear on that subtlety).
> >This is an infinite set, but that is not a problem from the above
> >definition, which never assumes finiteness.
>
> However by various matching transforms it trival to make matching
> front and backend programs to BICOM to make it bijective to the
> set of all bit srings. It is just that most people work with 8-bit
> byte files.
However, if BICOM is a keyed transformation, do you have any cryptanalytic
results (either positive or negative) on it? What security claims do you
make for it? I'm sorry if you posted them before, but I really have been
ignoring BICOM up to now.
--
poncho
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: PRP vs PRF (was Luby-Rackoff Theorems)
Date: Sun, 3 Jun 2001 15:15:20 -0700
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:SKxS6.19715$[EMAIL PROTECTED]...
> A PRF is a pseudo-random function and a PRP is a pseudo-random
permutation?
> (I'm reading the paper Wagner posted today).
>
> So basically a PRF is any type of mapping and a PRP is any injection?
I think you have the right idea (you mean bijection, not injection, and
domain and range are the same), but lets get it pedantically accurate:
A PRF is a distribution of functions generated from a particular source,
which has the following property: given a function F, which is either chosen
according to the distribution of the PRF, or a function chosen uniformly
randomly from the set of all functions with the same domain/range, it is
impossible (with some computational and query ceiling) to distinguish which
that particular F came from with probability 0.5 + \epsilon.
A PRP is exactly the same, except that we're dealing with permutations and
not functions.
Quite often, we talk about a single function being a PRF, which is
convienent, and has an intuitive meaning (the function "acts randomly" on
any input that hasn't been queried), but really doesn't have any precise
mathematical meaning -- it is analogous to the question of whether 42 is a
random number.
--
poncho
------------------------------
From: "Yashar Alishenas" <[EMAIL PROTECTED]>
Subject: Re: S-Boxes
Date: Mon, 4 Jun 2001 00:25:09 +0200
> (Hint: The sboxes are non-linear)
I've read that passage several times. Which concrete implications does the
nonlineartiy have on the security of DES, differential and linear
cryptanalysis?
/ya
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: S-Boxes
Date: Sun, 03 Jun 2001 22:34:18 GMT
"Yashar Alishenas" <[EMAIL PROTECTED]> wrote in message
news:9fecv9$m5v$[EMAIL PROTECTED]...
> > (Hint: The sboxes are non-linear)
>
> I've read that passage several times. Which concrete implications does the
> nonlineartiy have on the security of DES, differential and linear
> cryptanalysis?
The sboxes do not pass the chars nicely.
Read up Bihams papers (look up Eli Biham on yahoo) on diff and linear
analysis. If you're still stumped ask again.
Tom
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: S-Boxes
Date: Sun, 3 Jun 2001 15:22:55 -0700
Yashar Alishenas <[EMAIL PROTECTED]> wrote in message
news:9fecv9$m5v$[EMAIL PROTECTED]...
> > (Hint: The sboxes are non-linear)
>
> I've read that passage several times. Which concrete implications does the
> nonlineartiy have on the security of DES, differential and linear
> cryptanalysis?
Even bigger hint: suppose DES was totally linear. How would you break it?.
--
poncho
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: PRP vs PRF (was Luby-Rackoff Theorems)
Date: Sun, 03 Jun 2001 22:36:47 GMT
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:9fedm7$ke9$[EMAIL PROTECTED]...
>
> Tom St Denis <[EMAIL PROTECTED]> wrote in message
> news:SKxS6.19715$[EMAIL PROTECTED]...
> > A PRF is a pseudo-random function and a PRP is a pseudo-random
> permutation?
> > (I'm reading the paper Wagner posted today).
> >
> > So basically a PRF is any type of mapping and a PRP is any injection?
> I think you have the right idea (you mean bijection, not injection, and
> domain and range are the same), but lets get it pedantically accurate:
>
> A PRF is a distribution of functions generated from a particular source,
> which has the following property: given a function F, which is either
chosen
> according to the distribution of the PRF, or a function chosen uniformly
> randomly from the set of all functions with the same domain/range, it is
> impossible (with some computational and query ceiling) to distinguish
which
> that particular F came from with probability 0.5 + \epsilon.
So we say {x, y, ..., z} is a PRF if you can't tell how it was made from F?
> A PRP is exactly the same, except that we're dealing with permutations and
> not functions.
I don't get this. Isn't a PRP a function?
> Quite often, we talk about a single function being a PRF, which is
> convienent, and has an intuitive meaning (the function "acts randomly" on
> any input that hasn't been queried), but really doesn't have any precise
> mathematical meaning -- it is analogous to the question of whether 42 is a
> random number.
I will have to re-read this... thanks for the reply.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Uniciyt distance and compression for AES
Date: Sun, 03 Jun 2001 22:38:52 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> :> Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> :> : You're argument is only valid if we are trying to find randomly
> :> : compressed data streams.
> :>
> :> The conclusion holds no matter what type of data you are dealing with.
> :>
> :> If you have a compressor that succeeds in compressing your target data,
> :> then compression before encryption will increase the unicity distance
of
> :> the resulting system.
>
> : That's not true [...]
>
> Yes it is.
>
> Recall the unicity distance is how much cyphertext you need before you
> have a unique correct decrypt.
>
> Compression reduces the redundancy in the inputs to the cipher.
> Consequently you need more ciphertext to be able to identify
> whether you have a correct decrypt, because a larger proportion
> of decrypts look like plausible messages.
No it doesnt. Are you purely retarded or just ignoring my posts?
I posted earlier how I could tell a block of compressed data if it's valid
after decrypting. I don't see how that's any different then telling if the
block is english...
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: benefits of compression for security
Date: Sun, 03 Jun 2001 22:47:00 GMT
I've been giving this some thought (yes I know what a surprise...)
The biggest problem we have here in discussing this...... "is the dictionary
already built before we start?".
The implication is for example with a single pass adaptive codec that the
first 100 bytes of codec output are mostly literals. So the number of
possible messages we can cram into a block of N bytes is quite limited.
If we have 2 bpb (bits per byte) we have a compression ratio of 1:4. Which
means we can cram 4N bytes into the block. Keep in mind though that only
2^8N possible messages will fit into the block.
The difference compared to the normal plaintext mode is that out of the
possible 2^8N possible messages fewer are valid as compared to the
compressed stream.
This is where the "unicity distance" comes in.
So yes, I think it's possible if the dictionary is pre-built to increase the
# of possible messages per block as compared to plain ASCII plaintext.
But as compared to using say BZIP2 or Deflate I would say the first 100 or
so blocks are going to have the same if not lower unicity distance.
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Dynamic Transposition Revisited Again (long)
Date: 3 Jun 2001 23:03:41 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Mok-Kong Shen) wrote:
> I don't understand yet what do you mean by 'inverting half
> the bytes'? Randomly choosing one half of the bytes in the
> message and inverting all bits in these bytes while leaving
> the other half of the bytes in the message unchanged, or
> what?
Yes - so that the biased bit patterns within those inverted
bytes approximately negate the patterns in the unmodified
ones. The intention is to force the attacker to try all
2**n permutations (n=block size in bits). Having said that,
I think that a substitution cipher should be applied as well.
Keith.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: PRP vs PRF (was Luby-Rackoff Theorems)
Date: Sun, 3 Jun 2001 23:07:33 +0000 (UTC)
Scott Fluhrer wrote:
>Quite often, we talk about a single function being a PRF, which is
>convienent, and has an intuitive meaning (the function "acts randomly" on
>any input that hasn't been queried), but really doesn't have any precise
>mathematical meaning [...]
It does for me, if you use the following definition.
The function F : K x X -> Y is a (t,q,e)-secure pseudorandom function (PRF)
if, for all adversaries A using at most q queries and at most t steps of
computation, we have Adv A <= e.
Note that we often write F_k(x) as shorthand for F(k,x), and we often
write "F is a PRF" as shorthand for the claim that F is a (t,q,e)-secure
pseudorandom function for some t,q,e.
By the way, the advantage of an oracle algorithm A is defined as follows.
Let S be the set of all functions with signature X -> Y. Let R be a
random variable uniformly distributed on S. Let k be a random variable
uniformly distributed on K. Then Adv A = |Pr[A^{F_k} = 1] - Pr[A^R = 1]|.
------------------------------
** 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
******************************
