Cryptography-Digest Digest #825, Volume #11 Sat, 20 May 00 11:13:00 EDT
Contents:
Re: Interpretation of Hitachi patent claims (David Blackman)
Re: Compare 3DES's. (long) (Was: Mixmasters encrypt how?) (Paul Schlyter)
Re: Compare 3DES's. (long) (Was: Mixmasters encrypt how?) (tomstd)
Re: P+1 factorization algorithm (Cronos)
Re: Chosen plaintext attack, isn't it absurd? (John Savard)
Re: Reasonably secure OTP passing (Tim Tyler)
Re: Reasonably secure OTP passing (John Savard)
Re: what is the status finite automata base cryptosystems? (Tim Tyler)
Re: Base Encryption: Revolutionary Cypher (Tim Tyler)
Re: Chosen plaintext attack, isn't it absurd? (Jonathan Thornburg)
----------------------------------------------------------------------------
From: David Blackman <[EMAIL PROTECTED]>
Subject: Re: Interpretation of Hitachi patent claims
Date: Sat, 20 May 2000 19:17:46 +1000
Lyalc wrote:
> Patents are not written for others to understand them.
> They are written to define some intellectual property about a process. The
> patent office, patent lawyers, and the courts decide what is actually
> defined in the context of a specific challenge to a specific patent.
In some countries, including the USA, patents are supposed to be written
so that experts in the field can understand them. There is actually
something in the law about patents having to "teach" potential licencees
how do to the process described. If the patent is not written for others
to understand it, it is supposed to be invalid. (I am not a lawyer, and
i haven't looked at this for years, handle with care :-)
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Compare 3DES's. (long) (Was: Mixmasters encrypt how?)
Date: 20 May 2000 09:52:32 +0200
In article <8g4lqn$1eb$[EMAIL PROTECTED]>,
William Rowden <[EMAIL PROTECTED]> wrote:
> I want to understand the mechanics of Triple-DES, especially as used
> by Mixmaster remailers (see quotes below). I have read the pertinent
> sections of _Applied Cryptography_ (1st ed.) and _Handbook of Applied
> Cryptography_, and I still have these questions, so I'm asking my
> favorite newsgroup and some others for clarification. Please feel
> free to point me to additional sources.
>
> What variants of Triple-DES are in use, and how does their security
> compare? Specifically, I have these questions:
>
> . What advantage is there in using EDE? That is, why use
> E(K1,D(K2,E(K1,x))) rather than, say, E(K1,E(K2,E(K1,x)))? Is it only
> for backwards compatibility, since the DES encrypt and decrypt
> processes are equally secure? ("Backwards compatibility" here means
> that if K1=K2, E(K1,D(K2,E(K1,x))=E(K1,x), equivalent to single DES.)
Yes, it's for backwards compatibility: you then have a means to make
a 3DES devive compatible to an 1DES device.
> . Is using EDE weaker than the alternative? Since if K1=K2, EDE is
> equivalent to single DES, doesn't that reduce the usable keyspace?
> The same is *not* true of E(K1,E(K2,E(K1,x))): since DES does not form
> a group, there is no equivalent single DES even if K1=K2.
On the other hand, the key space is still only 2^56 keys with K1=K2,
so it offers no security advantage over EDE 3DES. And you lose the
backwards compatibility to 1DES.
> A similar observation applies to E(K1,D(K2,E(K3,x))) if K1=K3.
>
> . If EDE is preferred due to backwards compatibility only, why would
> one use it (as in Mixmaster) with 24 bytes of key? Obviously, here 24
> bytes * 8 bits/byte = 192 bits = 3 keys * (56 bits + 8 parity
> bits)/key. That is, why use E(K1,D(K2,E(K3,x))) rather than
> E(K1,E(K2,E(K3,x)))?
If K1, K2 and K3 are all different, there are ways to attack 3DES
which effectively reduces the key space to a 16-byte key. Therefore
using K1 different from K3 offers little security advantages over
using K1=K3.
> . How much stronger is use of 24 bytes of key as compared with 16
> bytes? That is, how does E(K1,D(K2,E(K3,x))) compare to
> E(K1,D(K2,E(K1,x)))? A naive view would say that 24 bytes would take
> at least 2**64 longer to crack than 16 bytes, but this assumes that no
> attack more efficient than brute force is available.
24-byte keys aren't much stronger than 16-byte keys, due to that
attack on 2DES which reduces a 24-byte key to a 16-byte key.
See above.
> . Conversely, if 24 bytes is *much* more secure than 16 bytes of
> key, why would one use the latter? The computation time for three DES
> encryptions/decryptions is necessary in either case, and the
> "backwards compatible" keys (K1=K3) still exist when using EDE.
Because 24-byte keys aren't much stronger than 16-byte keys in 3DES.
See above.
> . How is CBC mode defined for 3DES? According to the sci.crypt FAQ,
> only ECB is defined for 3DES.
While there's no official CBC 3DES definition, the most
striaghtforward way to define CBC for 3DES is to just use the 1DES
definition of CBC, but to replace each primitive 1DES operation with
a 3DES operation instead.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
Subject: Re: Compare 3DES's. (long) (Was: Mixmasters encrypt how?)
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 20 May 2000 04:28:35 -0700
In article <8g5g80$7s9$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Paul Schlyter) wrote:
>In article <8g4lqn$1eb$[EMAIL PROTECTED]>,
>William Rowden <[EMAIL PROTECTED]> wrote:
>
>> I want to understand the mechanics of Triple-DES, especially
as used
>> by Mixmaster remailers (see quotes below). I have read the
pertinent
>> sections of _Applied Cryptography_ (1st ed.) and _Handbook of
Applied
>> Cryptography_, and I still have these questions, so I'm
asking my
>> favorite newsgroup and some others for clarification. Please
feel
>> free to point me to additional sources.
>>
>> What variants of Triple-DES are in use, and how does their
security
>> compare? Specifically, I have these questions:
>>
>> . What advantage is there in using EDE? That is, why use
>> E(K1,D(K2,E(K1,x))) rather than, say, E(K1,E(K2,E(K1,x)))?
Is it only
>> for backwards compatibility, since the DES encrypt and decrypt
>> processes are equally secure? ("Backwards compatibility"
here means
>> that if K1=K2, E(K1,D(K2,E(K1,x))=E(K1,x), equivalent to
single DES.)
>
>Yes, it's for backwards compatibility: you then have a means to
make
>a 3DES devive compatible to an 1DES device.
>
>> . Is using EDE weaker than the alternative? Since if
K1=K2, EDE is
>> equivalent to single DES, doesn't that reduce the usable
keyspace?
>> The same is *not* true of E(K1,E(K2,E(K1,x))): since DES does
not form
>> a group, there is no equivalent single DES even if K1=K2.
>
>On the other hand, the key space is still only 2^56 keys with
K1=K2,
>so it offers no security advantage over EDE 3DES. And you lose
the
>backwards compatibility to 1DES.
>
>> A similar observation applies to E(K1,D(K2,E(K3,x))) if K1=K3.
>>
>> . If EDE is preferred due to backwards compatibility only,
why would
>> one use it (as in Mixmaster) with 24 bytes of key?
Obviously, here 24
>> bytes * 8 bits/byte = 192 bits = 3 keys * (56 bits + 8 parity
>> bits)/key. That is, why use E(K1,D(K2,E(K3,x))) rather than
>> E(K1,E(K2,E(K3,x)))?
>
>If K1, K2 and K3 are all different, there are ways to attack
3DES
>which effectively reduces the key space to a 16-byte key.
Therefore
>using K1 different from K3 offers little security advantages
over
>using K1=K3.
I disagree, the mitm attack on three-key triple des requires a
huge amount of memory and plaintext pairs. It's not practical
at all.
>> . How much stronger is use of 24 bytes of key as compared
with 16
>> bytes? That is, how does E(K1,D(K2,E(K3,x))) compare to
>> E(K1,D(K2,E(K1,x)))? A naive view would say that 24 bytes
would take
>> at least 2**64 longer to crack than 16 bytes, but this
assumes that no
>> attack more efficient than brute force is available.
>
>24-byte keys aren't much stronger than 16-byte keys, due to that
>attack on 2DES which reduces a 24-byte key to a 16-byte key.
>See above.
an even number of des applications is easier to break then an
odd. Which is why triple des is used instead of double. Triple
des is still rather secure since the mitm is not feasible.
>> . Conversely, if 24 bytes is *much* more secure than 16
bytes of
>> key, why would one use the latter? The computation time for
three DES
>> encryptions/decryptions is necessary in either case, and the
>> "backwards compatible" keys (K1=K3) still exist when using
EDE.
>
>Because 24-byte keys aren't much stronger than 16-byte keys in
3DES.
>See above.
>
>> . How is CBC mode defined for 3DES? According to the
sci.crypt FAQ,
>> only ECB is defined for 3DES.
>
>While there's no official CBC 3DES definition, the most
>striaghtforward way to define CBC for 3DES is to just use the
1DES
>definition of CBC, but to replace each primitive 1DES operation
with
>a 3DES operation instead.
>
>--
>----------------------------------------------------------------
>Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
>Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
>e-mail: pausch at saaf dot se or paul.schlyter at ausys
dot se
>WWW: http://hotel04.ausys.se/pausch
http://welcome.to/pausch
>
>
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Cronos <[EMAIL PROTECTED]>
Subject: Re: P+1 factorization algorithm
Date: Sat, 20 May 2000 12:38:22 +0100
So you dont mean the Lucas Sequence P+1 method then ? there is another
one ? What do you mean smooth ? As in small factors ?
On Thu, 18 May 2000 10:15:42 GMT, [EMAIL PROTECTED] wrote:
>Does anyone have source code, or a detailed description of how to
>implement, the P+1 factorization algorithm?, i.e. the one that finds a
>prime factor p of a large composite N if p+1 is smooth.
>I think I understand the theory but I don't have any experience
>of implementing an algorithm that works over GF(p^2).
>
>TIA
>Chris
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Chosen plaintext attack, isn't it absurd?
Date: Sat, 20 May 2000 14:02:46 GMT
On Wed, 17 May 2000 15:42:28 +0200, "Manuel Pancorbo"
<[EMAIL PROTECTED]> wrote, in part:
>I mean, if the attacker is able to access the encipher machinery (but not
>the actual key) and then test the ciphertexts she wants, what stops her to
>access the DEcipher machinery?
Aside from the specific case of public-key ciphers, the idea of a
chosen-plaintext attack covers these types of cases:
1) One is an authorized user of a system that has other users as well,
each with their own key. By choosing your plaintexts, you could, with
a chosen-plaintext attack, discover the actual key used for the system
to communicate with you, which would then be a first step (a single
known plaintext) in attacking the key distribution system to read the
communications of other authorized users.
2) In the case of a known-plaintext attack, it might be that one has
sufficient known plaintext that plaintexts with desirable
characteristics are included among those known. Thus, a cipher that is
vulnerable to a chosen-plaintext attack is also vulnerable to a
known-plaintext attack with sufficient known plaintext: and, hence, it
is desirable to have security against a chosen plaintext attack, even
if mounting such an attack directly is not actually practical.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Reasonably secure OTP passing
Reply-To: [EMAIL PROTECTED]
Date: Sat, 20 May 2000 13:45:20 GMT
Bradley King <[EMAIL PROTECTED]> wrote:
: I had the idea that some properties of OTP could be useful in more
: conventional public key encryption. Please tell me what I'm missing
: here, there must be a loose end somewhere.
: If we pass an OTP over a public medium using a straightforward public
: key/symetric system (� la virtually all consumer internet commerce) then
: the convetionally encrypted OTP should be virtually impossible to tease
: out of the cyphertext using cryptanalysis techniques because there would
: be theoretically no order to be found, the 'plaintext' in this case
: being random noise itself.
If the attacker has known plaintext, then he can recover the OTP
keystream.
If he has a known plaintext attack on the symmetric system, he can break
it - regardless of whether the plaintext is statistically random or not.
Your scheme affects chosen plaintext attacks - by making them more
difficult.
It introduces OTP attacks on the randomness of the pad. It also
introduces the OTP's lack of plaintext diffusion - and the fact that
known plaintext directly reveals the key.
It also doubles the length of all messages.
Consider: is it really worth it?
: The point of this excercise is not to create an "unbreakable" code, but
: to make certain that a brute force attack on the symetric passing of the
: OTP itself is the best technique rather than some sort of cryptanalytic
: study of vestigal order in the cyphertext (letter frequency or
: whatever).
It doesn't have this effect - if that pad is subsequently used to encrypt
a message - in which case you're back to cryptanalytic study again.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Be good, do good.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Reasonably secure OTP passing
Date: Sat, 20 May 2000 14:11:27 GMT
On Fri, 19 May 2000 11:20:48 -0400, Bradley King
<[EMAIL PROTECTED]> wrote, in part:
>If we pass an OTP over a public medium using a straightforward public
>key/symetric system (� la virtually all consumer internet commerce) then
>the convetionally encrypted OTP should be virtually impossible to tease
>out of the cyphertext using cryptanalysis techniques because there would
>be theoretically no order to be found, the 'plaintext' in this case
>being random noise itself.
Right: in fact, it would be actually impossible, not just virtually.
>If we then use the OTP that both parties now have to transfer the real
>plaintext message, then this cyphertext would also have no real order
>to it (which is the magic of the OTP method, after all).
True also.
But if an eavesdropper intercepted both the message containing the
enciphered OTP, _and_ the text message enciphered with that OTP, the
two messages _together_ would still have a pattern for the
cryptanalyst to attack, just as a text message enciphered by a
conventional system would have.
This is why this method has, in general, been rejected out of hand.
Why go to all the trouble of generating so many true random numbers?
Why use up twice the bandwidth? It's so much simpler to just use a
better conventional cryptosystem.
However, this method still does make it harder for the cryptanalyst to
see the patterns, since they're divided between two messages. So, if
the OTP-enciphered message is also conventionally enciphered as well
after the OTP is added, two hard cryptosystems have to be broken based
only on a relationship between their plaintexts. And, let's suppose
that the two ciphers used are different ones with no apparent
mathematical relationship.
There are, therefore, some conditions where this *is* not such a bad
idea (it is an old idea that keeps coming up, though) but they haven't
been really explored.
Here's another thought:
Send, enciphered very thoroughly, a whole bunch of OTPs, each of which
comes with an identifying number. Now, the cryptanalyst also has to
determine which OTP one's message is related to...
and if a returning message is sent with a header (all also enciphered
thoroughly in a conventional system) identifying _two_ of the OTPs,
and starting points within them, the cryptanalyst has quite a search
task ahead before even starting the difficult job of analyzing the
correlations between two enciphered texts.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: what is the status finite automata base cryptosystems?
Reply-To: [EMAIL PROTECTED]
Date: Sat, 20 May 2000 14:02:56 GMT
Christopher Pollett <[EMAIL PROTECTED]> wrote:
: Can anyone out there tell me what the current status of finite automata
: based crypto systems?
There are a couple which describe themselves as being "finite automata".
There's the FAKPCS (Finite Automaton Public Key CryptoSystem).
I have a bibliography for this at http://alife.co.uk/ca/publickey/biblio/
It was covered in BS's AC. The early version of this was broken - but
the replacement "Modified Finite Automata Public Key Cryptosystem" appears
to be unscathed AFAIK.
Then there's Howard Gutowitz's work at:
http://www.santafe.edu/~hag/pat/pat.html This was also covered in BS's AC.
This looks quite unusual to my eyes. I am unaware of it receiving much
analytic attention.
There's a significant sense in which all modern cryptosystems are "finite
automata" - especially those designed for hardware implementation.
Those that involve large prime numbers - or much in the way of addition or
multiplication - don't often get described in this way, though.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ VIPAR GAMMA GUPPY.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Base Encryption: Revolutionary Cypher
Reply-To: [EMAIL PROTECTED]
Date: Sat, 20 May 2000 14:16:27 GMT
wtshaw <[EMAIL PROTECTED]> wrote:
: In article <[EMAIL PROTECTED]>, Eric Lee Green
: <[EMAIL PROTECTED]> wrote:
:>....All bases can be represented in base 2, albeit with some
:> wasted bits for odd-number (non-power-of-2) bases. Adding other bases thus
:> can be considered to be a very crude block-cipher diffusion mechanism, i.e., a
:> mechanism for diffusing bits across a larger field of bits, with some
:> properties that make it decidedly inferior to most such mechanisms for
:> transforming bits (for one thing, a 1-bit change in the input does not have
:> the desired avalanche property).
: You are quoting dogma which happens to be mathematically wrong. Base 2 is
: only fundamental to other powers of two.
You are attacking a position which was never presented.
Eric never said: "base 2 is only fundamental to other powers of two."
He said: "All bases can be represented in base 2", which may be unclear -
but is unlikely to be wrong.
I would interpret it as meaning "any number, in any base can be
represented in base 2".
: Avalanching defined in bits has nothing to do with other bases. [...]
The idea is that "flipping a bit" corresponds to making a small change in
the input. With many popular computer based forms of information, this
characterisation is good enough.
If a systems fails to have proper avalanche properties when viewed from
the perspective of base 2, it's likely to be completely stuffed.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Be good, do good.
------------------------------
From: [EMAIL PROTECTED] (Jonathan Thornburg)
Subject: Re: Chosen plaintext attack, isn't it absurd?
Date: 20 May 2000 16:54:00 +0200
On Wed, 17 May 2000 15:42:28 +0200, "Manuel Pancorbo"
<[EMAIL PROTECTED]> asked:
>I mean, if the attacker is able to access the encipher machinery (but not
>the actual key) and then test the ciphertexts she wants, what stops her to
>access the DEcipher machinery?
The attacker can often see the ciphertext from chosen plaintexts,
*without* accessing the crypto machinery itself.
For example, consider an IPsec system between two hosts. An attacker
may be able to send an E-mail message to host #1, addressed to an address
at host #2. Host #1 will then forward the message to host #2. If the
attacker can sniff the #1 <--> #2 wire, then she can see the ciphertext
corresponding to the (chosen-plaintext) mail message.
Or, consider the encrypted link between country A's embassy in country B,
and country A's national government back home. If the B government hands
A's ambassador an important diplomatic note, the A embassy may well encrypt
this and send it back home. Since B got to *choose* the plaintext of
the diplomatic note, B has only to spy on the A-embassy --> A-home link
to see the ciphertext corresponding to this chosen-plaintext.
--
-- Jonathan Thornburg <[EMAIL PROTECTED]>
http://www.thp.univie.ac.at/~jthorn/home.html
Universitaet Wien (Vienna, Austria) / Institut fuer Theoretische Physik
"If security is set to none, everything just works."
quoted from http://msdn.microsoft.com/library/techart/msdn_signmark.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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
