Cryptography-Digest Digest #52, Volume #14 Sat, 31 Mar 01 19:13:01 EST
Contents:
What is ideal substitution cipher? (newbie)
Re: Data dependent arcfour via sbox feedback ("Bryan Olson")
Re: Breaking a DES encrypted code. (Andreas Franz)
Earpster AES v1.0 ("James Wyatt")
Re: Question on the Quadratic Sieve ("Bruce Murray")
Re: Potential of machine translation techniques? ("Martin Quensel")
Re: conferences? (Steve Portly)
Re: AES - yet another question :-) ("Brian Gladman")
Learning to write encryption algorithms. ("m.wolfenden")
Re: Data dependent arcfour via sbox feedback (Terry Ritter)
Re: Learning to write encryption algorithms. (John Joseph Trammell)
Re: Idea - (LONG) (David Wagner)
Re: Idea - (LONG) (David Wagner)
Re: conferences? (David Wagner)
Re: simple stream cipher (hehehe) (David Wagner)
A first: Rabin's broken! (Jan Panteltje)
Re: Learning to write encryption algorithms. (Ben Cantrick)
Re: simple stream cipher (hehehe) ("Tom St Denis")
Re: Compression-encryption with a key (Tim Tyler)
Re: Compression-encryption with a key (Tim Tyler)
----------------------------------------------------------------------------
From: newbie <[EMAIL PROTECTED]>
Subject: What is ideal substitution cipher?
Date: Sat, 31 Mar 2001 13:59:45 -0400
Is ideal substitution cipher breakable?
Is there a way to build it?
Newbie
------------------------------
From: "nospam"@"nonsuch.org" ("Bryan Olson")
Subject: Re: Data dependent arcfour via sbox feedback
Date: Sat, 31 Mar 2001 19:20:06 GMT
John Savard wrote:
> Ken Savage wrote:
>>RC4 shuffles the sbox itself; the modification I've done does not
>>make the mixing any different. Thus, if rc4 doesn't violate the
>>patent, I don't see how this mod does.
>
>Well, 'data dependent' implied to me that the shuffling depended on
>the plaintext, which is exactly what distinguishes Dynamic
>Substitution from RC4.
Neither RC4 nor this proposal are Dynamic Substitution, but
that's not what distinguishes them. RC4 and the proposed
modification do not encrypt by substitution of the data
characters; that's what makes Ritter's patent inapplicable.
Furthermore, the claims in Ritter's patent are not limited to
alterations of the table that are dependent on the plaintext
data stream.
I'm not sure it's been stated, so I'll note an obvious
defect in the proposed scheme: If we grant the attacker
multiple known plaintexts from the same starting state, he
can easily discover the state.
--Bryan
------------------------------
From: [EMAIL PROTECTED] (Andreas Franz)
Subject: Re: Breaking a DES encrypted code.
Date: Sat, 31 Mar 2001 21:23:58 +0200
William Hugh Murray <[EMAIL PROTECTED]> wrote:
> In WWII the Germans used the same Enigma key for an entire day and an entire
> theatre of battle. The discovery of a key and the verification that one had
> done so was easier the value higher.
Yes, and they used their keys for things like weather information which
had a regular header... (AFAIK)
--
"Andreas Franz" <[EMAIL PROTECTED]>
PGP Fingerprint: 83A1 7AE9 A9C6 B4DE C20F 3946 9D03 F17F, ID:0xC0F0D5FD
------------------------------
From: "James Wyatt" <[EMAIL PROTECTED]>
Subject: Earpster AES v1.0
Date: Sat, 31 Mar 2001 19:32:56 GMT
Public FTP:
wyattearp.dns2go.com 2001
login/pass: crypt/crypt
filename earpster.zip
Check it out...I will post an executable if anyone is interested...
Jim
------------------------------
From: "Bruce Murray" <[EMAIL PROTECTED]>
Subject: Re: Question on the Quadratic Sieve
Date: Sat, 31 Mar 2001 20:41:35 +0100
You should read Carl Pomerance's excellent article "A Tale of Two Sieves",
available at
http://www.ams.org/notices/199612/pomerance.pdf
Bruce Murray
Southampton UK
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:kDGw6.159782$[EMAIL PROTECTED]...
> Please forgive my misunderstandings if any...
>
> If I get the QS right you are trying to find a pair X, Y in Zn (n = # to
> factor) such that X != +/- Y, and X^2 = Y^2 mod n. This is because if
this
> is true then (x - y)(x + y) = kn and then (x-y) might be a divisor of n.
>
> Then the idea progresses by trying to find numbers Xi and their roots Yi
> such that Xi^2 = Yi (mod p). My first question is how do you pick these
> numbers (Xi I mean)? Are you picking numbers that are small AND have
> residues or ?? Second question is what is p? Is that an element of the
> factor base (i.e the list of small primes chosen)? Once you find all the
> residues how do you make use of them?
>
> Then you are supposed to form a polynomial such as
>
> product from {i=0 to l} of Xi^(Ei) is equal to the product from {i=0 to l}
> Yi^(Fi) (all mod n).
>
> Several questions here (first is that even remotely right?) first I know
> that Ei and Fi must sum to 0 mod 2 (i.e even powers). But how do you pick
> Ei and Fi? As I understand it the correct pattern of Ei and Fi (or is
there
> only one bit string?) comes from gauss reducing a binary matrix? How do
you
> build this matrix?
>
> I really just want to get into the jist of things. I know I probably have
> gotten this all wrong so if you reply: be kind :-)
>
> Thanks
> --
> Tom St Denis
> ---
> http://tomstdenis.home.dhs.org
>
>
------------------------------
From: "Martin Quensel" <[EMAIL PROTECTED]>
Subject: Re: Potential of machine translation techniques?
Date: Sat, 31 Mar 2001 22:32:30 +0200
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote:
> Volker Hetzer wrote:
>> German: Das ist eine schoene Blume. English, naive: This is a nice
>> flower. Now, the context is a german looking at a glass of beer and
>> appreciating the white foam on top of the glass. This foam in a beer
>> glass is called Blume (flower). How do the english say to this? Doe
>> they have a special name for this at all?
>
> It's usually called a "head" in the US. However, "nice head" has other
> connotations, so probably a native US English speaker would phrase it
> differently.
>
> The general issue is that correct language translation requires that the
> original be *understood*, i.e. related to the real world, and the
> constructed understanding used to re-express it in the target language.
> Good human translators, e.g. of literary works, routinely do this.
I know that some companies translates their technical manuals by using
machine translation. This requires a use of "simplified" english (or
whatever language the original text is written in) an many clear rules on
sentence structure.
I belive machine translation with use of content markuplanguages (SGML,
XML) can be very effective. But the writer needs to follow very strict
rules, so it can not be used everywhere, but in fields such as technical
manuals it already works quite well.
------------------------------
From: Steve Portly <[EMAIL PROTECTED]>
Subject: Re: conferences?
Date: Sat, 31 Mar 2001 15:54:34 -0500
Paul Rubin wrote:
> "Tom St Denis" <[EMAIL PROTECTED]> writes:
> > I just finished a design for a simple cipher based on MDS matrices and a FFT
> > like network (like CS-Cipher) the idea is to make the encryption really
> > simple and use it in CTR mode. The cipher takes a 192-bit key and a 64-bit
> > block (i.e you encrypt the 64-bit counter and xor it against the msg as
> > required).
> >
> > I was wondering what conferences this type of cipher would be relevant too.
>
> Stop designing ciphers and start breaking ciphers other people have designed.
> But you knew that already.
Some of the equipment needed for breaking ciphers is pretty expensive, anybody
know where to get good quality used equipment?
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: AES - yet another question :-)
Date: Sat, 31 Mar 2001 22:09:08 +0100
"Marc" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Thank you for your patience with the test vectors, I now understand
> how to use them.
>
> I have one further question if you don't mind. I notice that the
> AES decryption (in software) tends to be slower than the encryption.
> In my particular application I prefer fast decryption and slow
> encryption. Is there any security drawback when I simply swap both
> functions? In other words I plan to _De_crypt() the plaintext to
> get ciphertext, and to _En_crypt() the ciphertext to get plaintext.
> This way I have the speed advantage where I need it, and of course
> I'm not compatible to other AES implementations anymore, but this
> aside - do the AES security evaluations still apply?
AFAIK the is no security problem in running these in reverse. However there
is only a speed penalty for decryption compared to encryption when
particular implementation techniques are employed.
Moreover, when there is such a penalty, it causes a slower key set up phase
but not a slower decryption operation once the key has been established.
Hence even in this situation decryption will only be significantly slower
than encryption when the key is changed frequently.
In overall terms, unless your application is highly key agile, I doubt that
you will notice the speed difference between encryption and decryption.
Brian Gladman
------------------------------
From: "m.wolfenden" <[EMAIL PROTECTED]>
Subject: Learning to write encryption algorithms.
Date: Sat, 31 Mar 2001 21:59:57 +0100
Hi,
I would like to learn about how to write encryption algorithms to encrypt
files. Does anyone know whether there are any online tutorials or online
books or where I should go for help.
Thanks,
Mark
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Data dependent arcfour via sbox feedback
Date: Sat, 31 Mar 2001 21:24:40 GMT
On Sat, 31 Mar 2001 19:20:06 GMT, in <G5qx6.1$FU2.105@interramp>, in
sci.crypt "nospam"@"nonsuch.org" ("Bryan Olson") wrote:
>John Savard wrote:
>> Ken Savage wrote:
>>>RC4 shuffles the sbox itself; the modification I've done does not
>>>make the mixing any different. Thus, if rc4 doesn't violate the
>>>patent, I don't see how this mod does.
>>
>>Well, 'data dependent' implied to me that the shuffling depended on
>>the plaintext, which is exactly what distinguishes Dynamic
>>Substitution from RC4.
>
>Neither RC4 nor this proposal are Dynamic Substitution, but
>that's not what distinguishes them. RC4 and the proposed
>modification do not encrypt by substitution of the data
>characters; that's what makes Ritter's patent inapplicable.
I can only discuss the issue theoretically: I can't speak to either
RC4 or the current proposal.
However, the Dynamic Substitution claims do not require encryption by
substitution. Dynamic Substitution is just a combiner. Encryption
(combining data with confusion) could be by XOR, for example, after
Dynamic Substitution produced a value by combining values from two
RNG's or other sources.
>Furthermore, the claims in Ritter's patent are not limited to
>alterations of the table that are dependent on the plaintext
>data stream.
Right.
>I'm not sure it's been stated, so I'll note an obvious
>defect in the proposed scheme: If we grant the attacker
>multiple known plaintexts from the same starting state, he
>can easily discover the state.
In general, any stream cipher must avoid re-using a previous state.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (John Joseph Trammell)
Subject: Re: Learning to write encryption algorithms.
Date: Sat, 31 Mar 2001 21:57:10 GMT
On Sat, 31 Mar 2001 21:59:57 +0100, m.wolfenden <[EMAIL PROTECTED]> wrote:
> I would like to learn about how to write encryption algorithms to encrypt
> files. Does anyone know whether there are any online tutorials or online
> books or where I should go for help.
A great place to start would be the sci.crypt.research FAQ,
which is available at e.g.
ftp://rtfm.mit.edu/pub/usenet-by-hierarchy/sci/crypt/
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Idea - (LONG)
Date: 31 Mar 2001 22:15:25 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Paul Crowley wrote:
>[EMAIL PROTECTED] (David Wagner) writes:
>> By the way, as a curiousity: If you have any such block
>> cipher, each key can be broken with 2^{n/2} work (after
>> a precomputation of 2^n steps). It is a fun puzzle to
>> see why.
>
>Can you specify the puzzle more precisely? If I can choose the
>plaintext block, I can break any block cipher with an n-bit key
>instantly, so long as I can have 2^n precomuptation and 2^n storage
>:-)
Yes, sorry. The challenge is to do it without 2^n storage,
but rather with something like 2^{n/2} storage.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Idea - (LONG)
Date: 31 Mar 2001 22:16:39 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Rob Warnock wrote:
>Is there some way to quantify the added "work" for each primitive
>operation [...]?
If there were, we could probably show P != NP.
This suggests that developing such a formal discipline of cipher
design is unlikely to be easy.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: conferences?
Date: 31 Mar 2001 22:17:45 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Scott Fluhrer wrote:
>But, if we all just sat around and broke ciphers, who'd be designing the
>ciphers for us to break? :-)
Ahh, if only that were a problem... :-)
>But, seriously, it *is* much easier to get a cryptanalytic result published
>than it is to get a new cipher published.
If so, it is for good reason, IMHO.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: simple stream cipher (hehehe)
Date: 31 Mar 2001 22:28:06 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Tom St Denis wrote:
>To generate a byte of output do this
>
>1. Clock the LFSR once (e.g new bit). Forget the output of the LFSR since
>it's actually the state of the LFSR we care about.
>
>2. Divide the LFSR into an array of bytes (starting with the lsb of LFSR I
>used the lfsr in galois mode for speed...)
>3. r <= 0
>4. for i = 0 to len_lfsr/8 do
>4.1 r <= sbox[LFSR[i] xor r]
>5. Output r
It's got a potentially-bad property:
(*) If LFSR[0] = sbox^-1[0], then LFSR'[7] = sbox^-1[Z'] xor Z.
where Z,Z' denote two keystream bytes separated by 8 positions,
and where LFSR,LFSR' denote the corresponding contents of the
shift register at those positions. I'm concerned that it may be
possible to use this property to build an attack.
Here's the proof. Note that LFSR[i] = LFSR'[i-1] for i=1,..,7.
Thus, if sbox[LFSR[0]] = 0, then Z' = sbox[LFSR'[7] xor Z]. The
property (*) follows.
------------------------------
From: [EMAIL PROTECTED] (Jan Panteltje)
Subject: A first: Rabin's broken!
Date: Sat, 31 Mar 2001 22:29:04 GMT
Actually it is an April first
------------------------------
From: [EMAIL PROTECTED] (Ben Cantrick)
Subject: Re: Learning to write encryption algorithms.
Date: 31 Mar 2001 15:44:14 -0700
In article <lyrx6.8776$[EMAIL PROTECTED]>,
m.wolfenden <[EMAIL PROTECTED]> wrote:
>I would like to learn about how to write encryption algorithms to encrypt
>files. Does anyone know whether there are any online tutorials or online
>books or where I should go for help.
I would suggest Bruce Schnieir's excellent book "Applied Crypto."
You should be able to get it at just about any good bookstore. Source
code, descriptions of algorithms, good beginner-level explanations
of crypto principles. This is the book for a computer-savvy novice.
-Ben
--
Ben Cantrick ([EMAIL PROTECTED]) | Yes, the AnimEigo BGC dubs still suck.
BGC Nukem: http://www.dim.com/~mackys/bgcnukem.html
The Spamdogs: http://www.dim.com/~mackys/spamdogs
"The guitar is an instrument of the Middle Ages." -Ralf Hutter of Kraftwerk
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: simple stream cipher (hehehe)
Date: Sat, 31 Mar 2001 22:54:28 GMT
"David Wagner" <[EMAIL PROTECTED]> wrote in message
news:9a5llm$82q$[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >To generate a byte of output do this
> >
> >1. Clock the LFSR once (e.g new bit). Forget the output of the LFSR
since
> >it's actually the state of the LFSR we care about.
> >
> >2. Divide the LFSR into an array of bytes (starting with the lsb of LFSR
I
> >used the lfsr in galois mode for speed...)
> >3. r <= 0
> >4. for i = 0 to len_lfsr/8 do
> >4.1 r <= sbox[LFSR[i] xor r]
> >5. Output r
>
> It's got a potentially-bad property:
> (*) If LFSR[0] = sbox^-1[0], then LFSR'[7] = sbox^-1[Z'] xor Z.
> where Z,Z' denote two keystream bytes separated by 8 positions,
> and where LFSR,LFSR' denote the corresponding contents of the
> shift register at those positions. I'm concerned that it may be
> possible to use this property to build an attack.
Note that I don't clock the LFSR 8 times, only once. So they will be
separated by 64 positions not 8... but that doesn't affect the char.
if LFSR[0] = sbox^-1[0]? I don't follow. You mean if the output of the
first round is zero the input to the second round is zero? Well yeah that
happens with exact probability of 1/256 (note that LFSR[0] goes thru all
possible 256 states).
>
> Here's the proof. Note that LFSR[i] = LFSR'[i-1] for i=1,..,7.
> Thus, if sbox[LFSR[0]] = 0, then Z' = sbox[LFSR'[7] xor Z]. The
> property (*) follows.
Hmm I don't follow. Why would all the bytes of the LFSR be equal? Wouldn't
that happen for such a small fraction of all possible states?
Sorry, I know I'm a bit of a retard when it comes to serious math+attacks
but please indulge me.
Tom
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Compression-encryption with a key
Reply-To: [EMAIL PROTECTED]
Date: Sat, 31 Mar 2001 23:10:46 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
: Here is another way of putting the matter. *If* some given
: general symmetric-key system (known to the attacker) is used
: to encrypt a plaintext that is M bits long, using a key that
: is K bits long, and K << M (standard notation for "is much
: smaller than"), if the source of the plaintext has a reasonable
: amount of redundancy (such as is true of any natural-language
: text), if the general system is capable of encrypting arbitrary
: M-bit patterns, and if the attacker has unlimited computing
: resources, then in principle all 2^K possible key values can be
: used for trial decryptions. Of the 2^K recovered plaintexts,
: the vast majority *must* be garbage, meaning not generatable
: from the assumed plaintext source, and that property should be
: readily testable. (Any compression etc. is factored into the
: general system.)
This appears to be false.
: Sketch of proof: If only 2^K plaintexts were reasonable under the
: source model, the source would have vastly more redundancy than
: assumed. (2^K <<< 2^M.)
OK...
: So, to prevent checking for reasonableness of
: recovered plaintext, some of the assumptions must be made invalid.
It's not clear why.
I believe you may be implicitly assuming the decompressed decrypted files
are approximately 2^M in length. This need not be true - and when it is
*not* true, your counting argument doesn't appear to apply.
Looking at it another way, just because the program can process arbitrary
M-bit patterns, it doesn't mean that the space of decompressed
possible decrpyts of a given length contains much garbage (that can be
easily used to reject keys).
--
__________
|im |yler Try my latest game - it rockz - http://rockz.co.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Compression-encryption with a key
Reply-To: [EMAIL PROTECTED]
Date: Sat, 31 Mar 2001 23:15:10 GMT
Paul Crowley <[EMAIL PROTECTED]> wrote:
: Ross Younger <[EMAIL PROTECTED]> writes:
:> It is generally a Good Idea to compress your plaintext before
:> encrypting -- this normally reduces the amount of ciphertext for an
:> attacker to play with and reduces redundancy within (one could call
:> this obfuscating the plaintext, I suppose).
: Flogging a dead horse here, but:
: There's no security reason to compress before encryption.
A decidedly dodgy statement. What can your grounds for making it be?
: If you can't trust your cipher against a known-plaintext (or
: chosen-plaintext) attack, use another cipher.
Weaknesses in ones cypher are emphatically *not* the only context in
which the advantages of compression might make themselves felt.
Besides, how do you know if you can trust your cipher?
--
__________
|im |yler Can you escape the Rockz? - http://rockz.co.uk/
------------------------------
** 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
******************************
