Cryptography-Digest Digest #746, Volume #13 Sun, 25 Feb 01 12:13:01 EST
Contents:
Re: New unbreakable code from Rabin? (Tim Tyler)
Re: Rnadom Numbers (Tim Tyler)
Re: Powers of Complex Associative Functions (Mok-Kong Shen)
Re: Simple, possibly flawed, stream cipher ("Henrick Hellström")
Re: Encrypted Email for Business Documents (phil hunt)
Tempest ( Doug Goncz)
Re: PGP Public Keys (Tony L. Svanstrom)
Re: Super strong crypto (William Hugh Murray)
Re: Powers of Complex Associative Functions (Jim Steuert)
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: New unbreakable code from Rabin?
Reply-To: [EMAIL PROTECTED]
Date: Sun, 25 Feb 2001 12:01:29 GMT
Markus Kuhn <[EMAIL PROTECTED]> wrote:
: The technique described in
: http://www.iht.com/articles/11245.htm
: sounds at first glance a bit like a reinvention of
: Cachin/Maurer, EUROCRYPT '97:
: ftp://ftp.inf.ethz.ch/pub/publications/papers/ti/isc/wwwisc/CacMau97b.pdf
: Just a quick note on the practicality of such schemes that rely on the
: cost of recording the wide-area broadcast of a random bit sequence:
Which is not as high as the authors seem to think and in no way justifies
their apparently ridiculous security claims :-(
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Rnadom Numbers
Reply-To: [EMAIL PROTECTED]
Date: Sun, 25 Feb 2001 12:05:01 GMT
Simon Johnson <[EMAIL PROTECTED]> wrote:
: Would I right in saying that if a crypto-secure pseudo-random generator was
: unable to be cryptanalysed until x bytes of stream were recovered then all
: of the bytes previous to the x'th byte must be statistically random? [...]
Unable to be cryptanalysed by who?
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Powers of Complex Associative Functions
Date: Sun, 25 Feb 2001 14:08:26 +0100
Jim Steuert wrote:
>
> As a tiny example, I will take the second linear function OP2.
> Here the function, as in your notation can also be expressed in
> (non-constant) matrix form
> as: [c] = [a] OP2 [b] is defined as:
>
> | c0 | | a0 0 0 a2 | | b0 |
> | c1 | | 0 a1 a3 0 | | b1 |
> | c2 | | 0 a2 a0 0 | | b2 |
> | c3 | | a3 0 0 a1| | b3 |
>
> Note that I am NOT proposing any linear function, the exact placement of
> the vector components of vector [a] in multiple places, or structure of the
> matrix A is important, as in the OP2 example above, in order to make it
> associative, which is necessary for Diffie-Hellman usage.
>
> Choosing mod 11, and plugging in values a0 = 7, a1=5, a2 = 8, a3 = 3,
> makes the matrix A non-singular (since det A = a0*a1*a0*a1 = 4 mod 11).
> Note that the matrix IS NOT THE FUNCTION.
>
> | c0 | | 7 0 0 8 | | 7 |
> | c1 | | 0 5 3 0 | | 5 |
> | c2 | = | 0 8 7 0 | | 8 |
> | c3 | | 3 0 0 5 | | 3 |
>
> therefore: a^2 = [7 5 6 3] mod 11
I suppose you have a computing error. 8*5+7*8 = 8 mod 11,
so one has a^2 = [7 5 8 3] = a. (a happens to be the
'eigenvalue'.)
> now, plugging these into the formula: a^2 =
> | a0 0 0 a2 | | a0 |
> | 0 a1 a3 0 | | a1 |
> | 0 a2 a0 0 | | a2 |
> | a3 0 0 a1| | a3 |
> we get a^4 =
> | 7 0 0 6 | | 7 |
> | 0 5 3 0 | | 5 |
> | 0 6 7 0 | | 6 |
> | 6 0 0 5 | | 3 |
> ==> [ 1 10 6 2 ] mod 11
> and so on for arbitrarily higher powers of vector [a] using OP2.
> Since they are associative, we can create a^6 = a^4 OP2 a^2,
> so we can form any power by multiplying (OP-ifying) the
> already-built powers. Thus we can simply create a huge power
> of vector [a] in logarithmic time.
You have defined formally the square of a and, as you said,
that can be any non-linear function. How do you prove
that in the non-linear case the operator op2 is associative?
Thanks.
M. K. Shen
------------------------------
From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: Simple, possibly flawed, stream cipher
Date: Sun, 25 Feb 2001 15:00:01 +0100
"Scott Fluhrer" <[EMAIL PROTECTED]> skrev i meddelandet
news:979pvj$h6s$[EMAIL PROTECTED]...
>
> Henrick Hellström <[EMAIL PROTECTED]> wrote in message
> news:979p9h$afm$[EMAIL PROTECTED]...
<---snip--->
> > Furthermore, for the average arbitrary sbox about half of the values x
in
> > the interval [0..255] does not have a solution s in the equation x =
> sbox[s]
> > xor sbox[s+1]. This fact helps to eliminate some valid occurances
without
> > necessarily counting their frequency.
> However, other values of x have multiple solutions. If you choose x
> randomly, the expected number of solutions corresponding to that x is
> precisely 1. Hence, if you have 1000 potential values of x, you would
> expect that to lead to about 1000 solutions. Or at least, such was my
> reasoning.
Hm... I don't get this part right. Check out the pascal code (to be more
precise: Delphi code) below. I tried it with 1025 outputs and got a success
rate below 0.25. I tried it with 2049 outputs and got the value of state[0]
right about one half of the time and a lower success rate on
state[1],...,state[7]. It works like a charm with 4097 outputs, so I doubt
there are any pure implementation errors. Either one of us must have got
something wrong somewhere. Could you please check it out?
/.../
const
HighByte = 255;
HighState = 7;
HighOutput = 2048;
type
TSBox = array [0..HighByte] of Byte;
TInverseSBox = array [0..HighByte] of TSBox;
TFrequencies = array [0..HighByte] of Real;
TStateArray = array [0..HighState] of Byte;
TOutputArray = array [0..HighOutput] of Byte;
TDevArray = array [0..HighState] of Real;
var
i: Integer;
SBox: TSBox;
IBox: TInverseSBox;
Freq: TFrequencies;
State, Key, Guess: TStateArray;
Output, TestData: TOutputArray;
Dev: TDevArray;
procedure Initialize;
var
i: Integer;
begin
Randomize;
for i := 0 to HighByte do
Freq[i] := 0;
end;
procedure CreateSBox(var ASBox: TSBox; var AIBox: TInverseSBox);
var
i: Integer;
x, y, dx: Byte;
Taken: set of Byte;
begin
for i := 0 to HighByte do
AIBox[i,0] := 0;
Taken := [];
for i := 0 to HighByte do begin
repeat
x := Random(HighByte + 1);
until not (x in Taken);
Taken := Taken + [x];
ASBox[i] := x;
if i > 0 then begin
dx := x xor y;
AIBox[dx,0] := AIBox[dx,0] + 1;
AIBox[dx,AIBox[dx,0]] := i;
end;
y := x;
end;
dx := ASBox[0] xor y;
AIBox[dx,0] := AIBox[dx,0] + 1;
AIBox[dx,AIBox[dx,0]] := 0;
end;
procedure CreateInitialState(var AKey, AState: TStateArray);
var
i: Integer;
begin
for i := 0 to HighState do begin
AState[i] := Random(256);
AKey[i] := AState[i];
end;
end;
procedure CreateOutput(const ASBox: TSBox;
var AState: TStateArray;
var AOutput: TOutputArray);
var
i, j: Integer;
x: Byte;
begin
for j := 0 to HighOutput do begin
x := 1;
for i := 0 to HighState do begin
if Odd(x shr i) then AState[i] := (AState[i] + 1) mod 256;
x := x xor ASbox[AState[i]];
end;
AOutput[j] := x;
end;
end;
procedure Analyze1(const AOutput: TOutputArray;
const ASBox: TSBox;
const AState: TStateArray;
const Index: Integer;
const AIBox: TInverseSBox;
var AFreq: TFrequencies);
var
i, j, k, count, offset: Integer;
s: TStateArray;
x, y, dx: Byte;
df: Real;
yval: Boolean;
begin
for i := 0 to Index - 1 do
s[i] := AState[i];
s[Index] := 0;
yval := False;
for j := 0 to HighOutput do begin
x := 1;
for i := 0 to Index-1 do begin
if Odd(x shr i) then s[i] := (s[i] + 1) mod 256;
x := x xor ASBox[s[i]];
end;
if Odd(x shr Index) then begin
s[Index] := (s[Index] + 1) mod 256;
Offset := 256 - s[Index];
x := x xor AOutput[j];
if yval then begin
dx := x xor y;
count := AIBox[dx,0];
if count > 0 then begin
for i := 1 to count do begin
k := (AIBox[dx,i] + offset) mod 256;
Freq[k] := Freq[k] + 1/count;
end;
end;
end;
y := x;
yval := True;
end;
end;
end;
function Analyze2(var AFreq: TFrequencies;
var ADev: Real): Byte;
const
micro = 1/256;
var
maxf, sum: Real;
i: Integer;
begin
maxf := AFreq[0];
sum := maxf;
Result := 0;
AFreq[0] := 0;
for i := 1 to HighByte do begin
if AFreq[i] > maxf then begin
maxf := AFreq[i];
Result := i;
end;
sum := sum + AFreq[i];
AFreq[i] := 0;
end;
ADev := Abs(maxf/sum - micro)/micro
end;
begin
(* Initialization: *)
Initialize;
CreateSBox(SBox,IBox);
(* Create key to be attacked: *)
CreateInitialState(Key,State);
(* Create output to be attacked: *)
CreateOutput(SBox,State,Output);
(* Perform attack: *)
for i := 0 to HighState do begin
Analyze1(Output,SBox,Guess,i,IBox,Freq);
Guess[i] := Analyze2(Freq,Dev[i]);
end;
(* Check result: *)
for i := 0 to HighState do
State[i] := Guess[i];
CreateOutput(SBox,State,TestData);
i := 0;
while (i <= HighOutput) and (TestData[i] = Output[i]) do
Inc(i);
if i > HighOutput then
Memo1.Lines.Add('Success')
else
Memo1.Lines.Add('Failure');
(* Show result and some stats: *)
for i := 0 to HighState do
Memo1.Lines.Add(Format('%d - %d - %f',[Key[i],Guess[i],Dev[i]]));
Memo1.Lines.Add('---');
end;
--
Henrick Hellström [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: [EMAIL PROTECTED] (phil hunt)
Crossposted-To: alt.sources.crypto,talk.politics.crypto
Subject: Re: Encrypted Email for Business Documents
Date: Sun, 25 Feb 2001 13:53:28 +0000
On Sun, 25 Feb 2001 07:10:48 GMT, Peter Harrison <[EMAIL PROTECTED]> wrote:
>On Fri, 23 Feb 2001 16:56:58 -0800, "Joseph Ashwood" <[EMAIL PROTECTED]>
>wrote:
>
>>[send to both newsgroups and personal e-mail]
>>I've taken a cursory look at your idea, and there are several areas in which
>>it seems to be lacking.
>>
>>First why this is not a good idea. There is nothing special about business
>>documents as opposed to every other type of document that is already
>>encrypted (much like business documents are) using either PGP or similar
>>technology.
>
>If there is a common library for Delphi, Java, C/C++ and Visual Basic
>that is open source I would certainly like to hear about it.
If you want to write asn open source system, I wouldn't use VB as
that is inherently proprietary, and there is no open source implementation
of it.
(The open source equivalent of PGP is GPG (Gnu Privacy Guard)
which I expect is written in C or C++.)
If I were you, I would also be learning towards Unix-type systems
rather than the proprietary Microsoft environment. Actually, I'd
probably use Python for all by the most processor-intensive and
C++ for the rest; that way I could probably get it to run on Unix/Linux,
Micorsoft, Mac, etc with very little difficulty porting.
> I would
>be happy to use PGP if there were common implementations in all
>languages. Because there isn't I face either writing my own
>technology or implementing PGP by myself.
Consider GPG.
>>The fact that you do not encrypt the message just the attachments is a
>>distinct disadvantage of your system as opposed to every other system of
>>it's type in general use.
>
>Perhaps if I was designing a generic email encryptor you might have a
>point. However this system is specifically for sending Documents.
And how does this differ from email in general?
>I am looking at using PGP, however PGP doesn't address some of the
>issues I am trying to solve.
>
>Issues revolve around difficulty of use. Most encryption systems
>require users to obtain public keys through a manual process. My
>implementation obtains public keys when a email is sent without user
>intervention. With PGP there is a user intervention to download keys.
You might like to consider writing an easy-to-use wrapper around GPG.
--
*****[ Phil Hunt ***** [EMAIL PROTECTED] ]*****
"Mommy, make the nasty penguin go away." -- Jim Allchin, MS head
of OS development, regarding open source software (paraphrased).
------------------------------
From: [EMAIL PROTECTED] ( Doug Goncz )
Date: 25 Feb 2001 14:41:21 GMT
Subject: Tempest
Found with google searching for "Tempest":
The Complete, Unofficial TEMPEST Information Page. Celebrating four years
of public disclosure, and one-stop shopping for TEMPEST info... ...
Description: The most comprehensive source of TEMPEST information on the Net.
Category: Computers > Hacking > HERF, EMP, Tempest
www.eskimo.com/~joelm/tempest.html - 18k
Can you recommend any other Tempest pages? Are the US federal government still
actively solicitating development of Tempest hardware?
Is Tempest hardware a suitable topic for scr?
Yours,
Doug Goncz
------------------------------
Subject: Re: PGP Public Keys
From: [EMAIL PROTECTED] (Tony L. Svanstrom)
Date: Sun, 25 Feb 2001 15:23:43 GMT
John Atkins <[EMAIL PROTECTED]> wrote:
> If I wanted to decode all the information about a PGP key, how would I do
> it?
<ftp://ftp.ox.ac.uk/pub/crypto/pgp/utils/pgpacket3.1.pl.gz>
/Tony
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Super strong crypto
Date: Sun, 25 Feb 2001 16:30:13 GMT
wtshaw wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> >
> > From where this amateur sits, differential cryptanalysis is a very
> > powerful tool indeed. What am I missing from where I sit?
>
> Those most skilled in using it are unlikely to tell you if a particular
> new cipher is indeed as resistant to DC as you would like.
True. However, that is my limitation, not a limitation of the tool. I
have had that problem with many scientific instruments.
>
> --
> Better to pardon hundreds of guilty people than execute one
> that is innocent.
------------------------------
From: Jim Steuert <[EMAIL PROTECTED]>
Subject: Re: Powers of Complex Associative Functions
Date: Sun, 25 Feb 2001 11:29:22 -0500
Reply-To: Jim, Steuert
You are correct, it is a computing error. And that may not be a good example
since a^2 = a is not a good seed value.
As to how I prove it is associative,
I have a c program which does the tedious substitutions, as the following output
for each equation where (0,0) means a0*b0, (2,3) means a2*b3, and so on.
Note that the left and right set of ordered triples are the same set for any
given equation. My c program searches for those. I have found many
for 3 equations with 3 pairs, for 4 equations with 2 pairs, and 4 equations
with 4 pairs, but none for 5 equations or 6 equations. There is probably a
good reason for this, founded on group theory. (A serious subject if I wanted
to delve deeper). Perhaps there is an even simpler construction based on
symmetries of a matrix (I'm looking into that now). But here is my search
programs output for a single operator:
ASSOCIATIVE TEST FOR OPERATOR:
c0 = (0,0) + (2,3)
c1 = (1,1) + (3,2)
c2 = (0,2) + (2,1)
c3 = (1,3) + (3,0)
EQN: 0
LEFT ASSOCIATIVE TEST: (AB)C
pair: (0) 0
triple: (0 0) 0
triple: (2 3) 0
pair: (2) 3
triple: (0 2) 3
triple: (2 1) 3
RIGHT ASSOCIATIVE TEST: A(BC)
pair: 0 (0)
triple: 0 (0 0)
triple: 0 (2 3)
pair: 2 (3)
triple: 2 (1 3)
triple: 2 (3 0)
Your responses got me thinking about powers of matrices.
I dpn't think that these are all equivalent to powers of matrices.
But even if they were, I think my proposed construction would be useful,
because out ot the thousands of operators that I found.
A) the specific operator can be chosen at run-time. I am assuming that
any attack would be dependent on the specific operator being used. (I would
be wrong if they can all be couched in the form of matrix powers, but even
then all combinations would have to be tried, and
B) by nesting these associative operators, i.e., if instead of simple arithmetic
mod a prime,
a similar but different associative vector operator were used for those matrix
elements, and so on for a couple of levels of nesting, then there would be
millions
of possible operators on the data. Even a general matrix discrete logarithm
attack
would require trying all of the combinations of operators to put it into
matrix form.
(to reduce the fallacy of security by obscurity)
C) I think these would not be hard to implement in a simple c program.
My question is however, is there any information on attacks on Diffie-Hellman
for associative operators other than a) multiplication mod a large prime, b)
quaternions, or c) matrix. If there is an attack for matrices in general, can you
give me any references.
Thanks for your help,
-Jim Steuert
Mok-Kong Shen wrote:
> Jim Steuert wrote:
> >
> > As a tiny example, I will take the second linear function OP2.
> > Here the function, as in your notation can also be expressed in
> > (non-constant) matrix form
> > as: [c] = [a] OP2 [b] is defined as:
> >
> > | c0 | | a0 0 0 a2 | | b0 |
> > | c1 | | 0 a1 a3 0 | | b1 |
> > | c2 | | 0 a2 a0 0 | | b2 |
> > | c3 | | a3 0 0 a1| | b3 |
> >
> > Note that I am NOT proposing any linear function, the exact placement of
> > the vector components of vector [a] in multiple places, or structure of the
> > matrix A is important, as in the OP2 example above, in order to make it
> > associative, which is necessary for Diffie-Hellman usage.
> >
> > Choosing mod 11, and plugging in values a0 = 7, a1=5, a2 = 8, a3 = 3,
> > makes the matrix A non-singular (since det A = a0*a1*a0*a1 = 4 mod 11).
> > Note that the matrix IS NOT THE FUNCTION.
> >
> > | c0 | | 7 0 0 8 | | 7 |
> > | c1 | | 0 5 3 0 | | 5 |
> > | c2 | = | 0 8 7 0 | | 8 |
> > | c3 | | 3 0 0 5 | | 3 |
> >
> > therefore: a^2 = [7 5 6 3] mod 11
>
> I suppose you have a computing error. 8*5+7*8 = 8 mod 11,
> so one has a^2 = [7 5 8 3] = a. (a happens to be the
> 'eigenvalue'.)
>
> > now, plugging these into the formula: a^2 =
> > | a0 0 0 a2 | | a0 |
> > | 0 a1 a3 0 | | a1 |
> > | 0 a2 a0 0 | | a2 |
> > | a3 0 0 a1| | a3 |
> > we get a^4 =
> > | 7 0 0 6 | | 7 |
> > | 0 5 3 0 | | 5 |
> > | 0 6 7 0 | | 6 |
> > | 6 0 0 5 | | 3 |
> > ==> [ 1 10 6 2 ] mod 11
> > and so on for arbitrarily higher powers of vector [a] using OP2.
> > Since they are associative, we can create a^6 = a^4 OP2 a^2,
> > so we can form any power by multiplying (OP-ifying) the
> > already-built powers. Thus we can simply create a huge power
> > of vector [a] in logarithmic time.
>
> You have defined formally the square of a and, as you said,
> that can be any non-linear function. How do you prove
> that in the non-linear case the operator op2 is associative?
> 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
