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
<http://www.microsoft.com/technet/security/bulletin/ms00-025.asp>
and
<http://www.microsoft.com/technet/security/bulletin/fq00-025.asp>
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 assuming the attacker is immensely clever and lucky]
to arbitrary code being run.
Francois Grieu
------------------------------
From: [EMAIL PROTECTED]
Subject: Why encrypt email...
Date: Sun, 16 Apr 2000 17:49:09 GMT
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.
Much email is non-sensitive info so encryption is not used. At other
times, like for medical records, email is encrypted to protect
confidential info.
2) Email encryption is not used because users don't know how much it is
worth. Email encryption developers need funds to create privacy, but
different users value privacy differently. Many users want free online
privacy, expecting it to be "provided" by the Net. Others, like
corportate users, will pay resonable fees to companies (like Verisign)
because they need strong encryption.
What I need are papers, books, or other documents that back up (or
refute) the above claims. If anyone has user survey data (how users
value email encryption) that would be ideal!
Thank you,
Stanley
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Open Public Key
Date: Sun, 16 Apr 2000 18:06:26 GMT
Mark Wooding wrote:
>
> Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> > [EMAIL PROTECTED] wrote:
> > > Tom St Denis <[EMAIL PROTECTED]> wrote:
> > >
> > > > ElGammal or ECC are the certain winners in this case. Although
> > > > ElGammal is slightly easier to implement and understand.
>
> Firstly, his name is ElGamal. One `m'.
Oops.
>
> Secondly, Certicom holds many patents on elliptic curve methods. I
> wouldn't call ECC particularly `open'.
>
> > > How secure are ElGammal and ECC??
> > > Where can I find more information about ElGammal or ECC?
> >
> > ElGammal is slower and takes more space then RSA, but it's a bit tougher
> > to crack [ie solve]. You can find out about it on my little dork page
> > at
>
> I'm intrigued by this statement. Do you have any evidence with which to
> back it up? I'll not get into a discussion of performance: it depends
> on far too many factors.
>From what I have read the best Discrete log solved was 385 bits. I
would put this too way, either nobody cares to solve a bigger one, or
it's too hard, and takes more time.
> Your second point about ElGamal `taking more space'. I *presume* that
> you're referring to message expansion in encryption. If you're talking
> about signatures then you lose because the DSA-style reduction mod q,
> where q is a prime factor of p - 1 the ElGamal group order can be
> applied to the results and you end up with two signature components of
> (say) 256 bits each as opposed to an RSA signature of 1024 bits.
That's if you use the sub-group variant.
> If you use ElGamal absolutely straight then you get message expansion by
> a factor of two. Looking at ElGamal another way around, though, it's
> offline Diffie-Hellman, using modular multiplication by the shared
> secret as a simple symmetric cipher. But the usual job for public-key
> encryption is transmission of a symmetric session key, so why not simply
> use the Diffie-Hellman shared secret directly? Comparing a 1024-bit
> offline Diffie-Hellman key exchange with a 1024-bit RSA encrypted
> session key looks fairly even to me. Then consider the mess with PKCS#1
> plaintext formatting in RSA -- an adaptive chosen ciphertext attack
> using PKCS#1 decode failures (fixed in PKCS#1 v2.0).
I thought this is the normal Elgamal?
> ElGamal *encryption* isn't terribly useful, and DSA seems to be rather
> better for making signatures.
Isn't terribly usefull? If it's difficult to solve, and can be used,
it's usefull. If you don't want to use RSA, elgamal is certainly an
alternative.
> > Note: My spelling and grammar are a bit off, so if you actually read
> > the page and have comments please let me know.
>
> Just having read the ElGamal bits, I think you've not read Ross Anderson
> and Serge Vaudenay's excellent `Minding your p's and q's'
> (http://www.cl.cam.ac.uk/ftp/users/rja14/psandqs.ps.gz). Basically, do
> *not* choose g to be primitive mod p. It's a really bad idea.
If 'g' is not a primitive multiplicative generator then the pollard-rho
DL algorithm can be used can't it? taking sqrt(p) time where p is the
order of 'g'.
> 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.
Tom
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: ? Backdoor in Microsoft web server ? [correction]
Date: Sun, 16 Apr 2000 18:24:03 +0000
Francois Grieu wrote:
> 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.
The analyst who reported the problem (Rain Forest Puppy) did
not say it was a universal password, if by that you mean something
like the trojanized FTP of a few years ago that had a root access
password built in. However, it was obviously deliberate. See
http://packetstorm.securify.com/0004-exploits/RFP2K02.txt for
the actual claims of the analysts who investigated this back door.
> 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.
More than that: it fits the classical definition of a back door.
The insiders who placed this back door can access more information
than they're entitled to by using the password they left in there.
To bring back a little sci.crypt relevance, the URL above describes
the weak encryption algorithm used to obscure passwords (which he
calls the "weenie" algorithm).
> Microsoft statements on dvwssr.dll issues are at
> <http://www.microsoft.com/technet/security/bulletin/ms00-025.asp>
> and
> <http://www.microsoft.com/technet/security/bulletin/fq00-025.asp>
> 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 assuming the attacker is immensely clever and lucky]
> to arbitrary code being run.
Regardless of precisely which magical powers the back door gives,
it <is> a back door put into offical Microsoft code by official
Microsoft (weenie) engineers.
--
Jim Gillogly
Hevensday, 26 Astron S.R. 2000, 18:07
12.19.7.2.6, 11 Cimi 9 Pop, First Lord of Night
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Why is this algorithm insecure? (Newbie flamefodder)
Date: Sun, 16 Apr 2000 18:41:08 GMT
Richard Heathfield wrote:
>
> Here's the algorithm, which I rather self-consciously call CDX-1:
>
> Read the /whole/ plaintext into a buffer.
> Read the whole of the key into another buffer.
>
> For each byte of the key
> 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.
> Next
>
> Write out the buffer to the ciphertext file.
>
> Decryption is a simple reverse of the above process.
>
> I'd love to analyse this but I really don't have the skill to do it. I
> had a hard enough time breaking a Vigenere cipher.
>
> Since I'm no expert, I have to assume this algorithm is weak. But it
> looks horrendous. Yes, the key is scrawled all over the data but, on the
> other hand, the bits are constantly being stirred by the rotations,
> creating what I can only imagine to be a rather thick bit soup.
>
> (Please assume that the key is generated randomly. I know this is
> impossible within ordinary software in a digital computer, but please
> assume it anyway!)
> **********************
Imagine 2 plaintexts - both of the same length, differing in 1 bit,
for example, 1101100110110010 and 1101100110110011. Then after being
encrypted with your algorithm the 2 ciphertexts will differ in exactly
1 bit. This immediately gives you the total number of shifts and the
value of the total "key" at this spot.
Do you see now why this algorithm is weak?
Best wishes BNK
*************************
> Richard Heathfield
>
> "Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
>
> C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
> 29 K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html (68
> to go)
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Open Public Key
Date: 16 Apr 2000 18:41:41 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> > I'm intrigued by this statement. Do you have any evidence with which to
> > back it up? I'll not get into a discussion of performance: it depends
> > on far too many factors.
>
> From what I have read the best Discrete log solved was 385 bits. I
> would put this too way, either nobody cares to solve a bigger one, or
> it's too hard, and takes more time.
Both can be attacked by the generalized number field sieve. If what
I've understood from the postings by Bob Silverman in this group, the
matrix step at the end of a (cryptanalytically interesting) discrete log
computation is less absurdly difficult than the similar computation for
factoring.
Both are `difficult'. I suspect that less actual progress on large
discrete log problems has been made because RSA is better publicized
than DLP-based systems.
> > Your second point about ElGamal `taking more space'. I *presume* that
> > you're referring to message expansion in encryption. If you're talking
> > about signatures then you lose because the DSA-style reduction mod q,
> > where q is a prime factor of p - 1 the ElGamal group order can be
> > applied to the results and you end up with two signature components of
> > (say) 256 bits each as opposed to an RSA signature of 1024 bits.
>
> That's if you use the sub-group variant.
Yes. You'd be mad not to, really.
> > If you use ElGamal absolutely straight then you get message expansion by
> > a factor of two. Looking at ElGamal another way around, though, it's
> > offline Diffie-Hellman, using modular multiplication by the shared
> > secret as a simple symmetric cipher. But the usual job for public-key
> > encryption is transmission of a symmetric session key, so why not simply
> > use the Diffie-Hellman shared secret directly? Comparing a 1024-bit
> > offline Diffie-Hellman key exchange with a 1024-bit RSA encrypted
> > session key looks fairly even to me. Then consider the mess with PKCS#1
> > plaintext formatting in RSA -- an adaptive chosen ciphertext attack
> > using PKCS#1 decode failures (fixed in PKCS#1 v2.0).
>
> I thought this is the normal Elgamal?
(Notation: p is the group modulus, g is the generator of a large prime-
order subgroup of GF(p), x is Bob's private key, y is his private key.)
Diffie-Hellman:
A --> B: g^r mod p, use y^r mod p as a session key.
ElGamal:
A --> B: g^r mod p, k y^r mod p, use k as a session key.
Offline DH is preferable because decryption is simpler (ElGamal also
requires a modular inverse and multiply), and it requires less data.
Yes?
> > ElGamal *encryption* isn't terribly useful, and DSA seems to be rather
> > better for making signatures.
>
> Isn't terribly usefull? If it's difficult to solve, and can be used,
> it's usefull. If you don't want to use RSA, elgamal is certainly an
> alternative.
In real life, it offers the same security as offline DH, but it's more
complicated and produces more ciphertext. I don't think that makes it
useful, do you?
> > > Note: My spelling and grammar are a bit off, so if you actually read
> > > the page and have comments please let me know.
> >
> > Just having read the ElGamal bits, I think you've not read Ross Anderson
> > and Serge Vaudenay's excellent `Minding your p's and q's'
> > (http://www.cl.cam.ac.uk/ftp/users/rja14/psandqs.ps.gz). Basically, do
> > *not* choose g to be primitive mod p. It's a really bad idea.
>
> If 'g' is not a primitive multiplicative generator then the pollard-rho
> DL algorithm can be used can't it? taking sqrt(p) time where p is the
> order of 'g'.
Yes. You choose the generator order to be large enough so that
Pollard's rho is impractical. About 2^256 is about right. 2^160, as
used in DSA, is too small for my liking.
If the main modulus is a safe prime around 2^1024, then doing Pollard's
rho against the prime-order subgroup is O(2^511), or negligibly easier
than doing Pollard's rho against the main discrete log group anyway.
> > 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.
-- [mdw]
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: GOST idea
Date: Sun, 16 Apr 2000 21:09:59 +0200
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.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: General principles of design
Date: Sun, 16 Apr 2000 21:10:07 +0200
I suppose that 'diversity' passes as yet another general
principle of design of encryption algorithms. By that I mean
one should be liberal/flexible in the choice of the
components of the algorithms and not be confined from the
beginning to a very resticted repertoire of concepts/constructs.
The success of DES has rendered the Feistel construction very
well-known. However, a new block cipher certainly need not
closely mimic DES, though past experiences are very often
extremely helpful guides. Even the common dichotomy of
stream/block ciphers, notwithstanding its pedagogical and other
values, shouldn't lead to an apriori exclusion of features that
could be of value for the functioning of an algorithm as a whole.
In fact, an encryption algorithm can be a combination of diverse
stream- and block-oriented constructs. (The boundary between
encryption in the narrow sense and steganography is also fluid.)
It is intuitively clear that higher diversity forces the
opponent to employ a larger arsenal of methods of analysis
and lowers the success chance of launching a concentrated
attack on a single spot. Further, it appears to be profitable
to be open-minded towards considering adaptation of techniques
that are employed in neighbouring fields, e.g. data compression.
M. K. Shen
===========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: AND on encrypted data
Date: Sun, 16 Apr 2000 21:10:13 +0200
John Savard wrote:
>
> Multiple texts that are encrypted by the same bit transposition can be
> XORed, ANDed, or ORed with one another.
Maybe I misunderstood. But, if two bit streams are ANDed, how can
later the two streams be separated out? Thanks.
M. K. Shen
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
