Cryptography-Digest Digest #168, Volume #10 Fri, 3 Sep 99 16:13:03 EDT
Contents:
Description of SQ ("Kostadin Bajalcaliev")
Description of SQ ("Kostadin Bajalcaliev")
Re: 512 bit number factored (SCOTT19U.ZIP_GUY)
Re: 512 bit number factored (D. J. Bernstein)
Different Encryption Algorithms ("entropy")
Re: Alleged NSA backdoor in Windows CryptoAPI (Stephan Eisvogel)
Re: Alleged NSA backdoor in Windows CryptoAPI (Ian Goldberg)
Re: ECC, D.S., Fravia, & Ian (Ian Goldberg)
Re: Implementing crypto algorithms in Fortran. (SCOTT19U.ZIP_GUY)
Re: Home Invasion Bill Drives U.S. Computer Users across border ([EMAIL PROTECTED])
Re: IDEA- safe? (jerome)
Re: Alleged NSA backdoor in Windows CryptoAPI (DJohn37050)
----------------------------------------------------------------------------
From: "Kostadin Bajalcaliev" <[EMAIL PROTECTED]>
Subject: Description of SQ
Date: Fri, 3 Sep 1999 20:06:18 +0200
Please send your comments about my Stream cipher. Here is only the
description. If you need more details visit
http://eon.pmf.ukim.edu.mk/~kbajalc or http://members.tripod.com/kbajalc.
============================
The SQ1 Stream Cipher
Kostadin Bajalcaliev
April 26th Street num: 14,
91480 Gevgelija, Macedonia, Europe
[EMAIL PROTECTED]
Abstract: This document describes SQ1 stream cipher. SQ1 is
Cryptographically Secure Pseudo-Random bit generator. A novel feature of SQ1
is its hybrid design, using both permutation and variation. It is simple and
easy to implement, suitable for software and hardware implementation.
1. Data Structures
SQ1 is word-oriented algorithm; any word size is supported respecting the
available memory. In order to implement SQ1 data structures below are
required: (given in C notation)
P[w] � permutation of numbers from 0 to w
V[w] � variation, every element can have any value 0 to w
Sr - feedback register
* All data types are W-bit
The word size can be some conventional value 8,16 � bits, but the formal
definition of the algorithm assume any value with respect to available
memory. In the real implementation other variables are used but they are
meter of optimization.
2. Notation and SQ Primitive Operations
SQ1 require only four primitive operations supported by major processor
families.
1. Addition of two words, denoted by �+�, addition is done modulo 2w
2. Bit-wise exclusive OR of words, denoted by XOR
3. A left-rotation of words: the rotation of word x left by y bits is
denoted x<<<y
4. Modulo, x modulo y equal z denoted x mod y = z.
A left-rotation of fields: X�[y]=X[y+z mod field_size], denoted by X<<<z is
basic operation in SQ1, it is not primitive but easily deliverable from the
primitive operations.
3. Algorithm Specification
According to definition of data structure and primitive operations here is
algorithm formal definition:
/* initialization */
for j=0 to 2w { P[j]=j; V[j]=0; }
/* generator iteration */
{1} A=P[Sr]; B=P[V[A]];
{2} V[A]=B; Swap P[A], P[B]; P<<<1;
{3} Out=P[A+B mod 2w];
{4} Sr<<<1; Sr=Sr+Out;
Return Out
SQ1 is very simple, you can encode it as a function SQ which produce values
according to its internal state. The state of the generator is defined with
P[], V[] and Sr.
The first step {1} is calculation of indexes A and B according to present
state of the generator. The second step {2} is the transformation of P[] and
V[] according to A and B, P<<<1 is default transformation (the counter). The
third step {3} is calculation of the output value, and the forth {4} step is
changing the value into feedback register.
4. Keying SQ1
SQ as most of Stream Ciphers �keying the generator� is setting the initial
state. Very simple strategy is used. The key stream is feed into Variation
V[] and the key length is feed into Sr. First 22w outputs are discarded to
worm up the generator. Here is the formal definition of keying procedure.
K[0..L] is the keystream
L is length of the keystream
r=0;
For j=0 to 2w { V[j]=K[r]; r=(r+1) mod L; }
For j=0 to 22w SQ1();
SQ1() is the generator function described before. The keystream should be
the same word size as P[] and V[] but it is allowed to be smaller to. For
example if w=14, the keystream can be conventional 8-bit character field. If
the w<8 (what is very bed idea) that the keystream should be cut in w-bit
peace in order to feed it into V. The maximal key length allowed using this
strategy is 22w bits, the length of V in bits.
5. Implementation Remarks
This is document is intended to help you implementing SQ1, if you are
interested about the design solutions read the thesis available on-line.
Because of security of the algorithm please follow these remarks:
1. SQ1 is not intending to be secure for any word size or key length. The
word size must be greater than 8bits.
2. Do not use all the bits produced by the generator, discard at least one.
If you need 8-bit values to encrypt files or communication channel use 9-bit
word. The values produced by the generator are going to be 0..511, just
discard the MSB and you have your 8-bit output.
3. Be careful chousing keys, no matter how secure SQ1 is, if the key is too
short or �usual� there is nothing GOD can do to help you
SQ1 is a fast algorithm, generating 1MB take 1.2 sec using my Celeron 300
(RC4 require 1 sec). However SQ1 offer you more security than any other
Stream Cipher.
6. Source code
Here is the source code of a simple program that encrypts file A to B using
key according to algorithm SQ1.
#include <stdio.h>
#include <string.h>
#define p(a) P[(a+R)%w2]
#define v(a) V[a%w2]
int P[4096], V[4096], Sr, R, W=9, w2=512;
int init_sq(char *keystream,int keylen);
int sq(void);
int main (int argc, char **argv)
{
FILE *inf, *outf;
int c;
if(argc==0)
{
printf("SQ [input file] [output file] [key] \n");
return 0;
}
inf=fopen(argv[1],"rb");
outf=fopen(argv[2],"wb");
init_sq(argv[3],strlen(argv[3]));
c=getc(inf);
while(!feof(inf))
{
c^=sq();
putc(c,outf);
c=getc(inf);
}
fcloseall();
return 0;
}
int init_sq(char *keystream, int keylen)
{
int i,x;
x=0;
for(i=0;i<w2;i++)
{
P[i]=i;
V[i]=keystream[x];
x=(x+1)%keylen;
}
Sr=keylen;
for(i=0;i<w2;i++) for(x=0;x<w2;x++) sq();
return 0;
}
int sq(void)
{
int A,B,c,Out;
A=p(Sr); B=p(v(A));
v(A)=B; c=p(A); p(A)=p(B); p(B)=c; R=(R+1)%w2;
Out=p(A+B);
Sr<<=1; Sr=(Sr/w2)^(Sr%w2); Sr=(Sr+Out)%w2;
return Out;
}
NOTICE
This document you can obtain from any of the following sites:
http://eon.pmf.ukim.edu.mk/~kbajalc
http://members.tripod.com/kbajalc
http://kbajalc.8m.com
If you are interest to know more details read the thesis available on the
same site.
� Kostadin Bajalcaliev 1999
------------------------------
From: "Kostadin Bajalcaliev" <[EMAIL PROTECTED]>
Subject: Description of SQ
Date: Fri, 3 Sep 1999 20:08:39 +0200
Please send your comments about my Stream cipher. Here is only the
description. If you need more details visit
http://eon.pmf.ukim.edu.mk/~kbajalc or http://members.tripod.com/kbajalc.
============================
The SQ1 Stream Cipher
Kostadin Bajalcaliev
April 26th Street num: 14,
91480 Gevgelija, Macedonia, Europe
[EMAIL PROTECTED]
Abstract: This document describes SQ1 stream cipher. SQ1 is
Cryptographically Secure Pseudo-Random bit generator. A novel feature of SQ1
is its hybrid design, using both permutation and variation. It is simple and
easy to implement, suitable for software and hardware implementation.
1. Data Structures
SQ1 is word-oriented algorithm; any word size is supported respecting the
available memory. In order to implement SQ1 data structures below are
required: (given in C notation)
P[w] � permutation of numbers from 0 to w
V[w] � variation, every element can have any value 0 to w
Sr - feedback register
* All data types are W-bit
The word size can be some conventional value 8,16 � bits, but the formal
definition of the algorithm assume any value with respect to available
memory. In the real implementation other variables are used but they are
meter of optimization.
2. Notation and SQ Primitive Operations
SQ1 require only four primitive operations supported by major processor
families.
1. Addition of two words, denoted by �+�, addition is done modulo 2w
2. Bit-wise exclusive OR of words, denoted by XOR
3. A left-rotation of words: the rotation of word x left by y bits is
denoted x<<<y
4. Modulo, x modulo y equal z denoted x mod y = z.
A left-rotation of fields: X�[y]=X[y+z mod field_size], denoted by X<<<z is
basic operation in SQ1, it is not primitive but easily deliverable from the
primitive operations.
3. Algorithm Specification
According to definition of data structure and primitive operations here is
algorithm formal definition:
/* initialization */
for j=0 to 2w { P[j]=j; V[j]=0; }
/* generator iteration */
{1} A=P[Sr]; B=P[V[A]];
{2} V[A]=B; Swap P[A], P[B]; P<<<1;
{3} Out=P[A+B mod 2w];
{4} Sr<<<1; Sr=Sr+Out;
Return Out
SQ1 is very simple, you can encode it as a function SQ which produce values
according to its internal state. The state of the generator is defined with
P[], V[] and Sr.
The first step {1} is calculation of indexes A and B according to present
state of the generator. The second step {2} is the transformation of P[] and
V[] according to A and B, P<<<1 is default transformation (the counter). The
third step {3} is calculation of the output value, and the forth {4} step is
changing the value into feedback register.
4. Keying SQ1
SQ as most of Stream Ciphers �keying the generator� is setting the initial
state. Very simple strategy is used. The key stream is feed into Variation
V[] and the key length is feed into Sr. First 22w outputs are discarded to
worm up the generator. Here is the formal definition of keying procedure.
K[0..L] is the keystream
L is length of the keystream
r=0;
For j=0 to 2w { V[j]=K[r]; r=(r+1) mod L; }
For j=0 to 22w SQ1();
SQ1() is the generator function described before. The keystream should be
the same word size as P[] and V[] but it is allowed to be smaller to. For
example if w=14, the keystream can be conventional 8-bit character field. If
the w<8 (what is very bed idea) that the keystream should be cut in w-bit
peace in order to feed it into V. The maximal key length allowed using this
strategy is 22w bits, the length of V in bits.
5. Implementation Remarks
This is document is intended to help you implementing SQ1, if you are
interested about the design solutions read the thesis available on-line.
Because of security of the algorithm please follow these remarks:
1. SQ1 is not intending to be secure for any word size or key length. The
word size must be greater than 8bits.
2. Do not use all the bits produced by the generator, discard at least one.
If you need 8-bit values to encrypt files or communication channel use 9-bit
word. The values produced by the generator are going to be 0..511, just
discard the MSB and you have your 8-bit output.
3. Be careful chousing keys, no matter how secure SQ1 is, if the key is too
short or �usual� there is nothing GOD can do to help you
SQ1 is a fast algorithm, generating 1MB take 1.2 sec using my Celeron 300
(RC4 require 1 sec). However SQ1 offer you more security than any other
Stream Cipher.
6. Source code
Here is the source code of a simple program that encrypts file A to B using
key according to algorithm SQ1.
#include <stdio.h>
#include <string.h>
#define p(a) P[(a+R)%w2]
#define v(a) V[a%w2]
int P[4096], V[4096], Sr, R, W=9, w2=512;
int init_sq(char *keystream,int keylen);
int sq(void);
int main (int argc, char **argv)
{
FILE *inf, *outf;
int c;
if(argc==0)
{
printf("SQ [input file] [output file] [key] \n");
return 0;
}
inf=fopen(argv[1],"rb");
outf=fopen(argv[2],"wb");
init_sq(argv[3],strlen(argv[3]));
c=getc(inf);
while(!feof(inf))
{
c^=sq();
putc(c,outf);
c=getc(inf);
}
fcloseall();
return 0;
}
int init_sq(char *keystream, int keylen)
{
int i,x;
x=0;
for(i=0;i<w2;i++)
{
P[i]=i;
V[i]=keystream[x];
x=(x+1)%keylen;
}
Sr=keylen;
for(i=0;i<w2;i++) for(x=0;x<w2;x++) sq();
return 0;
}
int sq(void)
{
int A,B,c,Out;
A=p(Sr); B=p(v(A));
v(A)=B; c=p(A); p(A)=p(B); p(B)=c; R=(R+1)%w2;
Out=p(A+B);
Sr<<=1; Sr=(Sr/w2)^(Sr%w2); Sr=(Sr+Out)%w2;
return Out;
}
NOTICE
This document you can obtain from any of the following sites:
http://eon.pmf.ukim.edu.mk/~kbajalc
http://members.tripod.com/kbajalc
http://kbajalc.8m.com
If you are interest to know more details read the thesis available on the
same site.
� Kostadin Bajalcaliev 1999
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: 512 bit number factored
Date: Fri, 03 Sep 1999 19:28:49 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (D.
J. Bernstein) wrote:
>sci.crypt, November 1993: ``I can break 512-bit RSA keys. Let's say
>$10,000,000 per key. Reasonably quick turnaround guaranteed.''
>
>Anton Stiglic <[EMAIL PROTECTED]> wrote:
>> The inventors of RSA gave out a challenge, they beleived that factoring
>> would have taken _much_ longer time (be it impossible).
>
>People who conjecture lower bounds on time have a habit of being wrong.
>Ignore them; pay attention to the upper bounds instead.
>
>---Dan
That is why I recommand using the largest key possbile. But that may be
of no use if the following http://www.cryptonym.com/hottopics/msft-nsa.html
has any truth to it. I noticed that even the main machine I use when in Mexico
runs as slow as my 486. At first it seemed fast now it seems slow so there
may be a connection. When I get my new machine it will use Linux.
Take Care
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Subject: Re: 512 bit number factored
Date: 3 Sep 1999 17:39:37 GMT
sci.crypt, November 1993: ``I can break 512-bit RSA keys. Let's say
$10,000,000 per key. Reasonably quick turnaround guaranteed.''
Anton Stiglic <[EMAIL PROTECTED]> wrote:
> The inventors of RSA gave out a challenge, they beleived that factoring
> would have taken _much_ longer time (be it impossible).
People who conjecture lower bounds on time have a habit of being wrong.
Ignore them; pay attention to the upper bounds instead.
---Dan
------------------------------
From: "entropy" <[EMAIL PROTECTED]>
Subject: Different Encryption Algorithms
Date: Fri, 3 Sep 1999 14:45:38 -0400
I'm doing a high school research paper on different encryption algorithms,
such as CAST, IDEA, blowfish, RCx, DES, etc. Could anyone point me to
informative web sites pertaining to the differences between these encryption
methods?
Thank you.
--
a.
:::entropy:::
ktheory.com
------------------------------
From: Stephan Eisvogel <[EMAIL PROTECTED]>
Subject: Re: Alleged NSA backdoor in Windows CryptoAPI
Date: Fri, 03 Sep 1999 20:46:25 +0200
I say screw them. The story first showed up on John Young's
Cryptome site http://jya.com this morning. Took me only ten
minutes to patch the 'problem' on my NT4SP5 machine, now an
"NSA sig" will be no good no matter what (I didn't use the
published bloat-fix but patched the check and the key).
Also killed the "protected storage" crap some time ago since
I don't use Outlook and there's not much security added but
rather alot of obfuscation going on.
There's a couple of possibilities what _NSAKEY really means:
a) the real deal, backdoor key for new "NSA" crypto modules
b) some MS-programmer's prank (not funny)
c) 2nd MS key in case first one is compromised only with a
funny label
d) none of the above
I agree with CCC's Frank Rieger, it's time to establish some
more european open-source and no-nonsense security software,
take ssh for example. This Janet Reno "no real crypto" crap
is beginning to leave a bad taste in the mouth.
later
--se
------------------------------
From: [EMAIL PROTECTED] (Ian Goldberg)
Subject: Re: Alleged NSA backdoor in Windows CryptoAPI
Date: 3 Sep 1999 19:08:16 GMT
In article <[EMAIL PROTECTED]>,
DJohn37050 <[EMAIL PROTECTED]> wrote:
>The obvious reason for an NSA key (assuming that is what it is) is to allow NSA
>to write their own CSP's without needing to get permission from Microsoft.
>That is, they can put in their algorithms without going to Microsoft for
>approval. But the CSP still needs to be put on the machine somehow and this is
>a voluntary act (as far as I know), so I do not see anything nefarious.
>Don Johnson
And the NSA key would then be in *all* shipped copies of Windows
worldwide, why?
- Ian
------------------------------
From: [EMAIL PROTECTED] (Ian Goldberg)
Subject: Re: ECC, D.S., Fravia, & Ian
Date: 3 Sep 1999 19:10:00 GMT
In article <[EMAIL PROTECTED]>,
JPeschel <[EMAIL PROTECTED]> wrote:
>Ian Goldberg's updated picture. This cat looks a
>helluva lot like me, except he's about 20 years
>younger and a lot smarter. I think I'm in better
>shape, though. Wonder where he posts now?
Here, on occasion. :-)
- Ian "yeah, yeah, I know I've gained 30 pounds during my vacation..."
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Implementing crypto algorithms in Fortran.
Date: Fri, 03 Sep 1999 20:01:30 GMT
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>"SCOTT19U.ZIP_GUY" wrote:
>> ... IF the machine your on uses 2's complimnet
>> arithmetic then you can use signed numbers as unsigned.
>
>Only if overflow does not trigger an exception.
Most compliers give you the option of ignoring the
overflow or you can write a handler to it.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
Date: 3 Sep 1999 18:40:20 -0000
From: [EMAIL PROTECTED]
Subject: Re: Home Invasion Bill Drives U.S. Computer Users across border
Crossposted-To: alt.privacy.anon-server
=====BEGIN PGP SIGNED MESSAGE=====
On Fri, 03 Sep 1999 08:57:21 -0400 pbboy <[EMAIL PROTECTED]> wrote:
>
>At the risk of sounding completly oblivious to current events I must ask: Is
>this real?
>
Hasn't been 'real' so far.
I've been seeing stuff about this Zero-Knowledge Systems for a year.
I know people who are associated with them.
I've seen no product.
Sunny
ps: aside from that, I thought it was just another advertisement;-)
~~~
This PGP signature only certifies the sender and date of the message.
It implies no approval from the administrators of nym.alias.net.
Date: Fri Sep 3 18:40:15 1999 GMT
From: [EMAIL PROTECTED]
=====BEGIN PGP SIGNATURE=====
Version: 2.6.2
iQEVAwUBN9AWE05NDhYLYPHNAQEotQf9HHicBhR8iNB/9f7ASiPD9o2HAqUYj2wP
2ITXnqL63iJ1yRiWdKW60vkbjnrcynGVXaQEf5w9ZA2588SrMbVrIoaTqY260t9E
fE6Zp4i6ZNgiFpl/mYzwQbSL46qn2lqG5zJH5idCoQzUcGZEqtKL9ApWeu62R72z
0FYRF3coSucPsbg2y3k5X8ap3sHEvopbjRUc5eNHaNVH/y72inxTSp8gmzGySZz+
bq1xZwkaFBeaoyksjp1xAw2ATZZCOXEgSMNNYCwBOtTeMfyJhaAAU8vUxbMPHMmW
BOIT3RVtSCX+9ImNtO00L6zWprxiF0AhJcttvtkvJfCwAXDP/9QZYA==
=S6iF
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (jerome)
Subject: Re: IDEA- safe?
Date: 3 Sep 1999 19:03:28 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 02 Sep 1999 16:30:10 -0400, [EMAIL PROTECTED] wrote:
>
>As I have learned in the past few months on this newsgroup...as long as the
>key size is of sufficiant length (lets say 64 bits+), the keysize is really
>irrelivant. There are other types of attacks on algorithms than brute force.
>
and these attacks can use the key even if they are different than
brute force...
moreover if currently everybody says that 56bits is easy to reach, 64bits
is only 256 times more, so in 4.5months 64bits would be as easy as
56bits now, according to the principle "the cpu power double every 18months"
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Alleged NSA backdoor in Windows CryptoAPI
Date: 03 Sep 1999 19:03:20 GMT
The obvious reason for an NSA key (assuming that is what it is) is to allow NSA
to write their own CSP's without needing to get permission from Microsoft.
That is, they can put in their algorithms without going to Microsoft for
approval. But the CSP still needs to be put on the machine somehow and this is
a voluntary act (as far as I know), so I do not see anything nefarious.
Don Johnson
------------------------------
** 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
******************************
