Cryptography-Digest Digest #556, Volume #11 Sun, 16 Apr 00 08:13:01 EDT
Contents:
Re: One Time Pads Redux (Jim Gillogly)
Re: Why is this algorithm insecure? (Newbie flamefodder) (Richard Heathfield)
Re: Why is this algorithm insecure? (Newbie flamefodder) (Richard Heathfield)
Re: Non-standard shift register sequences ("Peter L. Montgomery")
Re: Is AES necessary? (Bryan Olson)
Re: Miami Herald article about ATM ripoffs (Norman D. Megill)
Re: Miami Herald article about ATM ripoffs (Norman D. Megill)
Re: ? Backdoor in Microsoft web server ? [updated] (Francois Grieu)
Re: Q: Entropy (Mok-Kong Shen)
Re: Is AES necessary? (Mok-Kong Shen)
Re: General principles of design (Mok-Kong Shen)
My STRONG data encryption algorithm ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: One Time Pads Redux
Date: Sun, 16 Apr 2000 05:14:59 +0000
Joaquim Southby wrote:
> A) Bob and Alice each have a RNG at their disposal. These do not need to
> be synchronized or even similar -- they just have to create numbers
> acceptably random for an OTP.
So far so good.
> B) Bob enciphers a message by XOR'ing the plaintext with numbers from his
> RNG; he keeps a temporary copy of the numbers he used for this message.
> He sends the enciphered message to Alice.
Mallet intercepts the message, and now has M XOR Rng[A].
> C) Alice repeats this process using her RNG and sends the result back to
> Bob.
Mallet intercepts the message M XOR Rng[A] XOR Rng[B] and XORs it
with the first message. He now has Rng[B].
> D) Bob uses his temporary copy of the numbers he used the first time,
> XOR'ing them with Alice's return message to remove his stuff from the
> mix. He sends the result to Alice.
Mallet intercepts the message M XOR Rng[B] and XORs it with Rng[B],
and reads M a little bit sooner than Alice.
> E) Alice uses her temporary copy to remove her encipherment and retrieve
> the original plaintext message.
Mallet acts on the information slightly before Alice does.
> F) Both of them destroy their temporary copies of their RNG numbers.
Mallet holds onto both of them in hopes of cracking the RNGs before
the next version of the protocol is developed.
> OTP's to multiple users. It seems so simple (other than the correlation
> of messages to RNG output) that there must be something wrong with it.
Good intuition.
--
Jim Gillogly
Hevensday, 26 Astron S.R. 2000, 05:08
12.19.7.2.6, 11 Cimi 9 Pop, First Lord of Night
------------------------------
Date: Sun, 16 Apr 2000 08:30:15 +0100
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Why is this algorithm insecure? (Newbie flamefodder)
"NFN NMI L." wrote:
>
>
> 128-bit, maybe 256-bit keys are fine. The larger the key, the more unwieldy it
> is. If you don't care about large keys, just use an OTP!
Well, there's large and then there's infinite. ;-)
Thanks for your speedy reply.
>
> <<For each byte of the key
> Pick some number B with which that byte of the key is uniquely
> identified (I used a bunch of primes)
> Rotate the buffer left by B bits.
> Perform a Vigenere-style XOR of the key all the way along the buffer.>>
>
> So, you repeat this process Q times, where Q is the number of bytes in the key,
> and the first time, you rotate the plaintext by 2 bits, the second time, by 3
> bits, and the Qth time by P[Q] bits?
Er, no - my description was less fastidious than my source code, I'm
afraid. Actually it's P[K[n]] where n is the byte we're on, in the range
0 to N - 1 (if the key has N bytes).
And after each rotation you just XOR the
> value KEYKEYKEYKEY...KEY to the plaintext?
Yes.
> Obviously, you can just start with
> 0000...000 and then do this process, producing a really munged key, and then
> XOR that key with the plaintext (this is equivalent to your algorithm).
I'm not sure whether that's true, given the above correction (which
stems from my poor explanation).
> This
> algorithm obviously fails horrendously for keys that are all 0's. What if your
> key is one byte: 01101100, say? See how little your algorithm can munge this
> key: rotating it by 3 bits is the same as rotating it by 11 bits.
Actually, whilst an 8-bit key is naturally a weakness, it would still
mung a reasonable amount, I think:
plaintext 01111010 00111011 10011011
key 01101100
So we start off by rotating by P[K[0]] - in my example source code I
used primes, and this byte of the key, 01101100 (108) gives us P[108]
which is 571. So we're going to rotate the buffer left by 571 bits.
Clearly, with a ciphertext of only 24 bits, there's no point in 571: we
can use 571 % 24 (which turns out to be 19. We would therefore take 19
bits off the left of the number and bolt them onto the right. /Now/ we
XOR the key, giving
intermed 11011011 11010001 11011100
key 01101100 01101100 01101100
ciphertext 10110111 10111101 10110000
Clearly, a short message with a very short key is not going to take much
cracking (although I'd be curious to know when/how Eve knows when she's
arrived at the correct solution). But if I were to use this algorithm
'in real life', I'd probably be using keys in the 512- to 4096-bit area,
for messages typically 512 bits long (individual TCP/IP packets).
> This would
> really suck if a key could be 6 bits (why?) Perhaps a key of 6 bytes, 48 bits,
> will suck too. Think about it.
I will think about this in the background, but initially I'm curious as
to whether your objection would still hold, now that I've explained the
algorithm a little more clearly. But I promise to think about it myself
too! :-)
Thanks once again for your speedy and courteous response.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
29 K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html (68
to go)
------------------------------
Date: Sun, 16 Apr 2000 08:47:55 +0100
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Why is this algorithm insecure? (Newbie flamefodder)
stanislav shalunov wrote:
>
> It appears that for any given key and length of plaintext there exists
> a string of the length the same as the plaintext that you XOR to get
> the ciphertext.
>
> This is bad. For example, a chosen plaintext attack with just one
> chosen plaintext reveals any further messages of the same length
> encrypted with the same key.
Thank you. I'm not sure, however, that I have understood you correctly.
You seem to be saying that Eve can decrypt any message she likes,
provided she has first done a chosen plaintext attack on a message that
length and using the same key as Alice. Okay, yes, that's a problem. But
how would she do such an attack? Would I be right in thinking that it
goes something like this:
Eve encrypts a plaintext of her own choosing (e.g. "Hello world") using
some random key (which she may deliberately choose not to know, though
she may store it, of course - it's not necessary at this stage, however)
Eve XORs the plaintext with the ciphertext, resulting in a sort of
skeleton key
Eve can now decrypt any message that long which was encrypted with the
random key she selected.
Is that what you meant? If so, I'm not sure that it works (although I
assure you I'll test it thoroughly), and even if it does work, how
useful is it? What if Alice is using a 4096-bit keyspace, for example. I
hesitate to expand this number into 10-based notation. It's quite large,
though. And if it's not large enough, consider an 8192-bit keyspace. I
can keep doubling all day... If Alice changes her key regularly, or
doesn't even know her key (for example, she establishes a common secret
with Bob at runtime, known to neither of them - only their computers),
then Eve is faced with a constantly changing key in a large keyspace.
Yes, she can run the ciphertexts through her database of
previously-tested keys in the hope that she'll get lucky - repeated key,
repeated messagelength, but it's surely not an /effective/ attack?
Please explain how I've misunderstood.
>
> There are many other problems.
>
Such as?
Please don't misunderstand me. I'm keen to learn the weaknesses of this
algorithm, and you've undoubtedly hit on a possible line of attack,
albeit a brute-force method, but either I have failed to interpret your
answer correctly, or... or... er... :-)
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
29 K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html (68
to go)
------------------------------
From: "Peter L. Montgomery" <[EMAIL PROTECTED]>
Subject: Re: Non-standard shift register sequences
Date: Sun, 16 Apr 2000 08:09:43 GMT
In article <8d1eg8$dns$[EMAIL PROTECTED]>
"Al Grant" <[EMAIL PROTECTED]> writes:
>I'm looking for literature on two non-standard shift-register
>techniques:
>
>1. use of a value computed from previous outputs, e.g.
> A_i = A_{i-n} + sum(A_0 to A_{i-1})
>where the sum is computed by updating an accumulator
>with each new output
This is easily converted to a standard shift-register
recurrence, with appropriate initial conditions. Note
A_i - A_{i-n} = sum(A_0 to A_{i-1})
= A_{i-1} + sum(A_0 to A_{i-2})
= A_{i-1} + (A_{i-1} - A_{i-n-1})
--
E = m c^2. Einstein = Man of the Century. Why the squaring?
[EMAIL PROTECTED] Home: San Rafael, California
Microsoft Research and CWI
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Is AES necessary?
Date: Sun, 16 Apr 2000 08:18:32 GMT
Mok-Kong Shen wrote:
> Paul Koning wrote:
[...]
> > Right, and not all of those have security benefits.
> You could use another DES as a random number generator to supply
> the keys for the DES that does the proper encryption.
The straightforward interpretation of that suggestion
is indeed a variant that has little if any security
benefit.
I think AES is necessary, but I grant that there's
a reasonable case for the adequacy of 3-DES. I don't
see any justification for these new tweaked-DES
ciphers.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Norman D. Megill)
Subject: Re: Miami Herald article about ATM ripoffs
Date: 16 Apr 2000 05:00:10 -0400
In article <[EMAIL PROTECTED]>,
Narley Okim <[EMAIL PROTECTED]> wrote:
>Today's Miami Herald has an article by David Green <[EMAIL PROTECTED]>
>titled, "S. Florida sees new breed of ATM, credit card crooks". In
>discussing the magnetic stripes on the backs of credit cards, he says "Each
>stripe contains a mathematical logarithm necessary to access that account."
>
>Does that make sense or are we talking clueless reporter here?
I went to the Computer Museum in Boston, where one of the exhibits is a
magnetic stripe reader that allows you to swipe a card, and on the
screen you see the characters encoded on the stripe. Well, I put in my
BankBoston ATM card and was shocked to plainly see among the first few
characters my PIN.
I reported this to BankBoston, and their reaction was that the Computer
Museum was irresponsible for letting the public see what is encoded on
their card. They have taken no further action.
Needless to say, I am now much more protective of the ATM card.
--Norm
------------------------------
From: [EMAIL PROTECTED] (Norman D. Megill)
Subject: Re: Miami Herald article about ATM ripoffs
Date: 16 Apr 2000 05:28:52 -0400
In article <8dbveq$[EMAIL PROTECTED]>,
Norman D. Megill <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>,
>Narley Okim <[EMAIL PROTECTED]> wrote:
>>Today's Miami Herald has an article by David Green <[EMAIL PROTECTED]>
>>titled, "S. Florida sees new breed of ATM, credit card crooks". In
>>discussing the magnetic stripes on the backs of credit cards, he says "Each
>>stripe contains a mathematical logarithm necessary to access that account."
>>
>>Does that make sense or are we talking clueless reporter here?
>
>I went to the Computer Museum in Boston, where one of the exhibits is a
>magnetic stripe reader that allows you to swipe a card, and on the
>screen you see the characters encoded on the stripe. Well, I put in my
>BankBoston ATM card and was shocked to plainly see among the first few
>characters my PIN.
>
>I reported this to BankBoston, and their reaction was that the Computer
>Museum was irresponsible for letting the public see what is encoded on
>their card. They have taken no further action.
I might add that this was about a year ago, and by "no further action" I
mean none that they told me about. I was a little dismayed by their
apparent lack of concern. Since then I have received a new card to
replace my expired one, and do not plan a visit to the Computer Museum
anytime soon. If someone in the Boston area plans a trip there anytime
soon it would be an interesting experiment to report on here.
--Norm
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: ? Backdoor in Microsoft web server ? [updated]
Date: Sun, 16 Apr 2000 11:54:08 +0200
Jim Gillogly <[EMAIL PROTECTED]> wrote :
> OK, here's first-hand confirmation. I did a Web search of
> dvwssr.dll and [..it contains..]
> !seineew era sreenigne epacsteN
Thanks to this report and a few others, we can now take for
granted the sentence "Nescape engineers are weenies!" is
embedded in Microsoft's dvwssr.dll
I found Microsoft's statement on the issue at
<http://www.microsoft.com/technet/security/bulletin/ms00-025.asp>
and
<http://www.microsoft.com/technet/security/bulletin/fq00-025.asp>
Microsoft does acknowledge that dvwssr.dll
" uses an obfuscation key to obscure the names of files being
requested by the client from the server "
My understanding is that "Nescape engineers are weenies!" is this
obfuscation key (now the thread starts to be crypto-related :-)
It is not entirely clear to me what is allowed by knowing the
obfuscation algorithm and the key, especially since there are
interactions with other file permission mechanisms.
According to a former version (*) of Microsoft's statement
" The vulnerability could allow a user who has privileges
on a web server to read certain files from other web sites
hosted on the same computer "
My best _GUESS_ is that, in order to implement a "link view"
[site map] feature in the web server, a read-all security bypass
was deemed useful, and was implemented with this "security
through obscurity" scheme. This qualifies as a backdoor to me,
although one with limited scope, and not the deliberate
"universal password" (**) kind of backdoor.
Microsoft now documents the issue with dvwssr.dll as a potential
buffer overrun. The report attempts to justify this focus shift:
the buffer overrun issue (found after the original problem)
could allow arbitrary code to be run, which is more dangerous.
IMHO it is a convenient way to no longer describe a security
override introduced by some programmer _deliberately_, which
makes it quite embarrassing.
Francois Grieu
Various related messages are at
<http://www.securityfocus.com/templates/archive.pike?list=1>
Discussion on the backdoor
<http://www.securityfocus.com/templates/archive.pike?list=1&msg=Pine.LNX.
[EMAIL PROTECTED]>
problem report on the buffer overrun
<http://www.securityfocus.com/templates/archive.pike?list=1&msg=38F7AD47.
[EMAIL PROTECTED]>
(*) first version of Microsoft's statement on the issue
<http://www.securityfocus.com/templates/archive.pike?list=1&msg=D1A11CCE7
8ADD111A35500805FD43F5867C2E3@RED-MSG-04>
Various related messages [including of the list owner, who admits
he misguided the press with unfounded speculations]
<http://www.ntbugtraq.com/default.asp?pid=36&sid=1&A1=ind0004&L=ntbugtraq
>
(**) for example, circa 1985 the company I then worked for was
selling the "ASCII Express" BBS for the Apple ][, customized for
our 1200/75 bps modem. To our great embarrassment, it turned out
the author had put a backdoor in the login code, allowing him
to connect with the highest privileges by supplying some special
login/password.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Sun, 16 Apr 2000 12:14:44 +0200
Bryan Olson wrote:
>
> Nope. "f(x) = g(x) + O(1)" tells us nothing about
> the sign or magnitude of f(x) - g(x) at any
> particular value of x.
Fine. What difference is there, if one has, instead of two finite
strings, two infinite strings to compare? (If I understand you
correctly, Komolgorov complexity can be used to compare two
infinite strings.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Is AES necessary?
Date: Sun, 16 Apr 2000 12:14:51 +0200
Bryan Olson wrote:
>
> Mok-Kong Shen wrote:
> > Paul Koning wrote:
> [...]
> > > Right, and not all of those have security benefits.
>
> > You could use another DES as a random number generator to supply
> > the keys for the DES that does the proper encryption.
>
> The straightforward interpretation of that suggestion
> is indeed a variant that has little if any security
> benefit.
The variant effectively renders differential analysis infeasible.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: General principles of design
Date: Sun, 16 Apr 2000 12:52:28 +0200
zapzing wrote:
>
> In article <8d04ge$3u1$[EMAIL PROTECTED]>,
> "almis" <[EMAIL PROTECTED]> wrote:
> > Hmmmmm..... OK
> >
> > However; your concept seems to be in conflict with a cryptographic
> > maxim that states (something like) '...That which cannot be hidden
> deeply,
> > should not be hidden at all...'
>
> And that crypto maxim contradicts a
> well known military maxim, "information
> will be given out on a need to know basis"
I have previouosly commented on almis' post. But the
'need to know' constraint practiced naturally in many security
environments is in cryptology generally not considered adequate
for protecting knowledge of an encryption algorithm from being
gained by the opponent. For instance, in WWII, crypto machines
were captured by enemies. However, as I said, a parametrized
cipher has two parts, one is constant, while the other is variable.
Capturing hardware or software gives knowledge of the constant
part to the opponent, but he is ignorant of the variable part,
which depends on the sessions.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: My STRONG data encryption algorithm
Date: Sun, 16 Apr 2000 11:50:05 GMT
/*
Hi all,
I have developed a data encryption algorithm and I think it is very
very strong,
maybe the strongest ever. It is 32768-bit and can be programmed to be
stronger easily if you wish. Of course, the stronger, the slower. It is
always slower than DES. But I think most people take more care of their
security and the famous morre rule will help to solve this problem.
To ensure it's strong as well as to share it with you, I post the
source code here to let you test and try breaking it. Please reply me
if you find anything unsatisfactory in the algorithm. The code is
written in Turbo C++ and is easy to understand. If you need a compiled
exe file, email me and I will give you a copy.
(Please use it for sientific research only)
I am looking forward to your replies.
Best,
YanQiQi.
[EMAIL PROTECTED]
http://www.thinkingsoft.com
*/
// YanQiQi's Data Encryption
Algorithm 0.1
// by
YanQiQi
// All rights
reserved
// email: [EMAIL PROTECTED]
//
// FOR SCIENTIFIC RESEARCH
ONLY
#define ENCRYPT 1
#define DECRYPT -1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
char filehead[]="YanQiQi's Data Encryption Algorithm 0.1";
char buffer[32768];
unsigned int passwordlen;
unsigned long int password[1024],pos,chaos,size;
char value;
double pow2_42;
double temp;
int c,i,j,state;
FILE *fp1,*fp2;
double a;
void main(char argc,char **argv)
{
printf("\n\nYanQiQi's Data Encryption Algorithm 1.0\n");
printf(" (FOR SCIENTIFIC RESEARCH ONLY)\n");
printf("\t by YanQiQi\n\tAll rights reserved\n");
printf(" mailto:[EMAIL PROTECTED]\n\n\n");
printf("Command: YQQ encrypt/decrypt sourcefile.ext
targetfile.ext password\n");
printf("Note: a password is a text string consists of 0..9,
a..f\n\n");
for(i=0;i<1024;i++) password[i]=0;
pow2_42=pow(2,42);
if(argc!=5)
{
printf("error command");
return;
}
if(strcmp(argv[1],"encrypt")==0)
state=ENCRYPT;
else if(strcmp(argv[1],"decrypt")==0)
state=DECRYPT;
else
{
printf("encrypt or decrypt?\n");
return;
}
//check and convert password
for(i=0;i<strlen(argv[4]);i++)
{
if(('0'<=argv[4][i])&&(argv[4][i]<='9'))
argv[4][i]=argv[4][i]-'0'+10;//add 10 to
avoid argv[4]i]==0;
else if(('a'<=argv[4][i])&&(argv[4][i]<='f'))
argv[4][i]=argv[4][i]-'a'+10+10;
else
{
printf("illegal password\n");
return;
}
}
//convert password into an array of unsigned longint
passwordlen=(strlen(argv[4])-1)/8+1;
for(i=0;i<passwordlen;i++)
{
for(j=0;j<8;j++)
{
if(i*8+j<strlen(argv[4]))
{
password[i]*=16;
password[i]+=argv[4][i*8+j]-10;
}
}
}
if((fp1=fopen(argv[2],"rb"))==NULL)
{
printf("fail to open source file.");
return;
}
if(state==ENCRYPT)
{
if((fp2=fopen(argv[3],"wb"))==NULL)
{
fclose(fp1);
printf("fail to create target file.");
return;
}
}
printf("working...");
//file head
switch(state)
{
case 1:
fwrite(filehead,1,strlen(filehead)+1,fp2);
//below change the password randomly to
avoid the
//situation that two files are encrypted
//using the same real password
randomize();
for(i=0;i<passwordlen;i++)
{
chaos=random(65536)*65536+random
(65536);
password[i]+=chaos;
fwrite(&chaos,4,1,fp2);
}
break;
case -1:
fread(buffer,1,strlen(filehead)+1,fp1);
if(strcmp(filehead,buffer)!=0)
{
printf("error file format\n");
fclose(fp2);
fclose(fp1);
return;
}
for(i=0;i<passwordlen;i++)
{
fread(&chaos,4,1,fp1);
password[i]+=chaos;
}
break;
}
//password confirmation to test password availability
switch(state)
{
case 1:
strcpy(buffer,filehead);
buffer[strlen(filehead)]=0;
break;
case -1:
fread(buffer,1,strlen(filehead)+1,fp1);
}
pos=0;
value=0;
for(i=0;i<strlen(filehead)+1;i++)
{
temp=0;
for(j=0;j<passwordlen;j++)
temp=floor(cos(temp+password[j]+pos+value)
*pow2_42);//possible unstable damages?
value=temp;
switch(state)
{
case ENCRYPT:
buffer[i]+=value;
break;
case DECRYPT:
buffer[i]-=value;
}
pos++;
}
switch(state)
{
case 1:
fwrite(buffer,1,strlen(filehead)+1,fp2);
break;
case -1:
if(strcmp(filehead,buffer)!=0)
{
printf("error password\n");
return;
}
}
if(state==DECRYPT)
{
if((fp2=fopen(argv[3],"wb"))==NULL)
{
fclose(fp1);
printf("fail to create target file.");
return;
}
}
//encrypting or decrypting data
while((size=fread(buffer,1,32768,fp1))>0)
{
for(i=0;i<size;i++)
{
temp=0;
for(j=0;j<passwordlen;j++)
temp=floor(cos(temp+password[j]
+pos+value)*pow2_42);//possible unstable damages?
value=temp;
switch(state)
{
case ENCRYPT:
buffer[i]+=value;
break;
case DECRYPT:
buffer[i]-=value;
}
pos++;
}
fwrite(buffer,1,size,fp2);
}
fclose(fp2);
fclose(fp1);
printf("done\n");
}
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
