Cryptography-Digest Digest #737, Volume #10 Tue, 14 Dec 99 08:13:01 EST
Contents:
Re: Deciphering without knowing the algorithm? (Anti-Spam)
Re: Deciphering without knowing the algorithm? (Guy Macon)
Re: Insecure PRNG? (Guy Macon)
Re: Insecure PRNG? (Mok-Kong Shen)
Re: Insecure PRNG? (Mok-Kong Shen)
Re: Simple newbie crypto algorithmn (Steven Siew)
Re: Simple newbie crypto algorithmn (Steven Siew)
Re: Simple newbie crypto algorithmn (Steven Siew)
Re: Why no 3des for AES candidacy ("Tim Wood")
Re: Why no 3des for AES candidacy ("Tim Wood")
Re: Insecure PRNG? (CLSV)
Re: Simple newbie crypto algorithmn (CLSV)
Re: How do you crack a Rotating Grille? (James Pate Williams, Jr.)
Re: How do you crack a Rotating Grille? (Jim Gillogly)
Re: Deciphering without knowing the algorithm? (Paul Schlyter)
----------------------------------------------------------------------------
From: Anti-Spam <[EMAIL PROTECTED]>
Subject: Re: Deciphering without knowing the algorithm?
Date: Mon, 13 Dec 1999 22:55:39 -0800
HKXLF wrote:
>
> Hi,
> I am new to cryptography although I am very interested in the subject. From
> browsing though this newgroup, I have come to a conclusion that, in order to
> decipher some message, all you need is to find the key. But how about the
> algorithm that is used the encrypt the text in the first place. Is it possible
> to decrypt some text without first knowing what algorithm is used to encrypt
> it?
>
> Anyway, I'll be grateful if anybody can satisfy my curiosity.
> Thanks,
> Herry.
HKXLF -
It is possible to decrypt text without knowing at first what the
employed cipher is. Properties of the ciphertext can reveal information
about the nature and operation of the cipher. There are books on
cryptanalysis that explain how to do this and give examples.
I'm a cryptanalysis neophyte. I'm working my way through William F.
Friedman's books on Military Cryptanalysis ( Parts I - IV )in the "Books
in the Cryptographic Series" from Aegean Park Press (You can get them
from Amazon.com). Some might say the example cipher systems are dated -
but working through the problems and examples is worth it. These are
example problems just as you described - decrypting text without first
knowing the algorithm used. Mr. Friedman shows how to determine the
likely cryptosystem used from several candidate systems by assessing the
characteristics of the ciphertext.
F.L.Bauer's "Decrypted Secrets" provides an additional overview of
cryptanalysis methods.
As for post-World War II (or post-Great Patriotic War for some readers)
cryptanalysis,
Schneier's book "Applied Cryptography" and Stinson's "Cryptography,
Theory and Practice" give examples of diffential cryptanalysis of block
ciphers. (Mr. Schneier also has a guide to self-education in block
cipher cryptanalysis at the Counterpane web site - see
http://www.counterpane.com/self-study.html ) Schneier's book covers
cryptanalysis of stream ciphers. And there's Barker's Cryptanalysis of
Shift-Register Generated Stream Cipher Systems from Aegean Park Press.
(Next on my list after I finish the 4 volume Friedman workout. )
Hope this is of some help,
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Deciphering without knowing the algorithm?
Date: 14 Dec 1999 02:08:29 EST
In article <834g8r$ou0$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Surface Mount) wrote:
>
>If you were to take a common algorithm for encryption, and modify it
>significantly, how hard would it be to decipher the message, assuming a good
>algorithm?
The problem is that there are subtleties that newbies like you and me
don't understand - your significant mod might make it really easy
to crack usinf cryptoanalysis.
Do a web search on "security through obscurity" for some very
interesting concepts related to hiding your algorithm.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Insecure PRNG?
Date: 14 Dec 1999 02:11:53 EST
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Mok-Kong Shen)
wrote:
>
>Douglas A. Gwyn wrote:
>>
>> Mok-Kong Shen wrote:
>> > Does encrypting 2 charaters out of 100
>> > results in twice the strength of encrypting 1 character out of 100?
>>
>> Just because Guy Macon doesn't have a good measure of cryptographic
>> strength doesn't mean anything one way or another for the general
>> issue of whether such a measure is possible. It is obvious, however,
>> that your question would not fit into the framework of any valid
>> measure.
>
>I have expressed my opinion that a rigorous measure is not possible
>and offered arguments. The lines you quoted is only a side remark
>intended merely to say that the issue is not so simple as Mr. Macon
>apparently has thought.
To be totally fair, I thought that the issue was really, really
hard, then your side remark showed me that it was harder than that!
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Insecure PRNG?
Date: Tue, 14 Dec 1999 09:39:43 +0100
William Rowden wrote:
>
> I don't think cryptographic security is so different from civil
> engineering design safety, except, perhaps, the state of the art. Go
> back in time, though, and you'll see, for example, that builders
> evaluated structural strength through trial-and-error. The scientific
> evaluation of structural strength in the USA didn't take full form
> until after public outcry over train bridge collapses. (Perhaps when
> everyone is using encryption...)
You may be interested to read a follow-up of mine of 13 Dec in this
thread where I commenced with the following sentence:
I personally would prefer to take an engineer's standpoint in
matters concerning crypto security.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Insecure PRNG?
Date: Tue, 14 Dec 1999 09:39:38 +0100
CLSV wrote:
>
> > At least this is what most users desire to know.
>
> I doubt that is the general case. Most commercial users would
> be happy to consult security agencies if they could (e.g. Microsoft
> NSAKEY). Most private users of security products are unaware of
> the risks and possibilities some use them but even don't care.
> That leaves only the privacy aware users with some cryptographical
> knowledge.
If they are careless as to blindly believe some slogans etc. it
is because they are either not intelligent enough or not properly
informed (this last is the responsibility of the government and also
of the crypto community in my view). But one either wants security
(seriously) or doesn't care. Those whose don't care don't belong to
the category of users in my sense. (Sorry if this was the cause of
confusion.) Those who want security certainly desire to know how
much security the system 'really' offers, even though they don't know
at all that it is very difficult or impossible to give an answer
in the sense they have in mind.
>
> > If the best academics currently can't attack a certain
> > algorithm but some three lettered agency can, that algorithm is
> > cracked, isn't it?
Let's put aside the issue of agencies, but I suupose you have no
doubt that there are analysis methods that are kept secret from
the public. Or do you need some historical facts in order to be
convinced that not all results essential to crypto are in the
public domain?
M. K. Shen
------------------------------
From: Steven Siew <[EMAIL PROTECTED]>
Subject: Re: Simple newbie crypto algorithmn
Date: Tue, 14 Dec 1999 20:17:34 +1100
My reply to peer reviews.
Eric Hambuch wrote:
>
> Steven Siew schrieb:
> >
>
> 1. Keysize is 4856 bits - too long
This is modern day and age, does people actually cares about the key
size? Does anyone really memorises keys anymore?
> 2. Your program needs more than 1.6 MBytes of memory - really too much !
> 3. It isn't fast.
It's not designed to be fast. It's designed to be secure. Again memory
was not considered by me during the design process. Security is what I'm
worried about.
> 4. It uses permutation on a 64 KByte block. I agree, that this is
> normally hard to break.
> But if you use this algorithm on smaller blocks (e.g. encryption
> stream data) I will
> become much weaker.
>
That is correct. I fail to see how I can make a 10 bytes file
crytographically secure? After all there is only 2^80 possible
combinations. So I just do my best.
> 5. Your "fibonacci generator" doen't produce a fibonacci sequence:
> fibseq = 607+1;
> {
> fibseq = ++fibseq % (FIBP+1);
> ...
> }
>
> only: 607,0,1,2,3,4,...,606,607,0,1,2,...
>
> If you had some knowledge of algebra, you would know that you should
> use a prime number
> for your modulo value (FIBP+1 isn't prime) !
>
Ah! The Fibonacci sequence I'm using is
F[n]= ( F[n-FIBQ] + F[n-FIBP] ) mod 256
Let FIBP=607 and FIBQ=273
F[n]= ( F[n-273] + F[n-607] ) % 256
Fill up array F from F[0] to F[606] with 607 random bytes
F[607]= ( F[607-273] + F[607-607] ) % 256
F[607]= ( F[ 334 ] + F[0] ) % 256
F[607]= ( F[0] + F[ 334 ] ) % 256
F[607]= ( F[(607+1)%608] + F[ (607 + (607 - 273) + 1) % 608 ] )% 256
F[seq]= ( F[ (seq+1)%(FIBP+1)] + F[(seq+(FIBP-FIBQ)+1)%(FIBP+1)] ) % 256
This way I only need a array of 608 elements. ie. F[0] to F[607]
F[608] would be stored in location F[0]
F[609] would be stored in location F[1]
and so fore.
> 6. If you can break your array fib[] you can easily remove your
> XOR-substition. And than
> try to break the permutation!
>
> Eric Hambuch
If you know the key, then yes you can break the encryption. But to
uncover the key (607 random bytes) from the cyphertext is very very
difficult. If you are thinking of uncovering F[0],F[1] to F[607] then
forget it as one array value changes on every fibonacci generation
sequence.
------------------------------
From: Steven Siew <[EMAIL PROTECTED]>
Subject: Re: Simple newbie crypto algorithmn
Date: Tue, 14 Dec 1999 20:25:14 +1100
"SCOTT19U.ZIP_GUY" wrote:
> >> 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. ...
> >
> >As you noted, there are flaws in the particular method,
> >but I want to add that Fibonacci generators *in general*
> >have been thoroughly studied and ways to crack them are
> >known. Think about it: Fibonacci sequences have a *lot*
> >of mathematical structure; that's not good from the point
> >of view of resisting analysis.
I agree. However I put it that it is still very difficult to recover
the fibonacci sequence from the cyphertext. Even in the worse case
scenario where the attacker can choose his own plaintext and observes
the cyphertext it is still difficult to determine the fibonacci sequence
because it is hidden by multiple Sboxs, an XOR and the bit shuffling
algorithmn. The whole setup is to hide the fibonacci sequence from the
attacker as once he/she cracks the sequence the game is up.
Also you may have notice the key is the initial state of the fibonacci
sequence. It is vital that the key is truely random for it determines
the randomness of the fibonacci sequence. This is a weak point I have
not yet been able to fix.
Steven Siew
------------------------------
From: Steven Siew <[EMAIL PROTECTED]>
Subject: Re: Simple newbie crypto algorithmn
Date: Tue, 14 Dec 1999 20:37:08 +1100
CLSV wrote:
>
> Steven Siew wrote:
>
> [...]
>
> 1 How many times do you have to run your algorithm for security?
> Shouldn't one time be enough? Or else define the number of cycles.
>
You are right. I went overboard that time. Yes one or twice should be
sufficient.
> > 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.
>
> 2 This is not correct.
> The number of permutations of A B C D is 4! = 24,
> the number of permutations of 1 0 1 1 is only 4.
> You are assuming 524288 different bit values while there
> are only two. A problem is that the number of permutations
> depends on the specific plaintext. A plaintext with all zeros
> has just one permutation. That could be the start of an attack.
>
> Regards,
>
> Coen Visser
Again your maths is better than mine. I actually considered that, that
is why I have three Sboxs to ensure that the plaintext is carefully
scrambled even before applying the bit shuffling algorithmn.
On the average half the bits are zero (and half are ones), so the number
of permutation is n choose (n/2)
or n! / ( (n/2)! (n/2)! )
Put n= 65536*8 = 524288
and we get [an error message on my calculator]
Steven Siew
------------------------------
From: "Tim Wood" <[EMAIL PROTECTED]>
Subject: Re: Why no 3des for AES candidacy
Date: Tue, 14 Dec 1999 10:50:04 -0000
>>>You can see why 3-DES, with it's single sized168 bit key, does not fit in
>>this
>>>categorie.
>>
>>of course it's effective key length (strength) is 112bit not 168bit...
>>
>
> it depends on how you do 3 DES
>
Very true, I simpley made the same assumptions as the original poster.....
However Is independant sub-keys still DES? when is DES not DES, what about
if you use one of the other S-box modes (such as making them
key/plaintext-dependant)?
Tim
--
**<Stolen line alert>**
>From my one-bit brain with a parity error.
**</Stolen line alert>**
>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: Why no 3des for AES candidacy
Date: Tue, 14 Dec 1999 11:03:35 -0000
Uri Blumenthal wrote in message <[EMAIL PROTECTED]>...
>> >> Why isn't 3des being considered for the AES?
<snip>
>> >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>
Why Is it incorrect in general? There are lower strength attacks, but even
then I think it would be incorrect to quote 3DES as 168bits ? It is
missleading.
Also doesn't DES include the Key schedule? a small quote from the above
paper;
<quote>
A Feistel cipher consists of two parts:
*the key schedule, which produces subkeys for each round, normally from the
�generating� or main key;
and
*scrambling�the �real� encryption, which mixes the subkey bits with the
input bits to produce the output bits.
</quote>
Not that it really matters that much, since 3DES is not a candidate.
Tim
--
**<Stolen line alert>**
>From my one-bit brain with a parity error.
**</Stolen line alert>**
------------------------------
From: CLSV <[EMAIL PROTECTED]>
Subject: Re: Insecure PRNG?
Date: Tue, 14 Dec 1999 11:31:49 +0000
Mok-Kong Shen wrote:
> CLSV wrote:
> > [...]Most private users of security products are unaware of
> > the risks and possibilities some use them but even don't care.
> If they are careless as to blindly believe some slogans etc. it
> is because they are either not intelligent enough or not properly
> informed (this last is the responsibility of the government and also
> of the crypto community in my view). But one either wants security
> (seriously) or doesn't care. Those whose don't care don't belong to
> the category of users in my sense. (Sorry if this was the cause of
> confusion.) Those who want security certainly desire to know how
> much security the system 'really' offers, even though they don't know
> at all that it is very difficult or impossible to give an answer
> in the sense they have in mind.
Maybe you are a bit harsh on part of the users. Any ignorance about
security is probably historically grown (and carefully cultivated
by commercial enterprises). The reason most users don't
know/care is the same reason I trust my bank not to invest my money
in some risky business. But times have changed. As more databases
and commercial services get connected the need for distributed
security becomes imperative. Not everyone catches up fast enough.
> Let's put aside the issue of agencies, but I suupose you have no
> doubt that there are analysis methods that are kept secret from
> the public. Or do you need some historical facts in order to be
> convinced that not all results essential to crypto are in the
> public domain?
No, no you don't have to convince me,
I share your opinion on these matters.
Regards,
Coen Visser
------------------------------
From: CLSV <[EMAIL PROTECTED]>
Subject: Re: Simple newbie crypto algorithmn
Date: Tue, 14 Dec 1999 11:45:10 +0000
Steven Siew wrote:
> [...] I actually considered that, that
> is why I have three Sboxs to ensure that the plaintext is carefully
> scrambled even before applying the bit shuffling algorithmn.
Ok. I had not read your code yet, I believe others made some
useful comments on it.
> On the average half the bits are zero (and half are ones), so the number
>
> of permutation is n choose (n/2)
>
> or n! / ( (n/2)! (n/2)! )
>
> Put n= 65536*8 = 524288
>
> and we get [an error message on my calculator]
You can use Stirlings approximation: n! = sqrt(2*PI*n)*(n/e)^n
If your calculator can not handle it, solve it algebraically.
Regards,
Coen Visser
------------------------------
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Subject: Re: How do you crack a Rotating Grille?
Date: Tue, 14 Dec 1999 12:36:19 GMT
On Tue, 14 Dec 1999 05:34:58 +0000, Jim Gillogly <[EMAIL PROTECTED]> wrote:
>UBCHI2 wrote:
>> If you are given a large board of letters, how do you determine the Grille
>> openings and rotations?
>
>The traditional method is with a crib -- place the crib by finding places
>where the letters will fit at reasonable distances in order, and see what
>results two turns along: those same holes will also be in order when the
>grille is 180 degrees away from where it started. You may need to try
>it in several places before the 180-degree rotation gives good plaintext.
>Then fill in the ones at the 90 and 270 degree rotations from your crib,
>and try to develop more plaintext to insert in the other rotations. If
>there are Q's, look for U's near them, and so on... the usual suspects.
>
>Depending on how large your square is, shotgun hillclimbing is quite
>effective -- that's the first cipher I tried it on. It works in reasonable
>time up to about 12x12 on a low-powered machine with or without a crib.
>I imagine a heavy-duty desktop or more time would take you a little further.
>--
> Jim Gillogly
> Highday, 24 Foreyule S.R. 1999, 05:29
> 12.19.6.14.2, 4 Ik 10 Mac, Third Lord of Night
I have an artificial intelligence background and I am familiar with
various forms of hill-climbing, can you give the shotgun hill-climbing
algorithm in this forum?
==Pate Williams==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: How do you crack a Rotating Grille?
Date: Tue, 14 Dec 1999 13:00:43 +0000
"James Pate Williams, Jr." wrote:
> I have an artificial intelligence background and I am familiar with
> various forms of hill-climbing, can you give the shotgun hill-climbing
> algorithm in this forum?
Briefly, you pick a random starting point in the key-space, decrypt
the ciphertext using it, then perturb the key to a neighbor, where the
concept of a neighbor depends on the cipher type, and re-decrypt. Pick
the steepest gradient... i.e. the neighbor that gives the best score.
Once you get to a local maximum, pick another random starting point and
start over. The "shotgun" part is the latter step: normally in
hill-climbing you pick a good starting point, or throw a dart at the
keyspace map and start from that. With shotgun hill-climbing you stand
back a dozen yards from the map, give it a blast, and start hill-climbing
from each starting point you hit.
For this particular cipher, the key is fully defined by assigning each
cell in (say) the top-left quadrant to the numbers 1-4, representing
the state of that cell in each of the four rotations. For an 8x8
grille that means 16 2-bit numbers, or 32 bits of key total. However,
the structure of the cipher is such that the search is much shorter
than 2^32 using this method.
Shotgun hillclimbing is useful for solving most classical ciphers, up
to about Enigma, including double transposition.
I wrote it up for "The Cryptogram", organ of the American Cryptogram
Association, in the November-December 1995 issue. See
http://www.und.nodak.edu/org/crypto/crypto/ for info on how to join;
I'm pretty sure back issues are still available.
--
Jim Gillogly
Highday, 24 Foreyule S.R. 1999, 12:52
12.19.6.14.2, 4 Ik 10 Mac, Third Lord of Night
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Deciphering without knowing the algorithm?
Date: 14 Dec 1999 12:12:22 +0100
In article <834g8r$ou0$[EMAIL PROTECTED]>,
Surface Mount <[EMAIL PROTECTED]> wrote:
> If you were to take a common algorithm for encryption, and modify it
> significantly, how hard would it be to decipher the message, assuming a good
> algorithm?
If you take an algorithm which is known to be secure, and if you
modify it, it's very likely that you'll create a much less secure
algorithm.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED]
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
** 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
******************************
