Cryptography-Digest Digest #455, Volume #11 Fri, 31 Mar 00 13:13:01 EST
Contents:
Re: The NSA's little NCSC bots (Richard Herring)
Re: Chronometric Cryptography ("Dan Coyle")
LFSR's (Pascal JUNOD)
Hoey's algorithm? ([EMAIL PROTECTED])
Re: Chronometric Cryptography (Gareth Howell)
Re: crypto books (Tim Tyler)
Re: Chronometric Cryptography (John Myre)
Re: Sunday People 26/3/2000: "FORGET YOUR PASSWORD... END UP IN JAIL" (Your Name)
Re: Q: Entropy ("Douglas A. Gwyn")
Re: Examining random() functions (Mok-Kong Shen)
Re: LFSR's (Tim Tyler)
Re: Sunday People 26/3/2000: "FORGET YOUR PASSWORD... END UP IN JAIL" ("PJS")
Re: OAP-L3: Semester 1 / Class #1 All are invited. (Taneli Huuskonen)
Re: Chronometric Cryptography (Mok-Kong Shen)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Richard Herring)
Subject: Re: The NSA's little NCSC bots
Date: 31 Mar 2000 11:23:05 GMT
Reply-To: [EMAIL PROTECTED]
In article <UWKE4.4592$[EMAIL PROTECTED]>, Remove NO_SPAM to reply
([EMAIL PROTECTED]) wrote:
> They may do a combination of bots and humans. In my case (actually,
> cases) it was humans. How do I know? Because they didn't follow
> every link, because they clicked only on links that one would expect
> them to be interested in, because they took up to a minute to go from
> one page to the next.....
Don't be too sure. I think we can safely assume that they have
heard of the Turing test :-)
--
Richard Herring | <[EMAIL PROTECTED]>
------------------------------
From: "Dan Coyle" <[EMAIL PROTECTED]>
Subject: Re: Chronometric Cryptography
Date: Fri, 31 Mar 2000 06:58:39 -0600
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Dan Coyle wrote:
> >
>
> > A simple solution to this problem would be to create a cipher that uses
> > processing time as a primary determinate for it's measure of security.
That
> > is, create a cipher that took just as long to encrypt any given
plaintext
> > into ciphertext, as it does to convert that ciphertext back into
plaintext.
> > Therefore allowing the application/object to determine the measure of
> > security at run-time instead of design-time. In addition, when
technology
> > changes, and more powerful machines are made that can resolve ciphertext
> > back into plaintext using brute force methods, the hardware which
executes
> > the cipher is the only component that what would need upgrading because
the
> > cipher would still take the same amount of time to execute, it just gets
> > more cycles to do it's job. I call this type of cipher, a Chronometric
> > cipher meaning a cipher whose security is measured by time.
>
> One problem you should note is that you generally don't exactly
> know the resources of the opponent. He may have 100, 1000 or 10000
> processors. So the moderate factor of increase in MHZ of chips
> with time is not that determining, I suppose.
>
> If you have (or believe to have) an idea of how long the (proper,
> i.e. knowing the key) decryption time should be in order to render
> the brute force time of the opponent imfeasible, then the best way
> I believe is to use a cipher that is parametrized in diverse
> aspects, in particular in the number of rounds. Through tuning
> the parameters you could arbitrarily increase the processing time
> to that you want. See my humble WEAK3-EX available on my web page.
>
> M. K. Shen
> ------------------------------
> http://home.t-online.de/home/mok-kong.shen
It's kind of Ironic, I was originally trying to create an Arbitrary Key size
algorithm, like WEAK3-EX, when I hit upon the Idea of a Chronometric
Cipher.
Even if the opponent has access to 100,000 processors, with which he/she may
use for a Brute Force attack, each processor will need to do an arbitrary
amount of work, even with the correct key, to decrypt a message. If the
attacker doesn't tell the processors to do enough work, the Brute Force
attack would not succeed, even if they stumbled upon the correct key. Once
more, a machine that tries to decrypt a message, and uses an incorrect key,
will come up with an incorrect starting key, and therefore will not only
incorrectly decrypt the message, but it would take, statistically, 2^127(128
bit key) decryption passes, before the algorithm would declare the message
decrypted, and that decrypted message would still be incorrect. The only
way an attacker could, feasibly, brute force the message, would be to guess
how many iterations the program performed upon the message, and after
decrypting that many iterations, declare that key void, and move on. And
like I said before if they are incorrect in guessing the number of
iterations, and guess too low a number, the message can never be
successfully decrypted.
Thanks
DC
------------------------------
Date: Fri, 31 Mar 2000 14:15:43 +0000
From: Pascal JUNOD <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: LFSR's
Let be the irreducible polynom x^63 + x + 1 over GF(2).
It describes a LFSR (linear feedback shift register), which is pretty
easy to
implement in software.
Let's just speak about the period, not about the cryptographic security
of the generated bits.
The polynomial being irreducible, it produces a sequence of bits
(normally the lsb of each states) with a period of 2^64 -1.
Now, instead of taking the lsb, we could take bit #56 or #2 or any one
of the 64
bits of the internal state.
All these possible sequences have a period of 2^64 - 1,or am I wrong ?
Now, if we output the whole internal state, we produce a sequence of
2^64 - 1
values of 64 bits each, or 64*(2^64-1) bits. Am I right ?
What is the period of such a sequence, if we look at it as a _bit_
sequence ?
A+
Pascal
--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Pascal Junod, [EMAIL PROTECTED] *
* Route d'Yverdon 25, CH-1028 Préverenges, Switzerland *
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
------------------------------
From: [EMAIL PROTECTED]
Subject: Hoey's algorithm?
Date: Fri, 31 Mar 2000 14:13:12 GMT
Anyone heard of Hoey's initial permutation algorithm? It is
apparently an optimised IP operator for DES that is used to prepare
input text for encryption using odd/even interleaved keys. I need
further details.
-- Jeff Hill
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Gareth Howell <[EMAIL PROTECTED]>
Subject: Re: Chronometric Cryptography
Date: Thu, 30 Mar 2000 17:15:10 +0200
"Dan Coyle" <[EMAIL PROTECTED]> wrote:
> Therefore allowing the application/object to determine the measure of
> security at run-time instead of design-time. In addition, when technology
> changes, and more powerful machines are made that can resolve ciphertext
> back into plaintext using brute force methods, the hardware which executes
> the cipher is the only component that what would need upgrading because the
> cipher would still take the same amount of time to execute, it just gets
> more cycles to do it's job. I call this type of cipher, a Chronometric
> cipher meaning a cipher whose security is measured by time.
>
I'm not quite sure what you mean by "more work".
Does this mean encrypting it again with the same cipher ? (Like 3DES ?)
Cheers
Gareth
--
Have courage for the great sorrows of life and patience for the small ones;
and when you have laboriously accomplished your daily task, go to sleep in
peace. God is awake."
- Victor Hugo
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: crypto books
Reply-To: [EMAIL PROTECTED]
Date: Fri, 31 Mar 2000 15:26:05 GMT
G. R. Bricker <[EMAIL PROTECTED]> wrote:
: [...] download the "Classical Cryptanalysis" course by LANAKI
: (search for LANAKI).
http://www.fortunecity.com/skyscraper/coding/379/lesson1.htm
--
__________
|im |yler The Mandala Centre http://mandala.co.uk/ [EMAIL PROTECTED]
Classified tagline. Please enter password:_
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Chronometric Cryptography
Date: Fri, 31 Mar 2000 08:33:52 -0700
Actually this seems related to a technique called "key stretching".
(I saw it at http://www.counterpane.com/low-entropy.html).
The basic idea is to take your starting key, then encrypt it or
hash it N times to get your operational key. Then you just
encrypt/decrypt your messages normally with the operational key.
A brute-force key search is now N times as hard.
If you can use the stretched key more than once, it saves you
(computing) effort, without helping the attacker. That is,
you can amortize the cost of computing the key over the number
of messages you encrypt with it.
>From what I've seen, N is usually taken to be 2^t, where t is
some pre-determined number of extra key bits you want. One could
instead do as you suggest, and iterate the key modification for
a given amount of time. I suppose you should count while you
go, and send N to the reciever for decryption.
John M.
------------------------------
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,uk.politics.censorship
Subject: Re: Sunday People 26/3/2000: "FORGET YOUR PASSWORD... END UP IN JAIL"
From: [EMAIL PROTECTED] (Your Name)
Date: Fri, 31 Mar 2000 15:47:11 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
>If they were done in the traditional way, with a men in berets waving guns
>and making statements about a victory for people's freedom and so on, you
>may be right, but imagine if Straw were simply run over in the street or
>shot by someone completely anonymous.
There is a most excellent paper, "Assassination
Politics" by Jim Bell at
http://www.zolatimes.com/v2.26/jimbell.htm
which shows how the technology of PK Encryption,
anonymous digital cash, and the internet can be
used to effect political assassinations in order
to restore freedom.
--Rich
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Fri, 31 Mar 2000 14:50:09 GMT
Pascal JUNOD wrote:
> entropy H(X) = - sum p_i * log_2 (p_i)
> where the sum is taken over all the elements with a probability > 0.
You can include all elements. In all such formulas in information
theory, 0*log(0) is properly taken as 0. (When *implementing* the
formulas, one needs to take this into account, not just go ahead
and compute log(0).)
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Examining random() functions
Date: Fri, 31 Mar 2000 19:08:48 +0200
Tim Tyler wrote:
>
> A KSTEST of those values yields 1.000000'
>
> If there are many 1.0000 or 0.0000 values in the table the generator fails.
>
> This is indicated clearly enough in the final "KSTEST" figure.
But you are requiring the user to do some other work and the
question remains whether applying KSTEST is the only optimal
step to be applied to interprest the results coming from Diehard,
I suppose. (I mean an inexperienced user needs sort of 'recipe'.)
M. K. Shen
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: LFSR's
Reply-To: [EMAIL PROTECTED]
Date: Fri, 31 Mar 2000 16:41:53 GMT
Pascal JUNOD <[EMAIL PROTECTED]> wrote:
: [...] irreducible polynom x^63 + x + 1 over GF(2) [...based LFSR]
: Let's just speak about the period [...]
: The polynomial being irreducible, it produces a sequence of bits
: (normally the lsb of each states) with a period of 2^64 -1.
: Now, instead of taking the lsb, we could take bit #56 or #2 or any one
: of the 64 bits of the internal state.
: All these possible sequences have a period of 2^64 - 1,or am I wrong ?
You're right.
: Now, if we output the whole internal state, we produce a sequence of
: 2^64 - 1 values of 64 bits each, or 64*(2^64-1) bits. Am I right ?
Yes.
: What is the period of such a sequence, if we look at it as a _bit_
: sequence ?
*Probably* n x (2^n - 1) = 64 x (2^64 - 1) in this case.
In general, the chances of this period being attained are probably
greatest when (2^n - 1) and n are prime.
--
__________ Hexagonal Engineering http://hex.org.uk/ [EMAIL PROTECTED]
|im |yler Lotus Artificial Life http://alife.co.uk/ Be good,
The Mandala Centre http://mandala.co.uk/ do good.
------------------------------
From: "PJS" <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,uk.politics.censorship
Subject: Re: Sunday People 26/3/2000: "FORGET YOUR PASSWORD... END UP IN JAIL"
Date: Fri, 31 Mar 2000 18:58:04 +0100
Your Name wrote in message <3M3F4.111$[EMAIL PROTECTED]>...
>In article <[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] says...
>
>>If they were done in the traditional way, with a men in berets waving guns
>>and making statements about a victory for people's freedom and so on, you
>>may be right, but imagine if Straw were simply run over in the street or
>>shot by someone completely anonymous.
>
>There is a most excellent paper, "Assassination
>Politics" by Jim Bell at
>
>http://www.zolatimes.com/v2.26/jimbell.htm
>
>which shows how the technology of PK Encryption,
>anonymous digital cash, and the internet can be
>used to effect political assassinations in order
>to restore freedom.
==========
FNORD.
------------------------------
From: [EMAIL PROTECTED] (Taneli Huuskonen)
Crossposted-To: talk.politics.crypto
Subject: Re: OAP-L3: Semester 1 / Class #1 All are invited.
Date: 31 Mar 2000 21:02:57 +0300
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
In <[EMAIL PROTECTED]> Anthony Stephen Szopa
<[EMAIL PROTECTED]> writes:
[...]
>Introduction then we will proceed with Mr. Huuskonen's point about
>the random number generator possibly having a weakness.
Strike the "possibly" - it does have a weakness, and below you can
find the code that I wrote to verify my own reasoning. You need to
supply a routine that either directly computes the random digit at the
given index or reads it from a file. It's the first function in the
programme.
Taneli Huuskonen
#include <stdio.h>
#include <stdlib.h>
#define FAC10 3628800 /* 10! */
#define BLOCKLEN 1000 /* can be
#define NBLOCKS 100 /* 100 is enough
#define UNKNOWN '?'
/*
* The known output of the PRNG is stored here.
* New known values are added as they are found out.
*/
char oap[ BLOCKLEN+NBLOCKS ][ BLOCKLEN ];
/* The following function returns the ASCII code for the
* (i * FAC10 + j)'th digit that is output by the PRNG
* (beginning with the 0'th).
* It is used both to initialize the known values in the array
* and to check the results of the cracking algorithm.
*/
char oapfun( unsigned i, unsigned j )
{
XXXXXX
}
/* The following function inserts NBLOCKS blocks of BLOCKLEN known
* digits into the array oap, and fills the rest of the array
* with the code for unknown values.
*/
void init_oap( void )
{
unsigned i, j;
for (i=0; i<NBLOCKS; i++) {
for (j=0; j<BLOCKLEN; j++) {
oap[ i ][ j ] = oapfun( i, j );
}
}
for (i=NBLOCKS; i<NBLOCKS+BLOCKLEN; i++) {
for (j=0; j<BLOCKLEN; j++) {
oap[ i ][ j ] = UNKNOWN;
}
}
}
/* This function handles a single inference of the form
* "The values at b1 * 10! + offset and b2 * 10! + offset
* are the same."
* It verifies its correctness and then checks whether this
* piece of information yields a new known output digit.
*/
void infer_oap( unsigned b1, unsigned b2, unsigned offset )
{
if (oapfun( b1, offset ) != oapfun( b2, offset )) {
/* Wrong inference?? that's a fatal error! */
fprintf(stderr, "BUG: b1=%u, b2=%u, o=%u\n", b1, b2, offset );
exit( 1 );
}
/* The inference is correct - did we get any new information? */
if ((oap[ b1 ][ offset ] == UNKNOWN) && (oap[ b2 ][ offset ] != UNKNOWN)) {
oap[ b1 ][ offset ] = oap[ b2 ][ offset ];
printf( "oap[ %5u ][ %5u ] = %c\n", b1, offset, oap[ b1 ][ offset ] );
}
}
/* The name tells it all. */
void crack_oap( )
{
unsigned i, j, k, l;
for (i=10; i<BLOCKLEN; i++) {
for (j=0; j<NBLOCKS-10; j++) {
for (k=j+10; k<NBLOCKS; k+=10) {
if (oap[ k ][ i ] == oap[ j ][ i ]) {
for (l=10; l<=i; l+=10) {
infer_oap( k+l, j+l, i-l );
}
}
}
}
}
}
int main( )
{
init_oap( );
crack_oap( );
return 0;
}
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBOOToIl+t0CYLfLaVEQK5rQCfTmq96cayKhUE0mYiQP2TLGLpjDMAnRa9
/QuIudgQ/LkBocp/QArLjfop
=F1da
=====END PGP SIGNATURE=====
--
I don't | All messages will be PGP signed, | Fight for your right to
speak for | encrypted mail preferred. Keys: | use sealed envelopes.
the Uni. | http://www.helsinki.fi/~huuskone/ | http://www.gilc.org/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Chronometric Cryptography
Date: Fri, 31 Mar 2000 20:11:04 +0200
Dan Coyle wrote:
>
> It's kind of Ironic, I was originally trying to create an Arbitrary Key size
> algorithm, like WEAK3-EX, when I hit upon the Idea of a Chronometric
> Cipher.
>
> Even if the opponent has access to 100,000 processors, with which he/she may
> use for a Brute Force attack, each processor will need to do an arbitrary
> amount of work, even with the correct key, to decrypt a message. If the
> attacker doesn't tell the processors to do enough work, the Brute Force
> attack would not succeed, even if they stumbled upon the correct key. Once
> more, a machine that tries to decrypt a message, and uses an incorrect key,
> will come up with an incorrect starting key, and therefore will not only
> incorrectly decrypt the message, but it would take, statistically, 2^127(128
> bit key) decryption passes, before the algorithm would declare the message
> decrypted, and that decrypted message would still be incorrect. The only
> way an attacker could, feasibly, brute force the message, would be to guess
> how many iterations the program performed upon the message, and after
> decrypting that many iterations, declare that key void, and move on. And
> like I said before if they are incorrect in guessing the number of
> iterations, and guess too low a number, the message can never be
> successfully decrypted.
To avoid potential confusions due to what you said about my algorithm,
let me first say that in the EX-version of the algorithm the key is
constant (56 bits in order to be conform to Wassenaar), but in the
original version (without the suffix EX) the key length could be
user choosen. The key length in my algorithm however does not affect
the processing time, because that's the seed for pseudorandom number
generation. There is on the other hand a parameter specifying the
the number of pseudo-random numbers to be combined into one number
through addition mod 1 before being used by the block encryption
part of the algorithm. If this parameter is e.g. set to 2, the
processing time is doubled. Another parameter is the number of
rounds. Using more rounds increases the processing time
correspondingly. Through tuning these two parameters, practically
any augmentation factor of the processing time can be obtained.
I was mentioning 10000 processors mainly to express my view that
the use of more processors by the opponent is likely to be a more
influencial factor demanding setting a high processing time threshold
to defeat brute force than the increase in chip processing speed
due to advancement in technology. The argument does not detract,
though, from the fact that, in order to defeat brute force, one needs
to increase the processing time.
>From a global standpoint we are doing similar things, namely
employing what I call the paradigm of Security through Inefficiency.
Your number of iterations is also a parameter that the user
can freely choose, just like the parameters in my algorithm. At a
lower level, of course, we go in quite different directions.
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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
