Cryptography-Digest Digest #364, Volume #14 Wed, 16 May 01 08:13:01 EDT
Contents:
Newbie Question: Crytography - Unlimited Inputs/Outputs? ("news.singnet.com.sg")
Re: Evidence Eliminator propaganda (Anonymous)
Re: Evidence Eliminator works great. Beware anybody who claims it doesn't work
(propaganda) ("Sam Simpson")
Re: ON-topic - UK crime statistics (was Re: Best, Strongest Algorithm) (Tim Tyler)
Re: What Is the Quality of Randomness? (Tim Tyler)
Re: What Is the Quality of Randomness? (Tim Tyler)
Re: ON-topic - UK crime statistics (was Re: Best, Strongest Algorithm) ("Sam
Simpson")
Re: enumerating permutations (G Winstanley)
Re: Avoiding RSA padding altogether? ("Jakob Jonsson")
Re: information theoretic stream cipher ("Tom St Denis")
Re: best algo ("Tom St Denis")
Karnaugh Maps ("Tom St Denis")
Re: Karnaugh Maps (Xcott Craver)
Re: What Is the Quality of Randomness? (Mok-Kong Shen)
Re: Quadibloc IX described on web site! (John Savard)
Re: Newbie Question: Crytography - Unlimited Inputs/Outputs? (John Savard)
----------------------------------------------------------------------------
From: "news.singnet.com.sg" <[EMAIL PROTECTED]>
Subject: Newbie Question: Crytography - Unlimited Inputs/Outputs?
Date: Wed, 16 May 2001 15:19:31 +0800
BlankHi, I am just getting into the world of cryptography and would like to
ask a question. If it is too commonly known then please direct me to a
website link/other resource.
I read/heard somewhere that given an encryption system where the tester is
allowed an unlimited number of inputs and outputs, that the system itself
will always be possible to break. Is this true?
E.g. If someone were to allow me the following inputs, outputs:
A : C
B: D
Then it would be possible, given enough time, to deduce that the system
adds 2 as an integer to the plaintext to produce the output (e.g. A + '2' =
C, B + '2' = D).
However if we add in mathematical formulae, XORs, MODs etc this would get
pretty complicated and I'd like to see such an analysis in action. A friend
recently gave me an example (not sure where he got the data from though):
a: YSmzWf2llvIiI
aa: Zj3aNphJEGxJc
aaa: uhKTXUgGTemE6
1: Lf6/GciWiIxSc
2: rvGGJiT/qIfsA
Of course I'm not going to mention that as a joke he offered to give me $100
if I could break it but I don't think so 8). However to be serious, I am
still interested in the theory and approach of this interesting concept.
Thanks in advance!
Carol Mu
------------------------------
Date: Wed, 16 May 2001 09:26:02 +0200
From: Anonymous <[EMAIL PROTECTED]>
Subject: Re: Evidence Eliminator propaganda
Crossposted-To:
alt.privacy,alt.security.pgp,alt.security.scramdisk,alt.privacy.anon-server
in <[EMAIL PROTECTED]> Beretta
[EMAIL PROTECTED] wrote:
> On Tue, 15 May 2001 22:33:36 +0100, in alt.security.pgp you wrote:
>
> >By now you will have witnessed the mass hysteria about Evidence Eliminator.
> <snip>
>
> V3.1 - Name: Snacker Serial: 1234567890-000084E21262
> V3.1 - Name: Snacker\MiSSiON Serial: 1234567890-0001EDC79005
> V4.0 - Name: Snacker\MiSSiON Serial: 1234567890-0001EDC79005
> V4.5 - Name: Hazard , Serial: Hazard-000063515895
> V5.0 - Code: EE10-44100004D012 (also allows upgrades)
>
> You fags keep spamming, and I keep posting serial numbers to your software
Excellent move.
More serials, please.
More serials, please.
More serials, please.
More serials, please.
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Crossposted-To:
alt.privacy,alt.security.pgp,alt.security.scramdisk,alt.privacy.anon-server
Subject: Re: Evidence Eliminator works great. Beware anybody who claims it doesn't
work (propaganda)
Date: Wed, 16 May 2001 08:54:03 +0100
*LOL* - good work Beretta....
--
Regards,
Sam
http://www.scramdisk.clara.net/
Beretta <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Tue, 15 May 2001 22:33:36 +0100, in alt.security.pgp you wrote:
>
> >
> >By now you will have witnessed the mass hysteria about Evidence
Eliminator.
> <snip>
>
> V3.1 - Name: Snacker Serial: 1234567890-000084E21262
> V3.1 - Name: Snacker\MiSSiON Serial: 1234567890-0001EDC79005
> V4.0 - Name: Snacker\MiSSiON Serial: 1234567890-0001EDC79005
> V4.5 - Name: Hazard , Serial: Hazard-000063515895
> V5.0 - Code: EE10-44100004D012 (also allows upgrades)
>
>
> You fags keep spamming, and I keep posting serial numbers to your software
>
>
> PGP Key: 0x194DF369
> Fingerprint: B777 DB2A FB11 55FA 509D CE63 F3DE D665 194D F369
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: ON-topic - UK crime statistics (was Re: Best, Strongest Algorithm)
Reply-To: [EMAIL PROTECTED]
Date: Wed, 16 May 2001 08:17:15 GMT
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
: No wonder violent crime is up in the UK you can't shoot
: the bastards that break into you own house. [...]
I believe shooting someone for breaking and entering would
itself be regarded as a violent crime in the UK.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: What Is the Quality of Randomness?
Reply-To: [EMAIL PROTECTED]
Date: Wed, 16 May 2001 08:21:53 GMT
David Hopwood <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
:> : There is no such thing as a random sequence, only a random source.
:>
:> Well, "random sequence" is a meaningul term - provided one uses the
:> notion of randomness that derives from Chaitin and Kolmogorov, rather
:> than from Shannon.
: The usual term is "[Chaitin-]Kolmogorov complexity", which as the name
: implies is a measure of complexity, not randomness or entropy [...]
Well, Chaitin himself uses this as a /definition/ of his own sort
of randomness. See, for example, the quote I provided from
http://www.cs.unm.edu/~sto/files/chaitin.html
: In cryptography we normally need to assess the strength of generators,
: not particular strings, so Shannon entropy is the appropriate concept
: to use.
Oh yes - definitely. I was simply saying that "random" was not
/necessarily/ a meaningless term when a particular string is involved.
--
__________ http://rockz.co.uk/ http://alife.co.uk/ http://hex.org.uk/
|im |yler http://atoms.org.uk/ http://mandala.co.uk/ [EMAIL PROTECTED]
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: What Is the Quality of Randomness?
Reply-To: [EMAIL PROTECTED]
Date: Wed, 16 May 2001 08:29:31 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> According to the Chaitin/Kolmogorov ideas, randomness would be defined
:> with respect to a formal descriptive language. Random strings would be
:> those that are incompressible with respect to that language, and more
:> ordered strings would be compressible.
: Doesn't the 'a' in 'a formal ...' imply the existence of others? [...]
Yes, it does.
: I mean couldn't different such descriptive languages lead to quite
: different evaluations [...] of the same set of strings that are given?
Yes, that's right. Kolmogorov randomness and complexity are only defined
with respect to a specified descriptive language.
What /seems/ random from the perspective of FORTRAN-77 might have a very
compact representation in some other language.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: ON-topic - UK crime statistics (was Re: Best, Strongest Algorithm)
Date: Wed, 16 May 2001 09:30:20 +0100
You'd be right: http://news.bbc.co.uk/hi/english/uk/newsid_717000/717511.stm
--
Regards,
Sam
http://www.scramdisk.clara.net/
Tim Tyler <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
>
> : No wonder violent crime is up in the UK you can't shoot
> : the bastards that break into you own house. [...]
>
> I believe shooting someone for breaking and entering would
> itself be regarded as a violent crime in the UK.
> --
> __________
> |im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: G Winstanley <[EMAIL PROTECTED]>
Subject: Re: enumerating permutations
Date: Wed, 16 May 2001 10:20:16 +0100
Reply-To: [EMAIL PROTECTED]
On Thu, 10 May 2001 08:59:06 GMT, the cup of Tim Tyler <[EMAIL PROTECTED]>
overfloweth with the following:
> Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> : I got bored in my College "Technical Math" class so I think I came up with a
> : way to enumerate permutations [...]
>
> The conventional way to number permutations is to put them into
> lexicographic order. There's and existing algorithm to iteratively
> generate permutations in this order.
>
> The algorithm is described in: E. W. Dijkstra, A Discipline of
> Programming, Prentice-Hall, 1976, p.71.
>
> There's an implementation with source code in an applet on one of my pages:
>
> http://mandala.co.uk/permutations/
Also the often-used Fischer-Krause algorithm.
Stan
------------------------------
From: "Jakob Jonsson" <[EMAIL PROTECTED]>
Subject: Re: Avoiding RSA padding altogether?
Date: Wed, 16 May 2001 11:26:15 +0200
> Thanks for these kind words! Does anyone happen to know if NFDH has
> been written up with an exact security proof anywhere? If not, would
> it be worth me doing it?
IMHO, it would certainly be worthwhile. I haven't seen any such proof, but I
cannot tell for sure. Coron or Bellare/Rogaway would certainly know the
answer.
Jakob
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: information theoretic stream cipher
Date: Wed, 16 May 2001 09:29:11 GMT
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >
> > Ok no secret primes here :-)
> >
> > Pick a public prime (say >2^128) you then divide the message into
> > blocks M_1, M_2, such that 0 < M_i < p, eg they are all units wrt to
> > Z*p.
>
> Why use Z*p, rather than GF(2^128)? Using a polynomial will eliminate
> expansion, and would be faster in hardware.
>
> >
> > The cipher has two variables in it's state A and B both of which are
> > the same magnitude as the prime. (say 128-bits). Both belong to Z*p
> > as well.
>
> > To encode a block you perform
> >
> > 1. C_i = M_i * A + B mod p
> > 2. Update A
> > 3. Update B
> > 4. If A is zero goto 2
> >
> > Let's suppose the update in #2 and #3 is perfect, then to break this
> > you have to either determine A or B from random. Since this is
> > pair-wise decorrelated it's hard to tell. You know one impossible
> > value of B, e.g. B = -C_i since the first part cannot be zero. Other
> > than that I dunno.
>
> Hmm? If A is evenly distributed in the range 0 < A < p, and M_i is
> evenly distributed in the range, 0 <= M_i < p, then we can conclude that
> M_i*A (mod p) is also evenly distributed in the range 0 <= M_i < p.
>
> Since M_i*A can be anything, how can we conclude that the first part
> cannot be zero?
We know that the product cannot be zero, so given MA + B, we know that the
'B' value that leads MA=0 is invalid.
> Unless of course you are talking about restricting M_i to being values
> greater than zero... This wouldn't work great with GF(2^128), but might
> work ok with Z*p, since you can simply replace the zero value with some
> special number between 2^128 and p-1 (inclusive).
>
> > As for #2 and #3 what would be required. Off the top of my head I am
> > thinking of a simple LCG. This is vulnerable to a divide and conquer
> > attack though wher you guess either A and B and see if it holds (i.e
> > the update rules make sense). If A and B are 128-bits each this
> > shouldn't be a problem.
>
> If you use an LCG for A, then you don't need step 4, since A will never
> be 0. Note that for GF(2^128), you would likely want an LFSR, not an
> LCG.
>
> > Another problem is how to encode zero blocks. I would say that if you
> > have p>2^128 you could simply encode them as 128-bit blocks and do the
> > transform C_i = (M_i + 1) * A + B mod p. This would chop off a whole
> > bunch of values of A and B since we know M_i is <= 2^128 but I doubt
> > it would be enough to tell em from random.
>
> In Z*p, you can simply replace any 0-valued M_i with a constant greater
> than the max allowed M_i, but less than p. For example, you could use
> either 2^128, or p-1, or something chosen randomly.
>
> > Yet another final problem is that the ciphertext would be a bit longer
> > than the plaintext. In this case it would be a single bit larger
> > which really shouldn't cause a problem.
>
> If you change to GF(2^128), then the expansion disappears. Of course,
> you then have a problem of getting a value to replace zero; you'll just
> have to deal with the fact that M_i=0 will reveal the B stream.
Another solution is to work in GF(2^129) and just fix the lsb to be zero.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: best algo
Date: Wed, 16 May 2001 09:32:00 GMT
"Gary Silverman" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Tom St Denis wrote:
>
> > "Nils Johansson" <[EMAIL PROTECTED]> wrote in message
> > news:9dpdb8$j0gbf$[EMAIL PROTECTED]...
> > > cant deffie-hellman be used to distribute the key
> > >
> > > I need something more secure, because anyone might be listening, and
catch
> > > the key. I dont want to involve a third part either...
> >
> > Well typically (i.e. in theory) DH is very secure. It's completely
> > vulnerable to mitm attacks though...
>
> Is it vulnerable to mitm attack even if the two participants already know
the
> "public data" necessary to form the session key? I'm relatively new to
this, so
> I want to make sure I understand what the vulnerability really is. I've
read
> that the public data could be a simple as using another entity's public
> certificate. If I know the certificate I'm inspecting is authentic - is
DH
> secure?
99.9999999% of the time if you make a random connection with Mr.X over the
net there is no mitm. But the problem is you cannot be sure and you cannot
prevent it.
With public keys posted on websites it may be a bit harder. But it's not
hard for me to put a key on the PGP keyring in your name...
> Or, is the point that typically I _don't_ know that the certificate I'm
> inspecting is really from the party I wish to establish a secure
connection
> with, because after I request the certificate, "mitm" will replace the
> "authentic" one with his own. Is this why it's insecure?
Well the average user will not have a Verisign certificate etc... they will
simply have a PGP key lying on their website and possibly the PGP key ring.
MITM is possible there as well as just faking your identity.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Karnaugh Maps
Date: Wed, 16 May 2001 10:22:42 GMT
Ok here is my first attemp to optimizing a boolean decomposition . This is
the lsb of the TC15 sbox..
dc ba 00 01 10 11
=========================================
00| 1 0 0 1
01| 0 1 1 0
10| 0 1 1 0
11| 0 1 1 0
y = ~(abcd) | (~cd)ab | bcd | acd
y = ~(cd)(~(ab) | ab) | bcd | acd
y = ~(cd) | bcd | acd
I have the bits backwards i.e ba instead of ab since my program outputs them
that way.
Can I optimize the last y statement any further? ( | means or, ~ means
not)
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
Subject: Re: Karnaugh Maps
From: [EMAIL PROTECTED] (Xcott Craver)
Date: Wed, 16 May 2001 11:08:57 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
>Ok here is my first attemp to optimizing a boolean decomposition . This is
>the lsb of the TC15 sbox..
>
>dc ba 00 01 10 11
>-----------------------------------------
>00| 1 0 0 1
>01| 0 1 1 0
>10| 0 1 1 0
>11| 0 1 1 0
Hi,
For k-maps, it's best to put the variables in Gray code order:
>dc ba 00 01 11 10
>-----------------------------------------
>00| 1 0 1 0
>01| 0 1 0 1
>11| 0 1 0 1
>10| 0 1 0 1
This causes simple regions on the map to correspond to
simple expressions. The middle square of 4 bits, for example,
are the outputs for which ac==1.
Are you allowed to use XORs as a primitive? Because this is
very XOR-friendly: the expression is (a^b)^(~(d|c)).
Also:
>y = ~(abcd) | (~cd)ab | bcd | acd
Oops! This expression is true for any values of a,b,c and d.
~(abcd) is only false when a=b=c=d=1, in which case bcd==1.
An expression using only and-or-not would be:
CD(ab|AB) | (c|d)(aB|Ab)
(here capitals indicate NOTs.)
-S
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: What Is the Quality of Randomness?
Date: Wed, 16 May 2001 13:50:45 +0200
Tim Tyler wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> : I mean couldn't different such descriptive languages lead to quite
> : different evaluations [...] of the same set of strings that are given?
>
> Yes, that's right. Kolmogorov randomness and complexity are only defined
> with respect to a specified descriptive language.
>
> What /seems/ random from the perspective of FORTRAN-77 might have a very
> compact representation in some other language.
So with a number of languages one gets a corresponding
number of measures of 'randomdomness' and 'complexity'
without possiblility of conversion. Would these results
be very useful/sensible? (Consider the analogous
hypothetical case where one has different measuring stabs
that give different length-values but one has no idea of
how to convert from one scale to the other!)
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Quadibloc IX described on web site!
Date: Wed, 16 May 2001 12:03:12 GMT
On Wed, 16 May 2001 04:33:49 GMT, [EMAIL PROTECTED]
(John Savard) wrote, in part:
>In addition to putting a splash of color on the page, I have modified
>the specification: the order in which the four intermediate results
>from the encipherment of the left half are assembled into two blocks
>to be enciphered has been changed. This change has been made to
>improve the diffusion properties of the cipher.
This modification created an asymmetry in the cipher between
enciphering and deciphering. Thus, a further change was required to
reduce this asymmetry. (The alternative would be to double the number
of rounds in the cipher, and have both a type A round and a type B
round.)
This further modification is to use the 32-bit subblocks produced from
the four intermediate results as subkeys in the encipherment of two
subkeys used to encipher the right half of the block in a different
order.
John Savard
http://home.ecn.ab.ca/~jsavard/frhome.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Newbie Question: Crytography - Unlimited Inputs/Outputs?
Date: Wed, 16 May 2001 12:06:15 GMT
On Wed, 16 May 2001 15:19:31 +0800, "news.singnet.com.sg"
<[EMAIL PROTECTED]> wrote, in part:
>I read/heard somewhere that given an encryption system where the tester is
>allowed an unlimited number of inputs and outputs, that the system itself
>will always be possible to break. Is this true?
Yes, if the key remains constant, one would think so: the tester would
eventually get around to inputting, by accident, the same input as the
original message, thus getting the corresponding ciphertext.
In some encryption systems, though, in addition to the key, a random
variable is generated by the encryption system and sent with the
message to ensure no two messages will be enciphered the same way.
But if the tester is allowed to choose an _unlimited_ number of
inputs, and see the output, obviously he can repeat the original
message as often as necessary until the random variable happens to be
the same as its original value by accident.
John Savard
http://home.ecn.ab.ca/~jsavard/frhome.htm
------------------------------
** 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
******************************
