Cryptography-Digest Digest #732, Volume #10 Mon, 13 Dec 99 13:13:01 EST
Contents:
Re: Please help this newbie crack a potentially simple encryption (Jim Gillogly)
Re: Why no 3des for AES candidacy (Anton Stiglic)
Re: NP-hard Problems (Anton Stiglic)
Re: Simple newbie crypto algorithmn (SCOTT19U.ZIP_GUY)
Re: Attacks on a PKI ("Tim Wood")
Re: some questions about DES (John Myre)
Re: Why no 3des for AES candidacy (Scott Fluhrer)
Re: NP-hard Problems ([EMAIL PROTECTED])
Re: Why no 3des for AES candidacy (John Myre)
Re: Why no 3des for AES candidacy (Uri Blumenthal)
Re: The future of telecommunication? (SCOTT19U.ZIP_GUY)
Re: Why no 3des for AES candidacy (SCOTT19U.ZIP_GUY)
Re: Attacks on a PKI (Helger Lipmaa)
----------------------------------------------------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Please help this newbie crack a potentially simple encryption
Date: Mon, 13 Dec 1999 17:16:51 +0000
John wrote:
> "The solution is a single sentence taken at random from a renowned
> English�language encyclopedia. Punctuation is ignored"
It's also possible that this cipher might be solved exhaustively:
some "renowned English-language encyclopedias" are available in soft
copy -- Britannica is inexpensive, Grolier is free with some CDROM
drives, and so on. You could reverse-engineer the storage format on
each of them and scan for single sentences of 223 letters in your
first pass, and for each of these see whether the repeated letters
show up in the right places. That might be less programming than
the hidden Markov model Doug suggested.
--
Jim Gillogly
Mersday, 23 Foreyule S.R. 1999, 17:11
12.19.6.14.1, 3 Imix 9 Mac, Second Lord of Night
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Why no 3des for AES candidacy
Date: Mon, 13 Dec 1999 12:21:23 -0500
Tim Wood wrote:
> >You can see why 3-DES, with it's single sized 168 bit key, does not fit in
> this
> >categorie.
>
> of course it's effective key length (strength) is 112bit not 168bit...
I agree, but it counts as a 168 bit key cipher since you need 168 bit of
randomness to create the key.
Anton
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: NP-hard Problems
Date: Mon, 13 Dec 1999 12:24:06 -0500
[EMAIL PROTECTED] wrote:
> Do you have a reference for this? That was the
A professor (in complexity theory) told me it might be
found in Garey-Johnson's book, pp 110-111. I have
not had the chance to look at it yet...
Anton
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Simple newbie crypto algorithmn
Date: Mon, 13 Dec 1999 18:20:17 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Steven Siew) wrote:
>It's sad to know that nowadays a lot of people held the NSA in such high
>regards as to wrongly believe that they have god like powers in cryptography
>and cryptoanalysis.
>
>It's not uncommon to hear things like "All codes that have been invented so
>far (with the exception of one time pads) have been broken by the NSA." or
>even "Today it is impossible for a newbie with basic C programming experience
>to write a crypto program that cannot be cracked by the NSA."
Yes this is the kind of Bull Shit the Crypto Gods would have the public
belive.
>
>Because a lot of people does not have cryptography experience, they have
>regarded cryptography as a black art. They believe that only crypto wizards
>are capable of coming up with wierd crypto algorithmns which no basic mortals
>are capable of understanding without devoting years to the studying of the
>black arts.
>
>That of course is total bullshit. Anyone with basic C programming skills and
>basic high school maths can write a crypto algo that the whole world cannot
>crack in less than 1000 years.
I think one can only say one can make it stronger and more secure than what
the phony crypto gods do with there short keyed methods. But to say its secure
for 1000 years is meaining less since who the hell knows where quantum
computers will be able to do in ten years.
>
>So I set about proving the above statement. In short I want to write a
>crypto program with the following chracteristics:
>
>1. The program must be simple and easy to understand. Thus the public can
> see easily the strengths of the encryption.
You will be surprised it how stupid the public is. They can't
understand high school math.
>
>2. The program must be cryptographically powerful enough not to be cracked
> even by using all the computers in the world in less than a 1000 years.
>
>3. No special knowledge of arcane cryptography is required. No maths more
> difficult than that encountered in high school is required.
>
>I have provided the source code below. I will explain what is needed to
>compile and use the program.
>
>There are two programs. The encryption program is called scramble and the
>decryption program is called unscramble.
>
>The programs were developed on a GNU/LINUX red hat 6.1 OS running on a
>pentium II computer. The program will worked on both big endian and little
>endian machines without changes to the source code.
>
>To compile the program:
>
>gcc -o scramble scramble.c
>gcc -o unscramble unscramble.c
>
>To use the program:
>
> scramble key < originaltext > encryptedtext
>
> unscramble key < encryptedtext > decipheredtext
>
Nice way to handle inputs and outputs.
>Where key is a regular file which contains the key to the encryption. For my
>program it is any regular file which has 607 or more bytes. For cryptography
>security please ensure that the key file contains pure random bytes.
This is the bane of most programs how does one get pure random bytes.
>
>To test that the program works, use:
>
> diff originaltext decipheredtext
>
>or
>
> cat originaltext | scramble key | unscramble key | less
>
>It you need to generate a random key but you dont have a source of pure
>random bytes then you can use the following trick.
>
> gzip -9 bigfile
> scramble bigfile.gz < bigfile.gz > key9
> scramble key9 < key9 > key8
> scramble key8 < key8 > key7
> scramble key7 < key7 > key6
> scramble key6 < key6 > key5
> scramble key5 < key5 > key4
> scramble key4 < key4 > key3
> scramble key3 < key3 > key2
> scramble key2 < key2 > key1
> tail -c 607 key1 > key
> rm key1 key2 key3 key4 key5 key6 key7 key8 key9
> gunzip bigfile.gz
>
>It will create a 607 bytes key file which should be almost completely
>random.
Well this is most likely your first mistake. YOU can't guarantee
this procedure makes a random file. Your eyeballs are not enough to guarantee
it. It reminds me of when Van Newman tried to deminstarte a random generator
and it locked up in a short cycle. If you method is any good at all you should
not need to do more than one or two scrambles on the key since you may be
reducing your available keyspace at each successive scramble. Since your
likely filtering out possiblites at each step. I'm not saying your method is
bad yet. But I am saying your way of generating a random key SUCKS big time.
Example
scramble key7 < key7 > key8
For there to be no information loss in the
transform from key7 to key8 You have to show that for any "Big File"
key8 that only scamble key7 < key7 > key8 can lead to key8
since if any other file say scramble filex < filex > key8
then you are losing information and thus the possiblity of keys.
>
>How the program works?
>
>The program uses permutation or "card shuffling" type tricks to encrypt the
>original text (plaintext). It also makes use of XOR to further confuse the
>attacker.
>
>The idea is simple. The fastest growing maths function in high school maths
>is factorial. A simple example is this. The number of ways a race of 7
>runners can finish is 7! or 7*6*5*4*3*2*1 ways. The number of ways a deck of
>52 cards can be shuffled is 52! And it grows very very very fast. If we
>encrypt a 64kb file, we can do it by shuffling 65536 * 8 = 524288 bits. The
>number of permutation is of course 524288! which is a big number. To say
>524288! is a big number is an understatement.
At this point you are very close to SCOTT16U.ZIP which is based on all
the Sincle Cyle permutations of 16bit wide look up table.
However 607 bytes would be a very small key for my method.
>
.....
>/* FIBP FIBQ alternative values for FIBP & FIBQ
> 607 273
> 1279 418 This is used to set up the fibonaci
> 2281 1029 sequence random number generator.
> 4423 2098 It should have a period of around
> 9689 4187 2^(FIBP-1)
>*/
>#define SIZE 65536
>#define FIBP 607
>#define FIBQ 273
>
....
.
> /* Initialise FIBADD */
> if (fread(fib,1,FIBP,fp) != FIBP)
> { printf("The key must be at least %d bytes\n",FIBP);
> exit(1);
> }
>
....
> while (stdread)
> {
> stdread=fread(stdinbuffer,1,SIZE,stdin);
> /* initialise substitution boxes */
> for(i=0;i<256;i++) sbox1[i]=sbox2[i]=substitution[i]=i;
> { unsigned char temp,n;
> for(i=0;i<256;i++) /* initialise sbox1 */
> { fibseq= ++fibseq % (FIBP+1);
> fib[fibseq]= fib[(fibseq+1)%(FIBP+1)]
> + fib[(fibseq+(FIBP-FIBQ+1))%(FIBP+1)];
> n=fib[fibseq];
> temp=sbox1[i];
> sbox1[i]=sbox1[n];
> sbox1[n]=temp;
> }
....
The heart of your method revolves around this sequencing of the
buff fib if the sequence can be proven to really have a period of
oder 2^(FIBP-1) for any array fib then you may have something
but I am not familar with this type of generator. Since in reality
any string of bytes is possible lets see what happens if they
all equal zero. The random ZERO key it is as likely as any other.
sequence of bits. if all fib[x] = 0 for all x then then the
equation fib[fibseq] = fib[(fibseq+1)%(FIBP+1)] +
fib[(fibseq+(FIBP-FIBQ+1)%(FIBP+1)];
does not change the value of fib[x] at all. In short the period is 1
which is a far cry from 2^(FIBP-1)
However you could use a generator of the form X = ((A*X)+B)modC
or somthing simmilar that is guarnateed to have maximal cycle length
where X is your key and than you can get the S-table you need based
on the current value of X. See scott16U or SCOTT19U for methods to
change files to S-cycle S boxes which is what yours small 8 bit sboxes
should be.
Don't give up with a few minor changes this is diffinitely on the way
to far superior encryption than any of the phony AES crap the goverment
and phony crypto gods wants us to use.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
------------------------------
From: "Tim Wood" <[EMAIL PROTECTED]>
Subject: Re: Attacks on a PKI
Date: Mon, 13 Dec 1999 17:36:20 -0000
Douglas A. Gwyn wrote in message <[EMAIL PROTECTED]>...
>David A Molnar wrote:
>> None of these is the real expectation. The real expectation is that
>> "this food won't make me sick." The rest is professionalism.
>> The difference seems to me that with a PKI, I take a look at a key
>> and it's not clear immediately what kind of keys "won't make me sick."
>
>Come on, at that level it is obvious: You should be able to get
>the authentic public key for any communicant.
>
>The details are at the same level as for food transport and
>storage..
The issue is slightly more complex than that, how do tell when it goes
wrong? It is far easier to detected poisoned food. A possible attack is
enough to kill a PKI, an actual attack is not necessary. There are a lot of
variables.....
Is the certificate a certificate of the link between a person and their
private key, an organisation (of several people) and its private key, and
e-mail address and it's private key?
Who is the certificate authority (CA)? Who decided to trust them, how do you
decide to trust a new CA? Is the RA trust worthy.
Then how did the certification take place, did the person have to present
themselves at an office with a private/public key on a disk, and show their
passport/birth certificate/driving license, or did they just email a request
with a public key in it to an automatic system which then e-mailed the
certificate back without any-other checks (both types of certificate are
available.....
Then how is the private key stored? the authorities private key?
How are public keys archived, certificates stored?
ARRGH......;-)
There are of course solutions to this, but most of them require research by
the user (and how many people here have read the verisign policy
statement?).
I suppose we need a trusted body to monitor the CA's.
but who watches the watchers? *grin*
tim
--
**<Stolen line alert>**
>From my one-bit brain with a parity error.
**</Stolen line alert>**
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: some questions about DES
Date: Mon, 13 Dec 1999 10:27:17 -0700
Anton Stiglic wrote:
> You can get this answer by a nice table that is given in an issue of
> CryptoBytes,
> Volume 3, No.2-Autumn 1997. Get it at
> http://www.rsasecurity.com/rsalabs/cryptobytes/
Volume 4, No. 2 - Winter 1999 has more recent data.
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: Why no 3des for AES candidacy
Date: Mon, 13 Dec 1999 17:39:20 GMT
In article <[EMAIL PROTECTED]>,
Anton Stiglic <[EMAIL PROTECTED]> wrote:
>UBCHI2 wrote:
>
>> Why isn't 3des being considered for the AES? Is it because it is slower than
>> DES?
>
>One good reason:
>
>The AES is supposed to support the following different key sizes: 128, 192, 256
>
>You can see why 3-DES, with it's single sized168 bit key, does not fit in this
>categorie.
In addition, AES candidates must have a block length of 128, 3DES has a block
length of 64.
--
poncbo
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: NP-hard Problems
Date: 13 Dec 1999 17:44:31 GMT
Anton Stiglic <[EMAIL PROTECTED]> wrote:
> Safuat Hamdy wrote:ut the
>> [...]
>> None of the authors are complexity theorists, so HAC is a non-authoritative
>> source regarding complexity theory. A really good source is B. Diaz,
>> J. Gabarro, and J. Balcazar: Structural Complexity I, 2nd ed. (beware!),
>> Springer, 1995.
> Could you post the definition of NP-Hard given in that book?
> It would be nice to have a compilation of definitions of NP-Hard.
Here's the definition from the Balcazar, Diaz, and Gabarro book (this
is from the 1st edition though, which is all I have....):
Definition 3.6: Given a class C,
1. A set A is C-hard, or m-hard for C, if and only if, for any
set B in C, B [ is polynomial-time many-to-one reducible to ] A.
2. A set A is C-complete, or m-complete for C, if and only if it
is C-hard and A is in C.
To rephrase that in terms of the class NP: A set A is NP-hard if and
only if for any set B in NP, B is (poly-time, many-to-one) reducible
to A.
Here's another source, "The Handbook of Theoretical Computer Science",
in the chapter "A Catalog of Complexity Classes", by David Johnson:
Definition: A search problem X is NP-hard if for some NP-complete
problem Y there is a polynomial-time Turing reduction from Y to X.
So there you have it. Two different definitions that cover different
things, actually. By the BDG (Balcazar, Diaz, and Gabarro)
definition, you need to use a polynomial-time many-to-one reduction,
which is only defined for decision problems (and, in fact, since they
define things in terms of "sets", you're stuck with decision problems
only anyway!). Johnson's definition from the Handbook is clearly
targeted as search problems (non-decision problems), and as a result
uses a Turing reduction rather than an m-reduction.
I'm afraid that doesn't clarify anything, but does show you that two
very good sources can disagree on what NP-hard really means....
--
Steve Tate --- srt[At]cs.unt.edu | Gratuitously stolen quote:
Dept. of Computer Sciences | "The box said 'Requires Windows 95, NT,
University of North Texas | or better,' so I installed Linux."
Denton, TX 76201 |
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Why no 3des for AES candidacy
Date: Mon, 13 Dec 1999 10:36:13 -0700
Anton Stiglic wrote:
> UBCHI2 wrote:
> > Why isn't 3des being considered for the AES? Is it because it is slower than
> > DES?
>
> One good reason:
> The AES is supposed to support the following different key sizes: 128, 192, 256
> You can see why 3-DES, with it's single sized168 bit key, does not fit in this
> categorie.
Then, too, AES is required to have a 128 bit block size, while DES and
3DES
have a 64 bit blocksize.
Nonetheless, two AES candidates are explicitly based on DES: DEAL and
Serpent. The latter is among the five finalists.
John M.
------------------------------
From: Uri Blumenthal <[EMAIL PROTECTED]>
Subject: Re: Why no 3des for AES candidacy
Date: Mon, 13 Dec 1999 12:42:54 -0500
> >> Why isn't 3des being considered for the AES? Is it because it is
> >> slower than DES?
1. Yes, because it's slow[er than newer, hopefully better algorithms].
2. Because it has 64-bit block, and if you go throught the trouble
of defining a whole new standard, may as well do it right, save
yourself some efforts in the [near] future and go to 128-bit
blocks.
> >One good reason:
> >The AES is supposed to support the following different key sizes:
> > 128, 192, 256
> >
> >You can see why 3-DES, with it's single sized 168 bit key,
> >does not fit in this categorie.
No I can't - there are ways to securely make key of any length
(from 64 bis to 768*3 bits) for 3DES.
> of course it's effective key length (strength) is 112bit not 168bit...
In general - this is incorrect. In particular, it HIGHLY depends
on the key schedule and how the DES engine is employed.
See "A Better Key Schedule for DES-like Ciphers" paper on
<http://www.research.att.com/~smb/papers/index.html>
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: The future of telecommunication?
Date: Mon, 13 Dec 1999 18:47:06 GMT
In article <8325hm$t55$[EMAIL PROTECTED]>, "Melinda Harris"
<[EMAIL PROTECTED]> wrote:
>Is it possible?? A virus that encrypts your entire hardrive upon logon?
Why did you ask this. OF COURSE ITS POSSIBLE.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Why no 3des for AES candidacy
Date: Mon, 13 Dec 1999 18:45:26 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(UBCHI2) wrote:
>Why isn't 3des being considered for the AES? Is it because it is slower than
>DES?
1. Depending on how one combines the cipher to make 3DES it could be come
to hard for current NSA to quickly decode the message for law enforcement.
2. Again it is easy to just say it would be to slow. Thus again making it
something the NSA will not have to mess with very much. You forget that
the AES is so the common man can be fooled into safe crypto and the
NSA does not wish to bother with taking much time at decoding.
3. The crypto field is full if people with bloated egos. To produce something
like DES would not look new or very inventive. But it would not be hard
to do it. It is just not the kind of thing the NSA would let you go with.
The speed thing is what most phony crypto gods would have you belive the
reason is. But in fact with the bloated operating systems one uses know a days
and as machines get faster very week this is really a lame reaon when one
wants real security.
But in my opinion it still is not as strong as what I woulf like. So even if
it was adopted we would not be much better off than any of the current
AES candidates.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
------------------------------
From: Helger Lipmaa <[EMAIL PROTECTED]>
Subject: Re: Attacks on a PKI
Date: Mon, 13 Dec 1999 19:53:22 +0200
David A Molnar wrote:
> lcs Mixmaster Remailer <[EMAIL PROTECTED]> wrote:
>
> [snip explanation of PKI, pointing out that even personal key file
> is in sense a PKI]
> > authority can specialize in this task. The disadvantage is that you
> > now must trust this other entity to securely and accurately manage his
> > certifications. Of course, you entrust your very life every day to the
> > expectation that third parties have professionally applied their skills
> > and energies, so there is nothing particularly revolutionary in extending
> > such trust to a key infrastructure.
>
> Eventually I will agree with you. :-\
>
> What seems "revolutionary" to me _now_ is that the key infrastructure
> does not seem to be as well understood, as accountable, or as well
> regulated as many of the other third parties I depend on. It's not
> completely clear what I should expect from a PKI, while in many real
> life cases the expectations are so amazingly clear that stating them
> seems pedantic.
>
> For example, I trust that the food I eat is free of disease; in doing so
> I'm implicitly trusting half a dozen third parties.
> late.
/* A short exempt from our lately submitted paper. */
/* BEGIN */
/* ... */
Secure electronic commerce necessitates wide-scale employment of
public-key cryptography that, in turn, requires secure and efficient
methods of certificate management in the \emph{Public-Key
Infrastructure} (PKI). Most of the known techniques for the latter
involve a public database of valid (or revoked) certificates that
originates from a trusted source (known as Certification Authority,
CA), but is maintained by a less trusted party (known as a Directory
Service, DS) who provides on-line certificate information services to
the clients. Neither the CA nor the DS is forced to store old
certificates. Anyone having a candidate certificate and a
certificate-specific attestation can efficiently verify whether the
certificate was included in the database (i.e., whether it was valid)
at a given moment in time, even if the third parties have ceased to
exist in between.
Certificate management is very often \emph{the} security bottleneck in
electronic commerce and other legal applications of digital
signatures. Therefore it is highly desirable to minimize the number
of possible frauds the third parties involved in PKI can accomplish.
This is often done by auditing the protocols followed by the CA.
Certificate issuing and revocation are examples of such procedures,
during which the CA is \emph{forced} to return the attestation. To
audit each operation the CA performs would be clearly too costly and
therefore, for the sake of efficiency, the CA is usually assumed to be
trusted in some aspects of certificate management. Additional trust
assumptions mean however that the origin of some frauds may stay
undetectable.
Still, we want that, in legal disputes arising from the frauds in
certificate management, both the frauds themselves and their origins
were efficiently detectable and provable to the third parties (i.e.,
we want the certificate management system to be \emph{accountable}).
Ideally, one should be able to distinguish between the frauds done by
a CA and the frauds caused by someone capable of breaking the used
primitives. This means that the number of frauds that a
computationally challenged CA is able to perform undetectably should
be minimal.
To explain how to proceed in building an accountable certificate
management system, we note that any legal case caused by the problems
in certificate management would involve two principals, having a pair
of so called \emph{contradictory} attestations, so that verification
accepts or rejects the certificate depending on which attestation was
used as input to the algorithm. Clearly, if it were tractable for the
CA to create contradictory attestations, we would have a
non-accountable system.
/* ... */
Our solution is the first efficient certificate management system that
enables one to replace inefficient CRLs without compromising security
and has hence, as we think, great practical importance. The described
construction can almost always be used instead of the certificate
revocation trees in order to reduce trust in the database maintainer,
without decreasing efficiency.
/* ... */
/* END */
In the case of interest please e-mail me directly.
Helger Lipmaa
http://home.cyber.ee/helger
Cybernetica, senior research engineer
------------------------------
** 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
******************************
