Cryptography-Digest Digest #62, Volume #11 Mon, 7 Feb 00 08:13:01 EST
Contents:
Re: NSA opens up to US News ("Douglas A. Gwyn")
Re: NIST, AES at RSA conference ("r.e.s.")
Re: question about PKI... (Palmpalmpalm)
Re: NIST, AES at RSA conference (Terry Ritter)
Re: Random-Width Transposition Tables? ("r.e.s.")
Re: NIST, AES at RSA conference (David Wagner)
Re: password encryption/decryption (Thomas Wu)
Prior art in science (Mok-Kong Shen)
Re: Polyalphabetic en/de-cryption program (Klaus Pommerening)
Re: polyalphabetic substitution cipher (Klaus Pommerening)
Re: Hill Climbing ("Michael Darling")
Re: Hill Climbing ("Michael Darling")
Re: Challenge: Who can discover the encryption used here? (Volker Hetzer)
Re: question about PKI... ("Lyal Collins")
Re: question about PKI... (Timothy M. Metzinger)
Re: NSA opens up to US News ("Mandy Petui")
----------------------------------------------------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: NSA opens up to US News
Date: Mon, 07 Feb 2000 06:15:38 GMT
John Savard wrote:
> Maybe their *network* went down, ...
Indeed, that was the case. Despite an attempt to cover it up,
somehow it was leaked to the press (ABC), and subsequently the
Director issued a press release in which it was blamed on an
unusually heavy load and said not to have affected collection,
just processing and analysis. (Neither of which seems to be
true.)
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
Date: Sun, 6 Feb 2000 22:44:15 -0800
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote ...
[...]
: An interesting question is, is there some natural
: counterexample wherein the overall "strength"
: (which I guess means difficulty in expert cryptanalysis)
: is actually *reduced* by composing encipherments?
Trivially, rot13(rot13(x))=x gives quite a reduction,
as does (rotN)^M for an M*N-letter alphabet.
--
r.e.s.
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Palmpalmpalm)
Subject: Re: question about PKI...
Date: 07 Feb 2000 07:07:31 GMT
Thanks...but
Is there any method to transfer a "private key" and a certificate on line?
I know that the certificate can be done, but the private key is very sensitive
information and thus any secure channel is necessary or off-line method.
Am I right?
Please let me know it.
Thanks again.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: NIST, AES at RSA conference
Date: Mon, 07 Feb 2000 07:13:08 GMT
On Mon, 07 Feb 2000 04:59:04 GMT, in <[EMAIL PROTECTED]>, in
sci.crypt "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>> "Joseph Ashwood" <[EMAIL PROTECTED]> wrote:
>> >Actually the statement that it is strictly stronger can be
>> >easily contradicted, using XOR (eXclusive-OR), where
>> >regardless of the keys chosen multiple encipherment is
>> >strictly equivalent to a single encipherment with the XOR of
>> >the keys.
>> First of all, only a one-time-pad (OTP) acts like that.
>
>It's true even for Vigenere encipherment (although the
>resulting period is the LCM of the component periods,
>so it is strictly true only when the repeating keys have
>the same length).
Right. Any group.
>> Since each cipher transforms its "plaintext" to ciphertext,
>> we expect each to contribute strength.
>
>If you're going to presuppose the answer, of course you will
>arrive at the conclusion you're after. But such arguments
>aren't proofs.
Fortunately, there is more than one way to do a proof. If we
presuppose the answer, we can search for contradiction.
>Here is another counterexample: simple substitution
>with random alphabet (permutation). Composing any
>number of these yields a cipher of exactly the same
>class; whatever "strength" is supposed to mean, it
>is evidently not increased by the multiple encipherments.
Right. Any group.
It may or may not be worth pointing out that this is a sub-sub-issue
of the original discussion:
The original discussion was that we could have greater confidence in
crypto security by multi-ciphering.
The sub-issue was that multi-ciphering is provably stronger than a
single cipher.
The sub-sub-issue was whether or not additional ciphers can be as weak
as the original. From that discussion, it is now clear that we have
to avoid ciphers which constitute a group. I think we can do that,
especially if the ciphers have different architectures.
The provable "increase in strength" to which I refer in the sub-issue
is simply the effort involved in executing the additional cipher, even
if that is broken or the key known. Even if the transformation from
ciphertext to plaintext for the second cipher is "easy," it still must
take place, and that is strength, even if hardly any at all.
>An interesting question is, is there some natural
>counterexample wherein the overall "strength"
>(which I guess means difficulty in expert cryptanalysis)
>is actually *reduced* by composing encipherments?
Sure. Deciphering with the correct key. But that seems unreasonable
as a real weakness, and is certainly not an attack strategy.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: Random-Width Transposition Tables?
Date: Sun, 6 Feb 2000 23:22:29 -0800
"John Savard" <[EMAIL PROTECTED]> wrote ...
: "r.e.s." <[EMAIL PROTECTED]> wrote, in part:
:
: >I can only speculate that a rationale to justify such a sacrifice
: >of entropy must involve hardening wrt to non-brute-force attacks.
: >Is that correct? Is there any "accepted wisdom" about when, whether,
: >and/or how much to randomize transposition table-widths?
:
: Yes. If one knows, for a simple columnar transposition, the length of
: the key, then one can immediately know the size of the "chunks" to
: divide the plaintext into to form the columns which were read out of
: the block (the only thing one doesn't know is which chunks contain one
: extra odd letter).
The case of a simple "row-wise fill" seems clear enough, but if more
complex transposition is used (e.g. "patterned fills" etc) it's not
so obvious to me. But if such cases do benefit from randomizing the
number of columns over a range [lo,hi], I still wonder how one might
go about determining the most advantageous values for lo & hi. (?)
--
r.e.s.
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: NIST, AES at RSA conference
Date: 6 Feb 2000 23:45:40 -0800
In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
> The provable "increase in strength" to which I refer in the sub-issue
> is simply the effort involved in executing the additional cipher, even
> if that is broken or the key known. Even if the transformation from
> ciphertext to plaintext for the second cipher is "easy," it still must
> take place, and that is strength, even if hardly any at all.
But this is *wrong*, as is implicitly demonstrated by the counterexamples.
Consider double-encryption with Vigenere (a group). Deciphering this
takes *precisely* as much work as deciphering single-Vigenere.
You claimed that the cryptanalyst must take the time to execute both
components of the multi-cipher to read the traffic. This is wrong:
because double-encryption is here equivalent to single-encryption with
a different key, the cryptanalyst will just do a single decryption,
executing the cipher only once to read the traffic. You failed to
consider the possibility of shortcut attacks that bypass the second
cipher.
One might conjecture that this phenomenom only occurs when the cipher
is a group, but such a claim would remain unproven at best.
------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: password encryption/decryption
Date: 07 Feb 2000 00:59:01 -0800
Eric Lee Green <[EMAIL PROTECTED]> writes:
>
> The "standard" protocol, not involving any encyption, is to store a one-way
> (non-reversible) hash of the password on the server. This way, if someone
> compromises the password file on the server, it's no big deal.
The "standard" protocol makes the server's password file entries plaintext-
equivalent to the users' passwords. If someone compromises the password
file on the server, it *is* a big deal, since he now has access to everybody's
account and has broken the system completely.
If P is the user's password, and the server stores H(P), your protocol has
the server sending s (the salt) and expecting H(H(P), s) back. Of course,
if an attacker steals H(P) for any user, he can compute H(H(P), s) as well,
even if he can't get at P directly. He doesn't need it.
> How the communications works:
> The server sends a random salt value (usually 128 to 168 bits in length) to
> the client that wishes to log in.
> The client sends a MD5 or SHA1 hash value to the server , a hash
> that has hashed into it:
> a) all characters of the password or passphrase, and then, the resulting
> hash is
> hashed with
> b) all characters of the 'salt' value.
> The server retrieves the one-way hash from its database, and adds in the
> 'salt' value.
> The resulting hash is then compared with the one sent by the client. If the
> two match,
> the client is authorized. If the two do not match, the client is NOT
> authorized.
>
> Note that no passwords are ever sent across the network. Also note that this,
> like many such schemes, is succeptible to dictionary attacks. See any good
> book about encryption to find out about dictionary attacks, replay attacks,
> and other such attacks that you need to be aware of.
Also check the Web for references to authentication systems that resist
the abovementioned attacks:
http://srp.stanford.edu/srp/
http://www.integritysciences.com/
--
Tom Wu * finger -l [EMAIL PROTECTED] for PGP key *
E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms in
Phone: (650) 723-1565 exchange for security deserve neither."
http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/srp/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Prior art in science
Date: Mon, 07 Feb 2000 11:10:56 +0100
The issue of 'prior art' is not only relevant in patent applications
but also of interest by itself in general in science, I suppose.
Recently in a thread it has been pointed out that what has been
published in newsgroups and similar forums possibly may not
qualify as 'prior art' because of limited possibilities of being
found in searches. Evidently this concerns at the end what is
defined as searching and is also related to documentation. In the
pre-electronic time, things were relatively simple. Matters that
were not in books or journals were not known to the general public.
But even in that situation there were problems concerning
accessibility, e.g. Russian journals for those living in west
European countries. In my personal opinion, the documentaion and
search possibilities of newsgroups articles are indeed not (yet)
very optimal for those who pose definite enquires. One factor among
others that make the search difficult is evidently the shear volume
of the articles in the internet forums. Another factor is that by
nature the articles there contain a high proportion of chaffs as
compared to the body of printed scientific publications. A large
part of newsgroup articles is known to be regularly archived by
dejanews, though personally I have yet no experience of how
efficient the search is concerning matters that lie very far back
on the time scale. On the other hand, an increasing number of
scientific journals are published exclusively electronically. The
volume of (genuine) scientific informations as a whole is exploding
at a terrible speed and it is not apparent how a scientist can have
sufficient confidence to have found almost everything that interests
him by doing weeks of searches employing all means available to him.
(That an employee at the patent office may not have the incentive or
energy to perform similar tasks is well understandable.) So in some
sense it appears paradoxically that, while we acquire more knowledge
every day, we know less at the same time.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Klaus Pommerening)
Subject: Re: Polyalphabetic en/de-cryption program
Date: 7 Feb 2000 10:27:13 GMT
In <eV0n4.1069$[EMAIL PROTECTED]> "Andersen" wrote:
> Does anyone know a pc program which can encrypt and decrypt plain text
by
> the polyalphabetic method as I need to create some exaples using that
> method.
>
Perl program for polyalphabetic ciphers
http://www.uni-mainz.de/~pommeren/Kryptologie/Perl/porta.pl
http://www.uni-mainz.de/~pommeren/Kryptologie/Perl/auxcrypt.pl
--
Klaus Pommerening [http://www.Uni-Mainz.DE/~pommeren/]
Institut fuer Medizinische Statistik und Dokumentation
der Johannes-Gutenberg-Universitaet, D-55101 Mainz, Germany
------------------------------
From: [EMAIL PROTECTED] (Klaus Pommerening)
Subject: Re: polyalphabetic substitution cipher
Date: 7 Feb 2000 10:29:03 GMT
In <87hs1j$d31$[EMAIL PROTECTED]> [EMAIL PROTECTED] wrote:
> Does anyone know of any tools on the internet to decipher
> polyalphabetic substitution ciphers -- something that one:
> - figures out how many alphabets are being used
> - deciphers text accordingly.
>
In Perl:
http://www.uni-mainz.de/~pommeren/Kryptologie/Perl/kasiski.pl
http://www.uni-mainz.de/~pommeren/Kryptologie/Perl/coinc.pl
http://www.uni-mainz.de/~pommeren/Kryptologie/Perl/auxcrypt.pl
--
Klaus Pommerening [http://www.Uni-Mainz.DE/~pommeren/]
Institut fuer Medizinische Statistik und Dokumentation
der Johannes-Gutenberg-Universitaet, D-55101 Mainz, Germany
------------------------------
From: "Michael Darling" <[EMAIL PROTECTED]>
Subject: Re: Hill Climbing
Date: Mon, 7 Feb 2000 10:43:46 -0000
Thanks for your reply.
Has Jim Gillogly written a paper on the subject of Hillclimbing?
If so is there an online version of it as I'd like to read it.
Thanks,
Mike.
James Pate Williams, Jr. <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Fri, 4 Feb 2000 16:29:43 -0000, "Michael Darling"
> <[EMAIL PROTECTED]> wrote:
>
> >I'm hearing a lot about hill climbing algorithms - can anyone tell me of
any
> >links or books which would
> >tell me more about them.
> >
>
> Hill-climbing algorithms are used in the branch of computer science
> known as artificial intelligence to solve constraint satisfaction
> problems such as the N-queens problem and graph k-coloring
> problem. Jim Gillogly (sp?) can tell you about the shotgun
> hill-climbing algorithm that is used in the cryptanalysis of some
> classic encryption systems.
>
> ==Pate Williams==
> [EMAIL PROTECTED]
> http://www.mindspring.com/~pate
>
------------------------------
From: "Michael Darling" <[EMAIL PROTECTED]>
Subject: Re: Hill Climbing
Date: Mon, 7 Feb 2000 10:49:29 -0000
Thanks for your reply. This has given me a little bit better understanding
of the subject.
I was thinking in terms of 2D graphs - the 3D I hadn't considered. Ideally
what I would
like is an example of hill climbing to solve something simple like a
playfair
cypher - then I believe the scoring function would be the Index of
coincidence
or something similar?
Anyone know of any online tutorials in this area.
Regards,
Mike.
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Michael Darling wrote:
> > I'm hearing a lot about hill climbing algorithms - can anyone tell
> > me of any links or books which would tell me more about them.
>
> Check out texts on optimization.
>
> The basic idea is to think of the problem parameters as a domain,
> generally sketched on the blackboard as the domain of a 2-D map
> (although there may be more than 2 independent parameters),
> and the "goodness value" of the function to be maximized as
> altitude, so one envisions a 3-D relief map where good values
> for the parameters are hills and bad values are valleys. A
> hill-climbing algorithm searches for a maximum value by sampling
> the domain and trying to follow the terrain up hills. Since
> each hill is merely a *local* maximum, a global optimum can be
> found only by special variations on this general method, such
> as sampling several random points in the domain every so often.
>
> One thing necessary for hill climbing is a scalar "goodness"
> function. For many applications, this is obvious (least cost,
> least work, etc.), but for the cryptographic problem it might
> not be obvious: Is AJSOWL better than EOQJDS? (Neither one
> has any straightforward relation to the actual plaintext.)
>
> In case there is no local structure (no obvious connection
> between values for one parameter set and an adjacent parameter
> set), the whole method breaks down. Ideally, changing any key
> bit causes about half the PT bits to change under a (spurious)
> decipherment, which kills hill-climbing methods.
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Challenge: Who can discover the encryption used here?
Date: Mon, 07 Feb 2000 11:11:17 +0000
TJ wrote:
>
> > What about contacting the guys who wrote it?
> >
> Yeah,
> I tried that thanks, but they "do not have the human resources to enable us
> to deal with such specific and individual requests.......yadda "
Looks like their polite phrase for "it's no business of yours."
> I just thought the crew here might be able to decipher the text thats all.
Perhaps there are.
> Guess I over-estimated the abilities of those who patronise this newsgroup.
No, you just didn't manage to convince us that you're not trying to cheat.
Volker
--
Hi! I'm a signature virus! Copy me into your signature file to help me spread!
------------------------------
From: "Lyal Collins" <[EMAIL PROTECTED]>
Subject: Re: question about PKI...
Date: Mon, 7 Feb 2000 18:55:25 +1100
No secure on-line transfer mechanism exists in normal browsers etc.
Why not get a new certificate for each access device - then there is no need
to transfer anything - just manage the passwords as per normal.
Lyal
Palmpalmpalm wrote in message
<[EMAIL PROTECTED]>...
>Thanks...but
>Is there any method to transfer a "private key" and a certificate on line?
>I know that the certificate can be done, but the private key is very
sensitive
>information and thus any secure channel is necessary or off-line method.
>Am I right?
>
>Please let me know it.
>Thanks again.
------------------------------
From: [EMAIL PROTECTED] (Timothy M. Metzinger)
Subject: Re: question about PKI...
Date: 07 Feb 2000 12:23:42 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Palmpalmpalm) writes:
>What method does the PKI product provide for mobile users?
>When users move to another computer, do they have to bring their own private
>key and certificate always?
>
In a PKI designed for high assurance, users rarely store their private keys on
a PC hard drive, because of the risk of someone hacking against that PC to gain
access to the private key(s). In this situation, the user is usually given a
"token" of some sort to hold the private key. This token can range from being a
floppy disk (not very secure) to a smart card, to a USB device, to a FIPS 140-1
level 3 unit like the Luna PED.
By seperating the private key from the PC, and making the user responsible for
safe handling, it's easier for users to move from PC to PC, AND the PKI is
(generally) more secure, all other things being equal.
Timothy Metzinger
Commercial Pilot - ASEL - IA AOPA Project Pilot Mentor
DOD # 1854 '82 Virago 750 - "Siobhan"
Cessnas, Tampicos, Tobagos, and Trinidads at FDK
------------------------------
From: "Mandy Petui" <[EMAIL PROTECTED]>
Subject: Re: NSA opens up to US News
Date: Mon, 7 Feb 2000 05:28:12 -0700
Sure, but NSA is so stuck on security and secrecy that they surely have
compartmentalized and *physically * separated their networks. Also, a
*leak* from NSA is not like a leak from the White House or the Department
of Education. A leak of sensitive info from the boys at Fort Meade would
bring on some heavy duty plumbers in no time flat. You just cannot have a
leaky cryptographic agency. What you want and what I believe we have is an
agency skilled at using the media for it's own advantage.
JK http://www.crak.com
John Savard <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Sun, 6 Feb 2000 15:54:30 -0700, "Henny Youngman"
> <[EMAIL PROTECTED]> wrote, in part:
>
> >Saying the NSA had a computer failure is like saying
> [the city of]
> >Phoenix
> [, Arizona]
> >had a restaurant failure.
>
> >No way "ALL" or even a large portion of NSA's computers went south at the
> >same time.
>
> Maybe their *network* went down, and so they couldn't use the
> computers, even if the computers _themselves_ were working. I could
> *indeed* imagine that the NSA might have their mighty array of Crays
> and the like connected to a network, and the people using them would
> do so from PC-like machines. In fact, I'm rather sure that is what was
> meant.
>
> And the article also contained a reference to an ambitious NSA network
> plan that didn't quite work out well.
>
> John Savard (teneerf <-)
> http://www.ecn.ab.ca/~jsavard/index.html
------------------------------
** 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
******************************
