Cryptography-Digest Digest #560

[Digestifier]

Cryptography-Digest Digest #560, Volume #11  Sun, 16 Apr 00 21:13:01 EDT

Contents:
  Re: Why is this algorithm insecure? (Newbie flamefodder) (stanislav shalunov)
  Re: GOST idea (Tom St Denis)
  Re: Why encrypt email... (Jerry Park)
  Re: Encrypt the signature? ("Scott Fluhrer")
  Re: One Time Pads Redux ("Joseph Ashwood")
  Re: Why is this algorithm insecure? (Newbie flamefodder) (NFN NMI L.)
  Re: Why is this algorithm insecure? (Newbie flamefodder) (David Hopwood)
  Re: Observer 16/4/2000: "Jack Straw wants the keys to your office. Don't let him in 
..." ("PJS")
  Re: Why encrypt email... ("Joseph Ashwood")
  Re: new Echelon article ([EMAIL PROTECTED])
  Re: Encode Book? (greenjh)
  Re: One Time Pads Redux ("Trevor L. Jackson, III")
  Re: My STRONG data encryption algorithm ("Trevor L. Jackson, III")
  Re: My STRONG data encryption algorithm (Tom St Denis)
  Re: Why is this algorithm insecure? (Newbie flamefodder) ("Trevor L. Jackson, III")
  Re: Why encrypt email... (Guy Macon)



Subject: Re: Why is this algorithm insecure? (Newbie flamefodder)
From: stanislav shalunov <[EMAIL PROTECTED]>
Date: Sun, 16 Apr 2000 22:38:12 GMT

Richard Heathfield <[EMAIL PROTECTED]> writes:

> > or make  Alice send some chosen plaintext).
> Skulduggery? Surely not! :-)

Many protocols would echo whatever Bob sends (or pieces of it).
Mallory could pretent to be Bob in the end of the transaction and
decrypt everything that happened before.

> That's worrying. I'll try to crack it on that basis to see if you're
> correct.

If I understood your description correctly, if you encrypt two
messages of the same length with the same key, XOR or the two
ciphertexts is the same as XOR of plaintexts.  That reveals way too
much information about plaintexts.

> > The task of brute-forcing 2^128 different keys is out of reach for any
> > known adversary.
> But wasn't it done recently?

No.  If I am not mistaken, the largest publicly known brute-force
attacks are against 56-bit keys.  It's probably true that 64-bit keys
can be brute-forced today by well-equipped adversaries (governments of
large countries or many co-operating users on the Internet).

But 2^128 is well out of reach by today's standards.  Computing based
on new physical principles would be required to brute-force that.

You might be confusing this with something like RSA-512 challenge.
RSA isn't a symmetric cryptosystem.

> Is it worth persevering with this algorithm, but adding partial
> rotations and partial XORing, as another poster suggested?

For fun and to learn--sure.  But even for fun you could try different
(more traditional) designs, such as a block cipher based on Feistel
networks.  It'll usually be faster, won't require loading of the
complete plaintext into memory, and will possibly be more secure.

Feistel networks are described in _Applied Cryptography_ by Bruce
Schneier, 2nd edition (a must-have first book for anyone plaining with
inventing or implementing cryptosystems).  They've been described in
this newsgroup before numerous times.

-- 
stanislav shalunov  | Speaking only for myself.
My address in From: is correct; if yours isn't, I don't want to hear from you.
Try to reply in newsgroup.  I don't need courtesy copies.

--

From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: GOST idea
Date: Sun, 16 Apr 2000 22:39:34 GMT



Tom St Denis wrote:
> 
> Mok-Kong Shen wrote:
> >
> > Tom St Denis wrote:
> > >
> >
> > > Well my idea cannot technically be any worse then before since F(x) 2x^2
> > > + x is a permutation in GF(2^w).  Another balanced approach would be
> > > todo this
> >
> > Could you explain why a permutation doesn't affect the avalanche?
> > Thanks.
> 
> No the permutation cannot hinder the avalanche.  It in fact increases
> the avalanche.

That's too vague, sorry.  It can't hinder it in this case since the S
function is simply a permutation itself.  And since the quadratic
used is a permutation it has no bias towards any particular value.  It's
like doing

F(x) = S(x + c), For any constant 'c'.  You are just changing the order
of the outputs, not the properties of S() itself.

Tom

--

From: Jerry Park <[EMAIL PROTECTED]>
Subject: Re: Why encrypt email...
Date: Sun, 16 Apr 2000 17:48:33 -0500

David Crick wrote:

> [EMAIL PROTECTED] wrote:
> >
> > Hi, I am doing a paper on email encryption and I have two theories:
> >
> > 1) The level of encryption depends on the information being encrypted.
>
> Only in military and government systems.
>
> > Much email is non-sensitive info so encryption is not used.
>
> There is no reason why you should not encrypt everything.
> (The speed issue with modern hardware and ciphers no longer
> is an issue. There are also enough free and tested algorithms
> so that patent issues, etc. are not an issue.)
>
> > At other times, like for medical records, em

Cryptography-Digest Digest #559

[Digestifier]

Cryptography-Digest Digest #559, Volume #11  Sun, 16 Apr 00 18:13:01 EDT

Contents:
  Re: ? Backdoor in Microsoft web server ? [correction] (Roger)
  Re: GOST idea (Tom St Denis)
  Re: Open Public Key (Tom St Denis)
  Re: Why is this algorithm insecure? (Newbie flamefodder) (Richard Heathfield)
  Re: Observer 16/4/2000: "Jack Straw wants the keys to your office. Don't let him in 
..." (JimD)
  Re: One Time Pads Redux (JimD)
  Re: Why is this algorithm insecure? (Newbie flamefodder) (Richard Heathfield)
  Re: Why is this algorithm insecure? (Newbie flamefodder) (Tom St Denis)
  Re: Q: Entropy (Diet NSA)
  Re: Why encrypt email... (David Crick)
  Re: Why is this algorithm insecure? (Newbie flamefodder) (Richard Heathfield)
  Re: Q: NTRU's encryption algorithm (Diet NSA)
  Re: ? Backdoor in Microsoft web server ? [correction] (Jim Gillogly)
  Re: Why is this algorithm insecure? (Newbie flamefodder) (Tom St Denis)
  asymmetrical systems ("rewted")
  Re: asymmetrical systems (Bill Unruh)
  Re: ? Backdoor in Microsoft web server ? [correction] (Mok-Kong Shen)
  Re: GOST idea (Mok-Kong Shen)
  Help with Exponentiation Cipher ("Monkey Boy")
  Re: Q: Entropy (Bryan Olson)
  Re: My STRONG data encryption algorithm (Nobody Home)
  Re: asymmetrical systems (Tom St Denis)
  Re: My STRONG data encryption algorithm (Tom St Denis)
  Re: GOST idea (Tom St Denis)
  Re: Why is this algorithm insecure? (Newbie flamefodder) (Boris Kazak)



From: Roger <[EMAIL PROTECTED]>
Subject: Re: ? Backdoor in Microsoft web server ? [correction]
Date: Sun, 16 Apr 2000 12:38:32 -0700

Jim Gillogly wrote:
> Regardless of precisely which magical powers the back door gives,
> it  a back door put into offical Microsoft code by official
> Microsoft (weenie) engineers.

And presumably MS will use source code control logs to find
the guilty party, and fire him.

No doubt this incident will be used to support the thesis
that open source software is the only way to get security.

--

From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: GOST idea
Date: Sun, 16 Apr 2000 19:41:27 GMT



Mok-Kong Shen wrote:
> 
> Tom St Denis wrote:
> >
> > I like the simplicity of gost... hmm Let's change the F function to be
> >
> > F(x) = S(2x^2 + x) <<< 11
> >
> > Where S is the parallel application of the eight 4x4 sboxes.  This would
> > have much higher avalanche and only make the F function slightly more
> > complex.
> 
> I suppose one should be careful and do sufficient amount of
> experiments to verify the avalanche properties, unless one
> has a theoretical proof.

Well my idea cannot technically be any worse then before since F(x) 2x^2
+ x is a permutation in GF(2^w).  Another balanced approach would be
todo this

F(x) = S(S(x) <<< 11) <<< 11

Which should increase the avalanche significantly and keep the algorithm
complexity about the same, just twice as slow in the F function.  

Another good point of GOST is the ram requirement, all you need is the
32 bytes of round keys, and 256 bytes for the sbox [or 1kb if you
pre-expand the sbox values].  

Tom

--

From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Open Public Key
Date: Sun, 16 Apr 2000 19:45:15 GMT



Mark Wooding wrote:

> > > You're still mixing up safe and strong primes.
> > >
> > > If you have a safe prime p = 2q + 1, then 4 is a generator of the
> > > order-q subgroup (exercise: prove this).  This is probably a good choice
> > > of generator for Diffie-Hellman and ElGamal-like systems.
> >
> > From what I can tell if p = 2q + 1, then p mod 4 = 3 'hmm duh', then we
> > get 4^q mod p = 1 and 4^2 mod p != 1.
> 
> In more detail, 4^q = 2^{2q} = 1 (mod p), but yes.

Ouch I should have gotten that.  Well I just picked up a book called
"Fundamentals of Number Theory"  it deals alot with the type of math you
would see in cryptography (quadratic residues, euclids algorithms,
etc...)

So now I can "get a clue" :).  Can't wait to get reading the book.

Tom

--

Date: Sun, 16 Apr 2000 20:51:50 +0100
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Why is this algorithm insecure? (Newbie flamefodder)

stanislav shalunov wrote:
> 
> Richard Heathfield <[EMAIL PROTECTED]> writes:
> 
> > Thank you. I'm not sure, however, that I have understood you correctly.
> > You seem to be saying that Eve can decrypt any message she likes,
> > provided she has first done a chosen plaintext attack on a message that
> > length and using the same key as Alice. Okay, yes, that's a problem. But
> > how would she do such an attack?
> 
> I was a bit careless: known plaintext is enough.

Ah. That makes a lot more sense. For example, a known protocol exchange
in a TCP/IP conversation.

> 
> What I have meant is that if Alice sends to Bob a stream of messages
> of the same length encrypted with the same key (e.g., network
> packets), and if Eve knows plaintext 

Cryptography-Digest Digest #558

[Digestifier]

Cryptography-Digest Digest #558, Volume #11  Sun, 16 Apr 00 15:13:01 EDT

Contents:
  Re: Why is this algorithm insecure? (Newbie flamefodder) (stanislav shalunov)
  Re: My STRONG data encryption algorithm (stanislav shalunov)
  Re: ? Backdoor in Microsoft web server ? [correction] (Francois Grieu)
  Why encrypt email... ([EMAIL PROTECTED])
  Re: Open Public Key (Tom St Denis)
  Re: ? Backdoor in Microsoft web server ? [correction] (Jim Gillogly)
  Re: Why is this algorithm insecure? (Newbie flamefodder) (Boris Kazak)
  Re: Open Public Key (Mark Wooding)
  Re: GOST idea (Mok-Kong Shen)
  Re: General principles of design (Mok-Kong Shen)
  Re: AND on encrypted data (Mok-Kong Shen)



Subject: Re: Why is this algorithm insecure? (Newbie flamefodder)
From: stanislav shalunov <[EMAIL PROTECTED]>
Date: Sun, 16 Apr 2000 17:12:45 GMT

Richard Heathfield <[EMAIL PROTECTED]> writes:

> Thank you. I'm not sure, however, that I have understood you correctly.
> You seem to be saying that Eve can decrypt any message she likes,
> provided she has first done a chosen plaintext attack on a message that
> length and using the same key as Alice. Okay, yes, that's a problem. But
> how would she do such an attack?

I was a bit careless: known plaintext is enough.

What I have meant is that if Alice sends to Bob a stream of messages
of the same length encrypted with the same key (e.g., network
packets), and if Eve knows plaintext of one of the packets, Eve
immediately can decrypt all the other packets.  (Eve could guess the
first packet, which might be part of a higher-level protocol or make
Alice send some chosen plaintext).

More than that, Eve can simply XOR any two packets and get rid of key
material completely.  If data has enough redundancy (e.g., is natural
language text) both packets can be recovered.  All further and
previous packets of the same length with the same key are compromised.

If a key can never be reused the cryptosystem is useless.  (One could
simply use OTP then.)

Also, you seem to be mentioning overly long keys (4K, etc.) all the
time.  If symmetric cryptosystem needs such long keys you know it's
worthless.  A secure algorithm doesn't need keys longer than 128 bits.
The task of brute-forcing 2^128 different keys is out of reach for any
known adversary.  For extra safety sometimes one might want even
longer key, such as 256 bits, but keys longer than that in a symmetric
system are a sure sign that the designer didn't understand what he's
doing.

-- 
stanislav shalunov  | Speaking only for myself.
My address in From: is correct; if yours isn't, I don't want to hear from you.
Try to reply in newsgroup.  I don't need courtesy copies.

--

Subject: Re: My STRONG data encryption algorithm
From: stanislav shalunov <[EMAIL PROTECTED]>
Date: Sun, 16 Apr 2000 17:19:18 GMT

No, it's not strong.  If you wish to receive further comments, post a
short pseudo-code (or English) description of the algorithm.

-- 
stanislav shalunov  | Speaking only for myself.
My address in From: is correct; if yours isn't, I don't want to hear from you.
Try to reply in newsgroup.  I don't need courtesy copies.

--

From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: ? Backdoor in Microsoft web server ? [correction]
Date: Sun, 16 Apr 2000 19:53:57 +0200

I'm glad I started the thread with a disclaimer.

The text "Nescape engineers are weenies!" is indeed embedded
[reversed] in the file dvwssr.dll coming with some Microsoft
web server software for Windows 95/98 and NT 4 [not Windows
2000], and reportedly in file mtd2lv.dll coming with some
corresponding web authoring tool.
But contrary to some early press reports, evidence is this
string is NOT a universal password, nor part of such a
deliberate mechanism.
My analysis of Microsoft's statements is
- this string is "an obfuscation key to obscure the names
  of files being requested by the client from the server"
  while gathering information used to draw a site map.
- knowledge of this algorithm and key only "allows a user
  who has privileges on a web server to read certain files
  from other web sites hosted on the same computer", and
  therefore the vulnerability only affects "customers who
  host more than one web site on a server".

Still, it looks like Microsoft has distributed a product
[reportedly acquired from another company] relying
deliberately on obscurity for some of it's security features,
a bad professional practice.

Microsoft statements on dvwssr.dll issues are at

and

Understandably, the focus is on another vulnerability:
a subsequently discovered potential for a buffer overrun,
which can lead to a denial of service attack, or conceivably
[IMHO assumi

Cryptography-Digest Digest #557

[Digestifier]

Cryptography-Digest Digest #557, Volume #11  Sun, 16 Apr 00 13:13:01 EDT

Contents:
  Re: Why is this algorithm insecure? (Newbie flamefodder) (erich)
  Re: My STRONG data encryption algorithm (Tom St Denis)
  Observer 16/4/2000: "Jack Straw wants the keys to your office. Don't let him in ..." 
("NoSpam")
  Re: Why is this algorithm insecure? (Newbie flamefodder) (Richard Heathfield)
  Re: One Time Pads Redux ("Amical")
  Re: One Time Pads Redux (Tom St Denis)
  Re: Why is this algorithm insecure? (Newbie flamefodder) (John Savard)
  Re: Open Public Key (Mark Wooding)
  Re: Why is this algorithm insecure? (Newbie flamefodder) (Richard Heathfield)



From: erich <[EMAIL PROTECTED]>
Subject: Re: Why is this algorithm insecure? (Newbie flamefodder)
Date: Sun, 16 Apr 2000 12:26:36 GMT

Well, as NFN NMI L. has pointed out it doesn't matter for the attacker
wether you rotate the bits of the plaintext, because you simply XOR the
result with a random key afterwards. Let's look at an example:

10111000
01110101

11000101

Now assume left rotation by three bits:

11000101
01110101

1011

This is equivalent with simply another key, of course:

10111000
1000

1011

I'm not very experienced and just a hobbyist, but I'd say that your
cipher in fact is a Viginere cipher. To cite from the sci.crypt FAQ:

8.2. How do I break a Vigenere (repeated-key) cipher?

  A repeated-key cipher, where the ciphertext is something like the
  plaintext xor KEYKEYKEYKEY (and so on), is called a Vigenere cipher.
  If the key is not too long and the plaintext is in English, do the
  following:

  1. Discover the length of the key by counting coincidences.
  (See Gaines [GAI44], Sinkov [SIN66].) Trying each displacement of
  the ciphertext against itself, count those bytes which are equal.
  If the two ciphertext portions have used the same key, something
  over 6% of the bytes will be equal. If they have used different
  keys, then less than 0.4% will be equal (assuming random 8-bit bytes
  of key covering normal ASCII text). The smallest displacement which
  indicates an equal key is the length of the repeated key.

  2. Shift the text by that length and XOR it with itself. This
  removes the key and leaves you with text XORed with itself. Since
  English has about 1 bit of real information per byte, 2 streams of
  text XORed together has 2 bits of info per 8-bit byte, providing
  plenty of redundancy for choosing a unique decryption. (And in fact
  one stream of text XORed with itself has just 1 bit per byte.)

  If the key is short, it might be even easier to treat this as a
  standard polyalphabetic substitution. All the old cryptanalysis
  texts show how to break those. It's possible with those methods, in
  the hands of an expert, if there's only ten times as much text as key.
  See, for example, Gaines [GAI44], Sinkov [SIN66].

Others please correct me if I'm wrong.

Greetings,

Erich Steinmann


Sent via Deja.com http://www.deja.com/
Before you buy.

--

From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: My STRONG data encryption algorithm
Date: Sun, 16 Apr 2000 12:43:41 GMT

Hehehehe, I was like this once, basically it looks like a salted
Vinegere cipher (spelling?).  Which given the length of the passphrase
is trivial to break.  Your usage of random() to increase the entropy of
the key is not going to work, so your essentially limited to the
passphrase.

Essentially this is not at all secure, but keep up the research, I
started this way too...hehe

Tom

[EMAIL PROTECTED] wrote:
> 
> /*
> Hi all,
> I have developed a data encryption algorithm and I think it is very
> very strong,
> maybe the strongest ever. It is 32768-bit and can be programmed to be
> stronger easily if you wish. Of course, the stronger, the slower. It is
> always slower than DES. But I think most people take more care of their
> security and the famous morre rule will help to solve this problem.
> To ensure it's strong as well as to share it with you, I post the
> source code here to let you test and try breaking it. Please reply me
> if you find anything unsatisfactory in the algorithm. The code is
> written in Turbo C++ and is easy to understand. If you need a compiled
> exe file, email me and I will give you a copy.
> (Please use it for sientific research only)
> I am looking forward to your replies.
> Best,
> YanQiQi.
> [EMAIL PROTECTED]
> http://www.thinkingsoft.com



--

From: "NoSpam" <[EMAIL PROTECTED]>
Crossposted-To: 
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,uk.business.accountancy,talk.politics.crypto
Subject: Observer 16/4/2000: "Jack Straw wants the keys to your office. Don't let him 
in ..."
Date: Sun, 16 Apr 2000 14:47:54 +0100

Fax your MP about RIP www.stand.org.uk

www.observer.co.uk/business/story/0,6903,194001,00.h

Cryptography-Digest Digest #556

[Digestifier]

Cryptography-Digest Digest #556, Volume #11  Sun, 16 Apr 00 08:13:01 EDT

Contents:
  Re: One Time Pads Redux (Jim Gillogly)
  Re: Why is this algorithm insecure? (Newbie flamefodder) (Richard Heathfield)
  Re: Why is this algorithm insecure? (Newbie flamefodder) (Richard Heathfield)
  Re: Non-standard shift register sequences ("Peter L. Montgomery")
  Re: Is AES necessary? (Bryan Olson)
  Re: Miami Herald article about ATM ripoffs (Norman D. Megill)
  Re: Miami Herald article about ATM ripoffs (Norman D. Megill)
  Re: ? Backdoor in Microsoft web server ? [updated] (Francois Grieu)
  Re: Q: Entropy (Mok-Kong Shen)
  Re: Is AES necessary? (Mok-Kong Shen)
  Re: General principles of design (Mok-Kong Shen)
  My STRONG data encryption algorithm ([EMAIL PROTECTED])



From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: One Time Pads Redux
Date: Sun, 16 Apr 2000 05:14:59 +

Joaquim Southby wrote:
> A) Bob and Alice each have a RNG at their disposal.  These do not need to
> be synchronized or even similar -- they just have to create numbers
> acceptably random for an OTP.

So far so good.

> B) Bob enciphers a message by XOR'ing the plaintext with numbers from his
> RNG; he keeps a temporary copy of the numbers he used for this message.
> He sends the enciphered message to Alice.

Mallet intercepts the message, and now has M XOR Rng[A].

> C) Alice repeats this process using her RNG and sends the result back to
> Bob.

Mallet intercepts the message M XOR Rng[A] XOR Rng[B] and XORs it
with the first message.  He now has Rng[B].

> D) Bob uses his temporary copy of the numbers he used the first time,
> XOR'ing them with Alice's return message to remove his stuff from the
> mix.  He sends the result to Alice.

Mallet intercepts the message M XOR Rng[B] and XORs it with Rng[B],
and reads M a little bit sooner than Alice.

> E) Alice uses her temporary copy to remove her encipherment and retrieve
> the original plaintext message.

Mallet acts on the information slightly before Alice does.

> F) Both of them destroy their temporary copies of their RNG numbers.

Mallet holds onto both of them in hopes of cracking the RNGs before
the next version of the protocol is developed.

> OTP's to multiple users.  It seems so simple (other than the correlation
> of messages to RNG output) that there must be something wrong with it.

Good intuition.
-- 
Jim Gillogly
Hevensday, 26 Astron S.R. 2000, 05:08
12.19.7.2.6, 11 Cimi 9 Pop, First Lord of Night

--

Date: Sun, 16 Apr 2000 08:30:15 +0100
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Why is this algorithm insecure? (Newbie flamefodder)

"NFN NMI L." wrote:
> 
> 
> 128-bit, maybe 256-bit keys are fine.  The larger the key, the more unwieldy it
> is.  If you don't care about large keys, just use an OTP!

Well, there's large and then there's infinite. ;-)

Thanks for your speedy reply.

> 
> <   Pick some number B with which that byte of the key is uniquely
> identified (I used a bunch of primes)
>   Rotate the buffer left by B bits.
>   Perform a Vigenere-style XOR of the key all the way along the buffer.>>
> 
> So, you repeat this process Q times, where Q is the number of bytes in the key,
> and the first time, you rotate the plaintext by 2 bits, the second time, by 3
> bits, and the Qth time by P[Q] bits?

Er, no - my description was less fastidious than my source code, I'm
afraid. Actually it's P[K[n]] where n is the byte we're on, in the range
0 to N - 1 (if the key has N bytes).

  And after each rotation you just XOR the
> value KEYKEYKEYKEY...KEY to the plaintext?

Yes.

> Obviously, you can just start with
> ...000 and then do this process, producing a really munged key, and then
> XOR that key with the plaintext (this is equivalent to your algorithm).

I'm not sure whether that's true, given the above correction (which
stems from my poor explanation).

> This
> algorithm obviously fails horrendously for keys that are all 0's.  What if your
> key is one byte: 01101100, say?  See how little your algorithm can munge this
> key: rotating it by 3 bits is the same as rotating it by 11 bits.

Actually, whilst an 8-bit key is naturally a weakness, it would still
mung a reasonable amount, I think:

plaintext  0010 00111011 10011011
key01101100

So we start off by rotating by P[K[0]] - in my example source code I
used primes, and this byte of the key, 01101100 (108) gives us P[108]
which is 571. So we're going to rotate the buffer left by 571 bits.
Clearly, with a ciphertext of only 24 bits, there's no point in 571: we
can use 571 % 24 (which turns out to be 19. We would therefore take 19
bits off the left of the number and bolt them onto the right. /Now/ we
XOR the key, giving
 
intermed   11011011 11010001 11011100
key01101100 01101100 01101100

ciphertext 10110111 1001 1011

Clearly, a short message