Cryptography-Digest Digest #453, Volume #13 Thu, 11 Jan 01 00:13:00 EST
Contents:
Re: Stream cipher (David Wagner)
Re: Differential Analysis (Tom St Denis)
Re: Can someone break this for me? (Tom St Denis)
Re: Differential Analysis (Tom St Denis)
Re: Hash/Message digest vs Signature vs MAC? (Bryan Olson)
Re: Comparison of ECDLP vs. DLP (Greggy)
Re: Comparison of ECDLP vs. DLP (Greggy)
Re: Comparison of ECDLP vs. DLP (Greggy)
Re: NSA and Linux Security (David Wagner)
COM Wrappers for PGP (grt)
Re: Stream cipher (David Hopwood)
Enigma Emulator for Palm Pilot? (Rich W.)
Re: Bluetooth security? (David Hopwood)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Stream cipher
Date: 11 Jan 2001 02:19:27 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
This is an xor of six Vigenere's, each with period about 2^16.
Thus, with 6 * 2^16 bits of known plaintext, you can break it.
You don't even need to know how each of the six generators work
(you could replace them with any other scheme with similar period,
and the attack would still work).
As a warmup, you could try considering the case where you pick N bits
at random and repeat them to get an infinite stream, then pick M bits
at random and repeat them, then output their xor. This is a breakable
with N+M bits of known plaintext. As an exercise, find the attack.
If you have trouble, you can consult the following references:
A. Sinkov, _Elementary Cryptanalysis: A Mathematical approach_.
B. Tuckerman, ``A study of the Vigenere-Vernam single and multiple
loop enciphering systems,'' IBM Research Report RC2879, 14 May 1970.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Thu, 11 Jan 2001 02:06:28 GMT
In article <93ip9q$mqq$[EMAIL PROTECTED]>,
Rex Stewart <[EMAIL PROTECTED]> wrote:
> In article Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> >
> > table[256][256] = { 0 };
> > for (x = 0; x < 256; x++)
> > for (y = 0; y < 256; y++)
> > ++table[x^y][sbox[x]^sbox[x^y]];
> >
> > Then scan the table for the highest element (ignoring table[0][0]).
> >
> > (Can you tell I program in C? hehehehe)
> >
> > Tom
> >
> I suspect you think in C.
> I wonder, do you dream in C?
> I first ran into this phenomenon with MPJ's explanation
> of his Ruby Cipher. I understand the phenomenon better
> nowadays, but it is a bit annoying to those of us who
> have trouble reaching above pseudo code :-)
> (also makes me a bit envious)
I express mechanical ideas best in technical langs... like C :-)
The algorithm is rather simple though... just make a 2D array
(0..2^n-1)(0..2^n-1) and increment the element pointed to by
(x xor y)(sbox[x] xor sbox[x xor y])
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Can someone break this for me?
Date: Thu, 11 Jan 2001 02:08:27 GMT
In article <9F376.1600$[EMAIL PROTECTED]>,
"Andrew Thomas" <[EMAIL PROTECTED]> wrote:
> Hello,
> Could someone please break this code for me:
It says " I post random junk to the newsgroup expecting a real response!"
muhahahaha
Tom
>
> I idieeyooy a�� I�e�eai��!
>
> I�e�eai�� � the ia�a�e�oa e�e�e��o� aeeieoaaie� iadi� ia ��ie!
>
> I�d��e��o�o� I�e�eai��!
>
> Thanks a lot,
> Andrew Thomas
> [EMAIL PROTECTED]
>
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Thu, 11 Jan 2001 02:07:33 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> Tom St Denis wrote:
> >
> > In article <[EMAIL PROTECTED]>,
> > Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> > > Tom St Denis wrote:
> > > >
> > > > In article <[EMAIL PROTECTED]>,
> > > > Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> > > [snip]
> > > > > In the AES sbox, there are 23 diferentials which have a
> > > > > probability of 6/256. There are a large number of differentials
> > > > > with probability of 4/256, 2/256, and 0.
> > > >
> > > > Wrong. The highest xor-pair probability is 4/256 not 6/256.
> > >
> > > Each of these XOR pair differences occur with probability 6/256.
> > >
> > > 08->53 09->62 15->3a 26->94 28->5f 2e->52 34->73 3f->16 46->31
> > > 4d->80 57->30 5b->5a 68->26 71->c8 7a->b9 80->a6 85->f4 86->27
> > > 89->c4 ce->e8 db->d2 de->7e fe->d8
> >
> > Something is wrong in your prgoram. There are NO pairs higher then
> > 4/256 in the Rijndael sbox. It's fact given the construction of the
> > sbox. Basically the simple way to calc an xor-pair table is do this
> >
> > table[256][256] = { 0 };
> > for (x = 0; x < 256; x++)
> > for (y = 0; y < 256; y++)
> > ++table[x^y][sbox[x]^sbox[x^y]];
> >
> > Then scan the table for the highest element (ignoring table[0][0]).
> >
> > (Can you tell I program in C? hehehehe)
>
> Hmm. What I've been doing for finding XOR pairs is this:
> for (x = 0; x < 256; ++x) {
> table[256] = { 0 };
> for (y = 0; y < 256; ++y)
> ++table[sbox[x]^sbox[x^y]];
> for (z = !x; z < 256; ++z) {
> if( table[z] <= 4 ) continue;
> fprintf(f,"%02x->%02x ",x,z);
> fprintf(f,"(%d/256)\n",table[z]); }
> }
>
> Is this correct or incorrect?
Incorrect. You tell me why :-)
> Here's my AES sbox generating code (copied verbatim):
>
> unsigned char AES_sbox[256], AES_sibox[256];
>
> void AES_setup() {
> unsigned char pow[256], log[256];
> int i, j;
> for( i = 0, j = 1; i < 256; ++i ) {
> log[pow[i] = j] = i;
> // The above line does pow[i] = 3**i % 0x11b
> // and of course it's inverse.
> j ^= (j << 1) ^ ((j & 0x80) ? 0x11b : 0);
> // The above line does j = j * 3 % 0x11b
> }
> for( i = 0; i < 256; ++i ) { int k;
> j = i ? pow[255 - log[i]] : 0;
> // j is now 3**(-i) % 0x11b
> k = ((j >> 7) | (j << 1)) ^ ((j >> 6) | (j << 2));
> j ^= 0x63 ^ k ^ ((k >> 6) | (k << 2));
> // j now is an affine transform of what it was.
> AES_sibox[AES_sbox[i] = j] = i;
> }
> }
>
> Is this correct or incorrect?
>
> I suppose that either the XOR pair, or the sbox generator, is wrong, but
> I don't know which, or how.
The former is wrong.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Hash/Message digest vs Signature vs MAC?
Date: Thu, 11 Jan 2001 02:23:58 GMT
Ingmar Grahn wrote:
> > In a "signature scheme with appendix", the sign operation
> > takes a message and a key, and produces a signature. The
> > verify operation takes a message, a key and a signature, and
> > returns either "good" or "bad".
> >
> > In a "signature scheme with message recovery", the input of
> > the sign operation is (again) a message and a key, but the
> > output is a signed-message. The verify operation takes the
> > signed-message and a key, and returns either "bad" or the pair
> > ("good", message).
>
> In the "signature scheme with message recovery", you said
> the output is a "signed message". What exactly does this
> consist of?
It consists of some data. The one and only requirement
as to its content is that it work with the corresponding
verify operation. Remember that we're describing what a
signature scheme is, not how any particular scheme works.
> Isn't it just the Message+Signature that's sent to the
> recipient? In that case it sounds just like the "signature
> scheme with appendix".
Given an example of a signature scheme with appendix,
we could certainly use it build a signature scheme with
message recovery by defining the signed-message that way.
The common examples of signature schemes with message
recovery found in the literature or in standards documents
do not in fact work that way.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: Comparison of ECDLP vs. DLP
Date: Thu, 11 Jan 2001 02:34:27 GMT
In article <93fpje$3re$[EMAIL PROTECTED]>,
"Jakob Jonsson" <[EMAIL PROTECTED]> wrote:
> "Roger Schlafly" <[EMAIL PROTECTED]> wrote
> > Jakob Jonsson wrote:
> > > Proofs in the random oracle model ARE proofs of security, but you
may
> have
> > > objections against the strength of the proof.
> >
> > Stop right there. You contradict yourself. Proofs are proofs.
> > There are no objections to the strength of a valid proof.
>
> Actually, I meant that one may have objections against the strength
of the
> theorems -- if the assumptions are too strong, then the resulting
theorems
> become "weak", since they may not be applicable in many situations.
For
> example, in our case the theorem fails as soon as a bias in the hash
> function is found, because then the adversary can distinguish it from
a
> truly random function.
>
> Yet, I don't see why the proofs themselves should not be valid
proofs. It is
> hard to argue against, e.g., the conclusions in Bellare-Rogaway's RSA-
PSS
> paper. They derive "theorems" from "assumptions" via sound
mathematical
> arguments, not via heuristic arguments or hand-waving. Or do you see
a basic
> flaw in the logical chain leading from the assumptions to the
theorems?
>
> Jakob
Well, as I remember my HS geometry course, the number system we operate
with is based upon postulates - those things we accept that we
cannot "prove". For example, 1 exists, 0 exists, 1+1=2, so 2 exists,
1+2=3, etc.
Then from those postulates we can argue theorems. The theorems are
always provable IF one accepts the postulates they are based upon.
Now I would like to know what you mean by "weak". If you say that some
people can argue that "1 exists" is a weak postulate, then I think you
are in error.
--
I prefer my fourth amendment rights over a dope free
society, even if the latter could actually be achieved.
Al Gore and the Florida Robes - More than just another rock group;
a clear and present danger to America's national security.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: Comparison of ECDLP vs. DLP
Date: Thu, 11 Jan 2001 02:30:46 GMT
In article <[EMAIL PROTECTED]>,
Roger Schlafly <[EMAIL PROTECTED]> wrote:
> Jakob Jonsson wrote:
> > Proofs in the random oracle model ARE proofs of security, but you
may have
> > objections against the strength of the proof.
>
> Stop right there. You contradict yourself. Proofs are proofs.
> There are no objections to the strength of a valid proof.
Well, it truly depends on what the word "proof" means... :)
--
I prefer my fourth amendment rights over a dope free
society, even if the latter could actually be achieved.
Al Gore and the Florida Robes - More than just another rock group;
a clear and present danger to America's national security.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: Comparison of ECDLP vs. DLP
Date: Thu, 11 Jan 2001 02:36:38 GMT
In article <[EMAIL PROTECTED]>,
Roger Schlafly <[EMAIL PROTECTED]> wrote:
> Jakob Jonsson wrote:
> > > > Proofs in the random oracle model ARE proofs of security, but
you may
> > > > have objections against the strength of the proof.
> > > Stop right there. You contradict yourself. Proofs are proofs.
> > > There are no objections to the strength of a valid proof.
> > Actually, I meant that one may have objections against the strength
of the
> > theorems -- if the assumptions are too strong, then the resulting
theorems
> > become "weak", since they may not be applicable in many situations.
For
> > example, in our case the theorem fails as soon as a bias in the hash
> > function is found, because then the adversary can distinguish it
from a
> > truly random function.
>
> More precisely, it fails as soon as any particular value of a hash
> function is found, because it is then no longer a random oracle.
>
> > Yet, I don't see why the proofs themselves should not be valid
proofs. It is
> > hard to argue against, e.g., the conclusions in Bellare-Rogaway's
RSA-PSS
> > paper. They derive "theorems" from "assumptions" via sound
mathematical
> > arguments, not via heuristic arguments or hand-waving. Or do you
see a basic
> > flaw in the logical chain leading from the assumptions to the
theorems?
>
> I see you have to put "theorems" in quotes. They prove something,
> but they do not prove that RSA-PSS is secure. The security argument
> is a hand-waive.
>
That is what I was trying to get at with my last post - that if you
base your assumptions on the basic postulates of math, such as "1
exists, 1+1=2, etc.", then the theorems that can be proven based upon
those assumptions will be accepted by anyone. How strong are the
assumptions (the postulates) that underline the theorems being proposed?
--
I prefer my fourth amendment rights over a dope free
society, even if the latter could actually be achieved.
Al Gore and the Florida Robes - More than just another rock group;
a clear and present danger to America's national security.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: NSA and Linux Security
Date: 11 Jan 2001 02:55:29 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Douglas A. Gwyn wrote:
>David Wagner wrote:
>> See, e.g.,
>> http://www.gwu.edu/~nsarchiv/NSAEBB/NSAEBB23/09-03.htm
>> which shows a memo, obtained by FOIA, telling the commanding
>> officer of a military site in Sugar Grove, West Virginia that
>> one of his duties is to maintain an ECHELON site.
>
>It's not clear why that instance of "echelon" was
>capitalized, but if you examine the other documents
>on the same Web site it should be apparent that in
>them "echelon" was used with its dictionary meaning.
That could be.
But aren't there also some reasons to find it more plausible
that the memo is referring to an intelligence collection program
called ECHELON?
In outline form, the relevant memo excerpt says
(b) Perform the following specific functions and tasks:
(1) Maintain and operate an ECHELON site.
(2) XXX process and report intelligence information XXX
(3) Ensure the privacy of US citizens are properly safeguarded
pursuant to the provisions of USSID 18.
...
It seems that USSID 18 refers to restrictions on communications
intercepted by the NSA that involve any US person.
If this is a completely ordinary military site, and the word
"ECHELON" was just a typo for "echelon", there are several questions
that come to mind. Why does this part of the memo talk about
processing intelligence information? Why does it refer to USSID 18,
which is intended for the NSA? Why does it say that the duty of the
site is to provide support to the Director of the NSA? Is it plausible
to conclude that it's just a coincidence that the same base to have a
"echelon"/"ECHELON" typo is also engaged in intelligence for the NSA?
I don't know. Maybe there are perfectly satisfactory answers to all
those questions. It could be.
In any case, whether or not there really is/was a NSA interception
program codenamed ECHELON fundamentally doesn't seem to matter too much.
People are most concerned about the NSA's global interception practices,
not about what the name of the project is.
Do you agree?
------------------------------
From: [EMAIL PROTECTED] (grt)
Crossposted-To: alt.security.pgp
Subject: COM Wrappers for PGP
Date: 11 Jan 2001 02:40:46 GMT
FYI
http://community.wow.net/grt/nsdpgp.html
PGPSTRING.DLL version 1.0
Freeware. Freely distributable.
PGPSTRING is a COM Object and Interface to PGP version 6.5.8.
It provides methods for String encryption and decryption to clients such
as Visual Basic, ASP, the Windows Scripting Host, Delphi etc.
The previously released NSDPGP COM Object provides methods for file
encryption/decryption/signing/verification/wiping.
--
Gerard R Thomas
Port of Spain, Trinidad and Tobago
mailto:[EMAIL PROTECTED] mailto:[EMAIL PROTECTED]
PGP Key IDs: RSA:0x9DBCDE7D DH/DSS:0xFF7155A2
------------------------------
Date: Thu, 11 Jan 2001 04:18:23 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Stream cipher
=====BEGIN PGP SIGNED MESSAGE=====
Simon Johnson wrote:
> Now, this cipher is designed to take a 96-bit key. The key is divided
> into 16-bit portions. Working from the MSB to the LSB the first 16-bits
> are put into the varible, A, the second 16-bits into variable, B, the
> third 16-bits into the variable, C and so on..... from A -> F
>
> Once this is done, clock the cipher once, and we are ready to start.
> To clock, do the following simple procedure:
>
> a = (a * 7) Mod 65537
> b = (b * 3) Mod 65539
> c = (c * 11) Mod 65543
> d = (d * 13) Mod 65551
> e = (e * 5) Mod 65557
> f = (d * 17) Mod 65563
Is that really supposed to be d * 17 in the last line, or is it f * 17?
Assuming it is f (d would be even weaker), there is a trivial 2^48
meet-in-the-middle attack, because the cipher is of the form
h_K2(g_K1(plaintext)), with K1 and K2 of length only 48 bits.
There are better attacks, I think, but there is not really much point
in considering a cipher that falls to a simple meet-in-the-middle attack
any further.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOl0zrzkCAxeYt5gVAQGTpAf+NphladNfSNn7I92gOBtkssu6AGvdjZbN
5m2/2kXlqbS/7bu81ZVE4Vei8Ul2517dsuEoRPTbSiDTNjG9VhSABgUeQAhXHf5b
4BeE8mrFpNGV19ad3Ygxz8vW0pC2oCvj+RAZpwCJW3nBrK3xI8nCz5yulpOHUhm/
z9WULALz07GRBLr2i5OCIIDwYVTQdtKLqHujSkcgDiK3OgSqkC3jY6p5Zdclwg45
iNKLQAYoh7k47RD0wAAedB+JnQIO5fgO9u7yGip2fA7SmZD3wHZZlwJ9bIvo0ZyL
U0B52rOIqHfo18EkBDPZrctqCJkIpG8YzyjEbwaeltvnaoyAld5aLQ==
=9qVy
=====END PGP SIGNATURE=====
------------------------------
From: Rich W. <[EMAIL PROTECTED]>
Subject: Enigma Emulator for Palm Pilot?
Date: Wed, 10 Jan 2001 23:29:31 -0500
Does anyone know of an Enigma Emulator for the Palm Pilot?
Thanks,
--
Rich...
------------------------------
Date: Thu, 11 Jan 2001 04:27:01 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Bluetooth security?
=====BEGIN PGP SIGNED MESSAGE=====
Benjamin Goldberg wrote:
> kihdip wrote:
> > The E0 algorithm is bluetooth specific.
> > This must be a drawback as I see it. The paper from Bell-labs
> > concludes that E0 should be replaced by another known algorithm, for
> > instance AES.
> > - Sounds reasonable.
> >
> > Kim
>
> <nitpick>Except for the fact that E0 is a stream cipher, and AES is a
> block cipher</nitpick>
Why does that matter? Bluetooth doesn't require a stream cipher, it
just happened to use one. Note that Bluetooth is a packetised protocol
that handles error correction at a different layer to security, so almost
any block cipher mode would work.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOl0VqjkCAxeYt5gVAQG1+wf+JBkmEgGCsKZIucKFi2IH52d7Fl6emgnW
IJwRV9XoNzf1Fnt7JQ/sgX3v9lOSS6rOTBR+w1qOAJ5YpW4zApR91CHIG9R5qYyu
HC2rSEDXQEfk/KfspHHR5Gk6W/RUFr3xWPy7Nruhyae7eIUwcyJE2h6OghQGV2yK
jHj9ZGRJscRmuwUqk9wNIUc5EZbKLndHt2l+w87ZMJd77DopxTn7karqyB3IhxR5
DipajwFyepAtEl0S+s9X4H2TEu2rEiwGdc23l9pZL/7PhA20P8g25/muQfq2ihYd
h8KpvSAyFePvdZaKwbbtLKU/7cTDX46gX9FaaDOSrqcpTA4+uokbGA==
=vhT7
=====END PGP SIGNATURE=====
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
