Cryptography-Digest Digest #707, Volume #12 Mon, 18 Sep 00 10:13:01 EDT
Contents:
Re: Chosen and known attacks - are they possible ?? (David Blackman)
Encryption Algorithms for 3GPP Security (Andrew Poh)
Re: wince encryption algorithm (Runu Knips)
Re: QUESTION ABOUT ALGORITHMS (Runu Knips)
Rik Kershaw-Moore/Intl/Herman Miller is out of the office. ("Rik Kershaw-Moore")
Re: QUESTION ABOUT ALGORITHMS (Runu Knips)
Re: Double Encryption Illegal? (Runu Knips)
Re: another nonlinear decorrelation idea (Runu Knips)
Questions about how to run a contest (Sylvain Martinez)
Re: Chosen and known attacks - are they possible ?? ([EMAIL PROTECTED])
Web-based archaeology course (Mikey)
Hamming weight ("kihdip")
Re: Chosen and known attacks - are they possible ?? (Guy Macon)
Re: Questions about how to run a contest ("kihdip")
Re: MIRACL (Soeren Gammelmark)
Re: Algebra, or are all block ciphers in trouble? (Mack)
Re: Hamming weight (Mack)
Re: Questions about how to run a contest (Mack)
Re: Chosen and known attacks - are they possible ?? ("kihdip")
----------------------------------------------------------------------------
From: David Blackman <[EMAIL PROTECTED]>
Subject: Re: Chosen and known attacks - are they possible ??
Date: Mon, 18 Sep 2000 22:14:03 +1100
kihdip wrote:
>
> In 'Communications Security for the Twenty-first Century: The Advanced
> Encryption Standard' Susan Landau explains different attack models.
> <http://www.ams.org/notices/200004/fea-landau.pdf>
>
> The models are frequently used to describe an attack form:
> - Ciphertext only
> - Known plaintext
> - Chosen plaintext
> - Chosen ciphertext
>
> Forgive my ignorance, but are the known and chosen attacks only teoretical
> ?? If not: How would an attacker get a chosen plaintext encrypted ??
> (His goal is to find the key, so obviously he cannot encrypt the plaintext
> himself)
>
> Kim
Known plaintext can come up.
In many cases, standard predictable messages of some sort will be sent
using the same key as seriously secret messages. In those cases, you
often know or can guess at least small amounts of plaintext.
For instance known plaintext played a part in the British cracks of
various German cyphers in WW2. The British knew or guessed that the
Germans broadcast encrypted weather forecasts each morning on navy
radio. The same encryption method and key were used for additional
transmissions later in the day, some of them being much more secret and
important. The British had about as much idea of the weather as the
Germans did, and because the German weather forecasts were in a very
standardised format, the British could often guess exactly what the
plaintext for the weather forecast was, and then crack the cypher to get
the key of the day.
Another possibility is the attacker has bugged department A of an
organisation and knows what they are sending, but hasn't managed to bug
department B. A and B use the same cypher and key for outside
communications.
Chosen plaintext seems unlikely, but it can happen in some applications.
Imagine a communication service provider sends all messages for their
clients from point to point using an encrypted link. Attacker is
wondering what some of the client messages are. Attacker buys a contract
with the service provider, taps the encrypted communication line (it's
easy to tap, that's why the provider bothers to encrypt it :-), and
sends all the chosen plaintext they like.
Chosen cyphertext seems even more unlikely, but i can imagine some
situations where even this might happen.
Good modern cyphers attempt to be secure even if the attacker has
obtained enormous amounts of known plaintext, chosen plaintext, or
chosen cyphertext. Loki 97 was dropped from the AES competition because
Rijmen and Knudsen found a way to crack it with about 2 to the power of
56 blocks of known plaintext (that's millions of full hard discs).
------------------------------
From: Andrew Poh <[EMAIL PROTECTED]>
Subject: Encryption Algorithms for 3GPP Security
Date: Mon, 18 Sep 2000 18:55:39 +0800
I am new to this newsgroup, so kindly forgive me if this question
has been posted and answered before in the past.
Basically, I am interested to know if there any any information
or pointers to the f1, f2, f3, f4, f5 function in the 3GPP Technical
Specs
TS 33.102.
The exact algorithm is not specified in the standards and I believe
it will be up to the implementors to come up with the algorithm.
However, I wish to know what are the possible algorithms that
others may have encountered which satisfy the requirements
given in the standards.
I am aware of the Confidentiality Algorithm f8 and the Integrity
Algorithm f9, which is based on the KASUMI algorithm.
I would appreciate any information or feedback you may have.
Kindly CC all replies to my e-mail address as well.
Thanks in advance.
Regards,
Andrew
--
ANDREW POH E-mail: [EMAIL PROTECTED]
------------------------------
Date: Mon, 18 Sep 2000 13:26:47 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: wince encryption algorithm
Nomen Nescio wrote:
>
> This is the secret Ace (and WinAce) encryption algorithm. It is a
> combination of a Blowfish derivation and a SHA-1 derivation and it
> uses Cipher Block Chaining. I called it AceFish therefore...
>
> This code will only work on machines with Intel byte order! It
> shouldnt be too difficult to adapt it for Motorola byte order,
> anyway.
But I miss all the ';', '{', '}', '^' etc characters ???
It is very hard to read this way.
Why have they be deleted ???
> void AceFish::hash(const char str, u32 hash5)
> u32 w80 = 0
>
> int len = strlen(str)
> memcpy(w, str, len)
> ((unsigned char)w)len = 0x80
> w15 = 8len
>
> hash0 = 0x67452301UL hash1 = 0xEFCDAB89UL
> hash2 = 0x98BADCFEUL hash3 = 0x10325476UL
> hash4 = 0xC3D2E1F0UL
>
> int t
> for (t = 16 t < 80 t++)
> wt = wt-3 wt-8 wt- 14 wt-16
>
> u32 a = hash0, b = hash1, c = hash2, d = hash3,
> e = hash4
>
> for (t = 0 t < 20 t++)
> u32 temp = ((a << 5) (a >> 27)) + ((b c) (~b d)) +
> e + wt + 0x5A827999UL
> e = d d = c c = (b << 30) (b >> 2) b = a a = temp
>
> for (t = 20 t < 40 t++)
> u32 temp = ((a << 5) (a >> 27)) + (b c d) + e +
> wt + 0x6ED9EBA1UL
> e = d d = c c = (b << 30) (b >> 2) b = a a = temp
>
> for (t = 40 t < 60 t++)
> u32 temp = ((a << 5) (a >> 27)) +
> ((b c) (b d) (c d)) + e +
> wt + 0x8F1BBCDCUL
> e = d d = c c = (b << 30) (b >> 2) b = a a = temp
>
> for (t = 60 t < 80 t++)
> u32 temp = ((a << 5) (a >> 27)) + (b c d) + e +
> wt + 0xCA62C1D6UL
> e = d d = c c = (b << 30) (b >> 2) b = a a = temp
>
>
> hash0 += a hash1 += b hash2 += c
> hash3 += d hash4 += e
------------------------------
Date: Mon, 18 Sep 2000 13:39:05 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: QUESTION ABOUT ALGORITHMS
Melinda Harris wrote:
> Can anyone tell me how to patent an algorithm. Where to go.
Guess what - patent office.
> What to sign and how much it costs???
Well their formulas and it costs AFAIK much. I've heard
60.000 deutschmarks for a europe-wide patent for a year.
But if you want to patent a cryptographic algorithm, you're
either a moron or an idiot. A moron if you want to sell
to people what you know they can get for free, or an idiot
if you think there are not already enough free algorithms.
> Any response would be greatly appreciated
Hardly. I've insulted you.
------------------------------
From: "Rik Kershaw-Moore" <[EMAIL PROTECTED]>
Subject: Rik Kershaw-Moore/Intl/Herman Miller is out of the office.
Date: Mon, 18 Sep 2000 12:07:57 +0100
I will be out of the office from 18/09/2000 until 04/10/2000.
I am on annual leave until 4th October. If you have any urgent issues
please contact one of the other members of the IS team.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Mon, 18 Sep 2000 13:40:10 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: QUESTION ABOUT ALGORITHMS
Big Boy Barry wrote:
> If someone publsihes an algorithm, can someone else patent it?
No.
In most countries, you can't even patent an algorithm which
has already been published. Even if the publisher was you
yourself.
------------------------------
Date: Mon, 18 Sep 2000 13:53:44 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Crossposted-To: comp.databases.oracle
Subject: Re: Double Encryption Illegal?
Mok-Kong Shen wrote:
>
> Tom St Denis wrote:
> >
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > >
> > >
> > > Tom St Denis wrote:
> > > >
> > > > [EMAIL PROTECTED] (Paul Schlyter) wrote:
> > >
> > > > > So you're claiming that triple-DES is no more secure than single-
> > > > DES ???
> > > >
> > > > Read my message. Geez. I said "double" encryption is not the way
> > to
> > > > go about added security.
> > >
> > > Could you be more explicit and explain why? Are you
> > > saying that superencipherment is always nonsense?
> > > Is 2-DES not better than DES?
> >
> > Given sufficient memory 2-des is not better then des.
>
> Please exlpain your claim or refer to literature.
That is the reason why people use 3DES, and never 2DES.
Well this has been explained, for example, in Bruce Schneiers
Applied Crypto. At least I think so ;-), I don't have it at
hand in the moment. There is an attack which requires masses
of memory, but then you can attack 2DES by attacking it from
both ends (meet-in-the-middle-attack).
It is also explained in my other crypto book, "Abendteuer
Kryptologie" (Adventure Cryptology), by Reinhard Wobst,
Addison Wesley, ISBN 3-8273-1413-5, page 192ff.
I think every not too short book which discusses DES would
contain this proof.
------------------------------
Date: Mon, 18 Sep 2000 13:58:13 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: another nonlinear decorrelation idea
Tom St Denis wrote:
> In article <8pvvkr$ouc$[EMAIL PROTECTED]>,
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> > In article <8pvt4c$mdv$[EMAIL PROTECTED]>,
> > Tom St Denis <[EMAIL PROTECTED]> wrote:
> > > In GF(65537) we can use F(x) = ax^3 + b (mod 65537) which has an
> > > inverse function given by F'(x) = ((x - b)/a)^43691 (mod 65537)
> > > which means it's a bijection. Although cubing requires at least
> > > two multiplications (square, mult) or three mults in total (the
> > > entire function) it shouldn't be terribly slow.
> > >
> > > Similarly in GF(257) we find 3(171) mod 256 = 1 thus it too would be
> > > function. Again this can be precomputed as a lookup table.
> > >
> > > In fact couldn't this extend to higher orders? I am bit shaky on
> > > this however, is the only requirement that the exponents have
> > > inverses? Such as F(x) = ax^7 + bx^5 + cx^3 + d (mod 2^k + 1)
> >
> > I must be missing something... x^3 mod 17 is a bijection but not x^3
> > mod 257. I know that 3(171) mod 256 is 1, so shouldn't the operation
> > be invertable?
>
> Doh, stupid me... an eight bit number to the fifth power >2^32 ...
> hehehe
>
> BTW let's consider
>
> F(x) = (a/x + b)^c mod (2^k + 1) where 2^k+1 is prime, a!=0 and c is an
> odd element. the key space is thus (127)(256)(255) = 23 bits.
>
> Question does each value of 'c' lead to a unique permutation? for
> example is there an a^b = a^c for b != c?
*ROTFL*
Tom you're the first person I've ever seen which talks with
himself over a newsgroup ;-)
------------------------------
From: Sylvain Martinez <[EMAIL PROTECTED]>
Subject: Questions about how to run a contest
Date: Mon, 18 Sep 2000 12:11:40 GMT
Hi,
I am actually running a contest to crack a crypto algorithm but I would
like to know if the information I give away is enough to check if the
algorithm is secure or not.
Here is the information I give:
- Source code of the algorithm
- Documentation
- 2 crypted texts which have been crypted with the same key
- size of the key that has been used
- Nature of the original text.
The contest is: find the 2 original texts.
Is this enough to check the quality of a cryptography algorithm ?
Maybe I should change this contest slightly and:
- Also give the 2 original texts
- Ask to find the key that has been used
But wouldn't be too easy then ?
Is this better to check the strength of a cryptography algorithm ?
For more information please go to: http://www.bcrypt.com
Regards,
Sylvain.
---
Unix security administrator
BUGS crypto project: http://www.bcrypt.com
http://www.encryptsolutions.com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Chosen and known attacks - are they possible ??
Date: Mon, 18 Sep 2000 12:05:51 GMT
In article <8q4pq6$9co$[EMAIL PROTECTED]>,
"kihdip" <[EMAIL PROTECTED]> wrote:
> In 'Communications Security for the Twenty-first Century: The Advanced
> Encryption Standard' Susan Landau explains different attack models.
> <http://www.ams.org/notices/200004/fea-landau.pdf>
>
> The models are frequently used to describe an attack form:
> - Ciphertext only
> - Known plaintext
> - Chosen plaintext
> - Chosen ciphertext
>
> Forgive my ignorance, but are the known and chosen attacks only teoretical
> ?? If not: How would an attacker get a chosen plaintext encrypted ??
> (His goal is to find the key, so obviously he cannot encrypt the plaintext
> himself)
>
Known plaintext attacks are common for files of a known format, e.g. if I
know the document is a word document then it has a certain header. Chosen
plaintext attacks are possible in a couple of ways: with PKI the attacker has
the public key and so chosen plaintext attacks are trivial. With symmetric
encryption the chosen plaintext attack is trickier, but you could imagine a
situation whereby an attacker could influence what is encrypted by the victim
in some way, e.g. by sending them a document that they know the victim will
re-encrypt and forward on to other parties. Dubious, admittedly, but
possible.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mikey <[EMAIL PROTECTED]>
Subject: Web-based archaeology course
Date: Mon, 18 Sep 2000 11:07:21 +0100
Hi,
Another article has been complied for the archaeology web-based
course: on the origins of sedentary life and food production in the
Near East.
Course cost: �70 / $100
Start date: 23 October
Course e-mail: [EMAIL PROTECTED]
Michael Brass
Archaeology SocSci(Hons), University of Cape Town
===================
http://www.users.directonline.net/~archaeology
------------------------------
From: "kihdip" <[EMAIL PROTECTED]>
Subject: Hamming weight
Date: Mon, 18 Sep 2000 14:38:36 +0200
Does anybody have an exact definition of 'Hamming weight' ??
(and knowledge of what 'unit' to use - do you say 0,5 ; 50% or something
else ??)
Is a Hamming weight of 0,5 necessarily the goal for every cipher ??
Kim
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Chosen and known attacks - are they possible ??
Date: 18 Sep 2000 12:40:09 GMT
> "kihdip" <[EMAIL PROTECTED]> wrote:
>> In 'Communications Security for the Twenty-first Century: The Advanced
>> Encryption Standard' Susan Landau explains different attack models.
>> <http://www.ams.org/notices/200004/fea-landau.pdf>
>>
>> The models are frequently used to describe an attack form:
>> - Ciphertext only
>> - Known plaintext
>> - Chosen plaintext
>> - Chosen ciphertext
Chosen ciphertext? What is that?
------------------------------
From: "kihdip" <[EMAIL PROTECTED]>
Subject: Re: Questions about how to run a contest
Date: Mon, 18 Sep 2000 14:52:27 +0200
The information you surply will determine which attacks you'll allow.
If you want to test your ciphers strength, you should surply the plaintext
and the ciphertext and ask for the key. - This gives the attackers bigger
opportunities.
But even with the plaintext and ciphertext it is extremely difficult (if you
have written a good cipher) - Normally lots of plaintext/ciphertext pairs
encrypted with *the same* key has to be used to break the cipher.
(I guess it also depends on how willingly you'll let go of your 50 pounds
;-) )
Kim
Sylvain Martinez wrote in message <8q50pf$6kq$[EMAIL PROTECTED]>...
> Hi,
>
>I am actually running a contest to crack a crypto algorithm but I would
>like to know if the information I give away is enough to check if the
>algorithm is secure or not.
>
------------------------------
From: Soeren Gammelmark <[EMAIL PROTECTED]>
Subject: Re: MIRACL
Date: Mon, 18 Sep 2000 14:54:22 +0200
I do not have tasm32.exe, and I don't know where to get it so i tried to
compile after defining MR_NOASM in mirdef.h, but this didn't help a bit.
Now I seem to get the samme error messages as before plus additional
warnings in several different source files.
SG
John Myre wrote:
> Soeren Gammelmark wrote:
> <snip>
> >
> > Error: Unable to execute command 'tasm32.exe'
> <snip>
>
> Do you have tasm32.exe? That's the assembler; it doesn't come
> with every version of the compiler. Presumably certain of the
> source files have embedded assembly statements. Therefore
> either you have to get the assembler, or perhaps there is a
> configuration value somewhere to compile without it. Check
> the sources that cause the error and find the assembly code;
> see if there is a conditional compilation (probably using
> #ifdef) to avoid it. Etc.
>
> JM
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Algebra, or are all block ciphers in trouble?
Date: 18 Sep 2000 13:41:36 GMT
>Well, I've added a new page to my site:
>
>http://home.ecn.ab.ca/~jsavard/co041206.htm
>
>in which I try to generalize from the fact that, given an invertible
>f-function, it is trivial to solve for the subkeys from known
>plaintext for a two-round Feistel cipher, to solving a four-round one
>with two known plaintexts, an eight-round one with four known
>plaintexts, and so on.
>
>I don't get very far: for four rounds, I get to:
>
>T2 = C2 XOR f( T1 XOR c1 XOR f( c2 XOR C2 XOR F( C1 XOR T1 ) ) XOR
> F( c2 XOR p2 XOR f( p1 XOR P1 XOR F( T2 XOR P2 ) ) ) )
>T1 = P1 XOR f( T2 XOR p2 XOR f( p1 XOR P1 XOR F( T2 XOR P2 ) ) XOR
> F( c1 XOR f( c2 XOR C2 XOR F( C1 XOR T1 ) ) XOR p1 ) )
>
>where p and P are the two plaintexts (p1 and p2 are the left and right
>halves), c and C the two ciphertexts, and T is the intermediate result
>after two rounds for the second plaintext/ciphertext set.
>
>F is the inverse of the f-function.
>
>So I did eliminate the subkeys and the intermediate result for the
>first known plaintext from the equations, and obtaining T would let me
>substitute in and get the subkeys trivially.
>
>But as long as f(x) is nonlinear, it appears that one cannot go
>further, and that Feistel-round block ciphers are safe.
>
>John Savard
>http://home.ecn.ab.ca/~jsavard/crypto.htm
>
>
>
The Method of Formal Coding. I recently worked some with it
myself. The dificulty is that you wind up with a number of
non-linear boolean equations that grows very rapidly with the
increase in the number of rounds. At least if f(x,k) is non-linear.
I think it can be shown that all current attacks are approximations
of the method of formal coding. I haven't developed a proof but
it seems as if there should be one.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Hamming weight
Date: 18 Sep 2000 13:47:13 GMT
>Does anybody have an exact definition of 'Hamming weight' ??
>(and knowledge of what 'unit' to use - do you say 0,5 ; 50% or something
>else ??)
>
>Is a Hamming weight of 0,5 necessarily the goal for every cipher ??
>
>Kim
>
>
Hamming weight is the number of elements of a string that differ.
It is generally applied to boolean strings but is just as applicable to
other bases.
Ciphers are generally designed to have hamming weight of 0,5 Length.
In this way they are invertible. For hash functions this is an average.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Questions about how to run a contest
Date: 18 Sep 2000 13:54:27 GMT
> Hi,
>
>I am actually running a contest to crack a crypto algorithm but I would
>like to know if the information I give away is enough to check if the
>algorithm is secure or not.
>
>Here is the information I give:
>- Source code of the algorithm
>- Documentation
>- 2 crypted texts which have been crypted with the same key
>- size of the key that has been used
>- Nature of the original text.
>The contest is: find the 2 original texts.
>
>Is this enough to check the quality of a cryptography algorithm ?
>Maybe I should change this contest slightly and:
>- Also give the 2 original texts
A number of cipher text/plaintext pairs is nessessary for more powerful
crytological tools. I would suggest a set of cipher/plain text pairs
and then one or two texts encrypted with the same key. The number of
texts should be fairly large.
>- Ask to find the key that has been used
A better method is to ask to find the plaintext for a corresponding
ciphertext. The key is sufficient to find them but not the only
method.
The best method is to award the prize to whomever comes up with
the best attack. ie. if it reduces the complexity below the number
of bits of the key to the lowest number of bits.
>
>But wouldn't be too easy then ?
>Is this better to check the strength of a cryptography algorithm ?
Yes this is an improvement.
>
>For more information please go to: http://www.bcrypt.com
>
>Regards,
>Sylvain.
>
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: "kihdip" <[EMAIL PROTECTED]>
Subject: Re: Chosen and known attacks - are they possible ??
Date: Mon, 18 Sep 2000 16:02:18 +0200
Guy Macon wrote in message <8q52f9$[EMAIL PROTECTED]>...
>> "kihdip" <[EMAIL PROTECTED]> wrote:
>
>>> In 'Communications Security for the Twenty-first Century: The Advanced
>>> Encryption Standard' Susan Landau explains different attack models.
>>> <http://www.ams.org/notices/200004/fea-landau.pdf>
>>>
>>> The models are frequently used to describe an attack form:
>>> - Ciphertext only
>>> - Known plaintext
>>> - Chosen plaintext
>>> - Chosen ciphertext
>
>Chosen ciphertext? What is that?
>
Susan Landau distinguish between chosen plaintext (the attacker chooses
which plaintext to be encrypted) and chosen ciphertext (the attacker chooses
a ciphertext to be decrypted).
(She has omitted the adaptive chosen plaintext and the adaptive chosen
ciphertext attacks)
Also see p. 41/42 in Handbook of applied cryptography
(http://www.cacr.math.uwaterloo.ca/hac/about/chap1.pdf)
Kim
------------------------------
** 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
******************************
