Cryptography-Digest Digest #969, Volume #12 Sat, 21 Oct 00 10:13:00 EDT
Contents:
Re: Dense feedback polynomials for LFSR (Tim Tyler)
Re: Dense feedback polynomials for LFSR (Tim Tyler)
Re: Storing an Integer on a stream (Tim Tyler)
Re: Storing an Integer on a stream (Tim Tyler)
Re: Storing an Integer on a stream (Tim Tyler)
Re: Storing an Integer on a stream (Tim Tyler)
Re: BIOS password, will it protect PC with PGPDisk against tampering ? (Guy Macon)
Re: CRC vs. HASH functions (Tim Tyler)
Re: My comments on AES (Tim Tyler)
Re: ---- As I study Rinjdael... (Tim Tyler)
Re: GCHQ Challenge (Tim Tyler)
Re: Counting one bits is used how? (Tim Tyler)
Re: Encrypting large blocks with Rijndael (John Savard)
Re: Rijndael in Perl (Rob Warnock)
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Dense feedback polynomials for LFSR
Reply-To: [EMAIL PROTECTED]
Date: Sat, 21 Oct 2000 11:17:07 GMT
Joaquim Southby <[EMAIL PROTECTED]> wrote:
: In article <[EMAIL PROTECTED]> Tim Tyler, [EMAIL PROTECTED] writes:
:>The original idea makes no sense, but execution time does not appear to be
:>a problem with it.
: Simply because you fail to grasp an idea or possible applications for it
: doesn't mean it makes no sense.
True, but not pertinent here.
: I didn't come up with this idea; it was passed on to me from a friend who
: uses me as a sounding board from time to time. She pointed out that
: sub-maximal LFSR's have most of the same behaviour as maximal LFSR's. If
: a maximal length LFSR has a tap sequence of n, A, B, C, then an LFSR with
: the tap sequence n, n-A, n-B, n-C will also be maximal length. Guess
: what -- it works for sub-maximal LFSR's, too. The state spaces of two
: sub-maximal LFSR's constructed in that way and using the same init vector
: are the same size. [...]
Which might be interesting - if you had provided a method of identifying
which LFSRs had a large period that does not involve stepping through the
states one at a time, and noticing when they repeat.
[FWIW, I know such methods exist - but do not know of any useful ones.]
Since this appears to be the best approach you've mentioned, the results
will not have a guaranteed minimum period greater than what you can step
through. Consequently, they are only known to offer protection against
attackers with resources less than or equal to your own.
Perhaps you would buy such a device. To me it appears to have nothing but
disadvantages compared to a maximal period LFSR.
: One group of behaviours that is dissimilar between the two is how
: "random" the output stream looks. The output over a period of a
: maximal-length LFSR will *always* have the same characteristics: a) # of
: 1's minus # of 0's = 1; [...]
# of 1s minus # of 0s = n where n = register width?
: b) the number of runs is strictly quantifiable -- 1/2 of all runs have
: length 1, 1/4 have length 2, etc.; c) perform a circular shift of some
: number less than the period on the output string and then XOR the
: result with the original string -- the result of the XOR will exhibit
: the same characteristics described in a) and b).
: Conversely, the output over a period of a submaximal-length LFSR is not
: constrained to these characteristics. (The autocorrelation exhibited in
: part c is still very strong, though.) In that regard, this output looks
: more like a random stream of bits because it will statistically vary from
: the idealized output described above. [...]
No! If anything it looks less like a random stream - since it has a
shorter period.
: (Before anyone jumps in with the old "what is random" thread, I did not
: say that the output is random -- I said it looks more like a random
: stream than that of the maximal-length LFSR.) Can you see any possible
: uses for a sub-maximal LFSR now?
The idea that its output is less likely to exhibit statistical anomolies
than a conventional LFSR appears to be false.
Yes, the output over a period is no longer balanced (give or take n 0s)
- but try writing a statistical test to detect that. The same goes for
the runs. You might as well iterate until you've found the period - a
test which the non-maximal LFSR will fail first.
Both algorithms fall equally to Berlekamp-Massey, of course.
: These puppies are a lot more interesting than their maximal-length
: brethren simply because of the wider range of behaviour that, AFAIK,
: hasn't been explored yet.
Nobody's interested in them - but with good reason. Generally the whole
point of using an linear counter is to cheaply get some guaranteed long
cycles. Miss out this property, and what remains is of low utility.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Dense feedback polynomials for LFSR
Reply-To: [EMAIL PROTECTED]
Date: Sat, 21 Oct 2000 11:29:40 GMT
Joaquim Southby <[EMAIL PROTECTED]> wrote:
: In article <[EMAIL PROTECTED]> Tim Tyler, [EMAIL PROTECTED] writes:
:>: One of the most straightforward ways of checking to see if a polynomial
:>: is primitive is to use it as the tap sequence of an LFSR, plug in an init
:>: vector, and start clocking. If one were to note not only the primitive
:>: polynomials (i.e., those that made it to 2^n - 1 clocks before repeating
:>: the init vector), but also those that happened to show a large state
:>: space for that init vector (i.e., a large number of clocks before
:>: repeating the init vector), a library of such sub-maximal LFSR's could be
:>: built. [...]
:>
:>This is an exhaustive search.
: I'm curious about your definition of "exhaustive search". [...]
I'm not sure I can be pinned down there.
However, I know that stepping an LFSR repeatedly until it returns to its
starting state is pretty "exhaustive" method of determining its period -
in the sense that if you tried it, you would probably soon be exhausted ;-)
:>You're never going to get vary large guaranteed minimum period,
:
: As I've said before, some of the state spaces of non-maximal LFSR's can
: contain almost all the possible state space of the given register --
: sometimes up to 99% of it. [...]
I don't dispute this - the problem is finding which LFSRs fit into this
category. If your approach involves iterating through their state spaces
(as it currently seems to) "you're never going to get vary large
guaranteed minimum period" - because you'll die before you can verify that
a large period exists.
The idea in cryptography is to defend against opponents who have more
computational resources than either communications partner.
Defending against attackers who have less comutational resources than
you do would not be a very compelling result.
:>: Advantage: very easy to choose a suitable key. With a sub-maximal LFSR,
:>: the known init vector is seeded to the LFSR, then the LFSR is clocked a
:>: number of times equal to the key value before using the stream output.
:>: Advantage: key can be larger than 2^n since the clock count will
:>: effectively be the key moduloed by the size of the state space.
:>
:>You call discarding much of the information in your key an "advantage"?
:
: I misspoke on this; I was thinking of something else similar in nature.
: The salient point that you missed here is that (key modulo state space)
: reduces the actual key space to the size of the state space.
To avoid your neglecting the point I raised, what I had a problem with was
calling this an "advantage" of using non-maximal period LFSRs.
The key value can be larger than 2^n when using an maximal LFSR as
well - if your approach to using the extra key material is to throw
it away.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Storing an Integer on a stream
Reply-To: [EMAIL PROTECTED]
Date: Sat, 21 Oct 2000 11:50:18 GMT
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] (Benjamin Goldberg) wrote:
:>SCOTT19U.ZIP_GUY wrote:
:>> SORRY http://members.xoom.com/ecil/compres8.htm
:>>
:>> >> If the file data is in whole bytes. and the padding starts on a
:>> >> word boudary.
:>> >
:>> >That sentence no verb.
:>>
:>It would be nice, if you said HOW the code does that. I'm writing this
: for the method that adds a pointer to a file I use a special input
: file that has a long attached at end for the pointer. My code DSC
: takes any file of this form converts it to a binary file X
: such that for any file X then DSC( UNDSC (X)) = X
: and any file X that is a 8bit byte binary. will be converted to
: a underlying data file. with a long attached that represents a pointer
: to a byte in the file.
This is almost - but not quite - something I was looking for a while ago.
I believe this code adds an arbitrary "long" value to a file.
If used with a file with appended padding, this could be used to show
where the padding starts.
However, the problem is that the pointer may be larger than the length of
the file.
(Unless care is taken) this means an attacker might be able to reject
decrypted messages if they have "impossible" padding pointers.
What it would be good to have is a method of adding a number to the end
of a file with the value of the number being between 0 and the length
of the file.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Storing an Integer on a stream
Reply-To: [EMAIL PROTECTED]
Date: Sat, 21 Oct 2000 12:27:10 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
: :>SCOTT19U.ZIP_GUY wrote:
: :>> SORRY http://members.xoom.com/ecil/compres8.htm
: This is almost - but not quite - something I was looking for a while ago.
: I believe this code adds an arbitrary "long" value to a file.
: If used with a file with appended padding, this could be used to show
: where the padding starts.
: However, the problem is that the pointer may be larger than the length of
: the file. [snip]
: What it would be good to have is a method of adding a number to the end
: of a file with the value of the number being between 0 and the length
: of the file.
That will teach me to speak before reading the documentation.
In fact the code appears to do everyting I was hoping for.
To quote from the documentation:
``This program takes a file of the form [data block][ Last ]
where the Data is made up of 1 to N bytes and the value
of Last which is in range exactly from 0 to N-1. [...]
This program takes any string of bytes and converts
it uniquely to a string of bytes followed by a long data word
which is exactly constrained to be in the range of 0 to N-1.''
Assuming David's claims are correct, this program works while adding the
minimum possible known plaintext to the file - namely zero bits.
I would identify this as an object of great potential significance to
people who want to find the best way of padding their files out with
random data, to best conceal the lengths of their files from atatckers, or
prior to performing a AONT to help defend against known-partial plaintext
attacks.
For those looking for explanations relating to how the code works,
perhaps look at the comments in the undsc.cpp file in the distribution (in
particular the from_bwt() method). The code appears to be sophisticated
- and I don't pretend to understand it all at the moment - but the author
has put in some effort to explaining how it works for those with an
appropriate background.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Free gift.
------------------------------
Crossposted-To: comp.compression
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Storing an Integer on a stream
Reply-To: [EMAIL PROTECTED]
Date: Sat, 21 Oct 2000 12:39:26 GMT
In sci.crypt Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
: As believe I've already stated, the task in question isn't really about
: describing a file length, that's merely an example of using it. The
: task in question is about storing an arbitrary sized integer on a bit or
: byte stream. [...]
In fact, storing an integer representing some fraction of the file length
is the guts of the problem. Tacking on an arbitrary integer is relatively
simple by comparison.
It's the former construction that has the most relevance to cryptographic
padding schemes.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
Crossposted-To: comp.compression
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Storing an Integer on a stream
Reply-To: [EMAIL PROTECTED]
Date: Sat, 21 Oct 2000 12:49:05 GMT
: Andras Erdei wrote:
:> The method i like most is fibonacci coding:
:>
:> - start with the largest fib number smaller than your integer
:>
:> - if the current fib number is smaller than your number
:> substitute it and write down 1
:> else
:> write down 0
:> - take the next fib number
:>
:> Example:
:>
:> number: 15
:> fib: 1,1,2,3,5,8,13
:> encoding: 13+2 -> 0010001
:>
:> This way you encoded your (arbitrarily big number) in a way that
:> there are *no consecutive 1s* in the encoding, and it ends with 1;
:> so you can append an additional 1 and thus make it a prefix code.
:>
:> result: 00100011
:>
:> IIRC this encoding is asimptotically optimal.
"Severly sub-optimal" is how I would describe it, especially in the
context of padding schemes.
Padding with a format that can't use repeated 1s could only ever be
anywhere near optimal for small values.
Since when larger and larger values are used, methods which can use a
greater range of symbols will systematically trounce it, it's hard to see
how it could be described as "asymtotically optimal".
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: BIOS password, will it protect PC with PGPDisk against tampering ?
Date: 21 Oct 2000 12:56:54 GMT
Seeker wrote:
>
>> Many modern motherboards use flash, and the battery trick doesn't work.
>
>In that case a BIOS decryptor with a boot disk could work.
..except that you need to enter the BIOS password before you
can boot...
>Either way, I think the point is that relying on a BIOS password
>is far from the most secure solution.
Agreed. The other point is that it's not as trivial to defeat on
some modern motherboards than it was in the Good Old Days.
I defeat BIOS passwords by programming a BasicX Stamp (www.basicx.com)
to emulate a keyboard, and let it run a brute force search in the
corner for a cople of days (or weeks - some BIOSes make each trial
take a long time).
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: CRC vs. HASH functions
Reply-To: [EMAIL PROTECTED]
Date: Sat, 21 Oct 2000 13:01:09 GMT
Bryan Olson <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] (Mack) wrote:
:> >Mack wrote:
:> >> CRC's are generally best for: [entropy distillation]
:> 128 bit CRCs are easier to implement both in software
:> and hardware than secure hash functions. Another
:> thread suggested that a hash may be made as fast as
:> a CRC but only at the expense of silicon space.
: CRCs are certainly the winner in hardware speed. I don't
: think the other poster was right that cryptographic hashes
: can be as fast in hardware, at least not for the popular
: ones such as SHA-1.
I believe the "other poster" was me.
To reiterate, my claim is not that secure cryptographic hash functions can
be made as fast in hardware as CRCs.
My claim was that *throughput* through most secure hash functions can be
made extremely rapid in hardware, by laying out the rounds in physical
rows and allowing more data to pass into the inputs of the hash before
the current data has been completely processed.
This will make a hardware implementation of a hash very fast - but it
*still* may not match that of a CRC because:
a) the round function may be complex and slow to compute;
b) there are more components, and thus greater problems getting
synchronous operation. This is likely to negatively impact performance.
My argument is that speed issues with hashes could be reduced to be a
relatively minor concern in the context of entropy distillation
applications - *if* silicon area is available. Choosing a hash with a
large number of simple and rapid rounds would help still further.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: My comments on AES
Reply-To: [EMAIL PROTECTED]
Date: Sat, 21 Oct 2000 13:06:49 GMT
Stephen M. Gardner <[EMAIL PROTECTED]> wrote:
: Runu Knips wrote:
:> Bruce Schneier wrote:
:> > http://www.counterpane.com/crypto-gram-0010.html#8
:>
:> Seems to me that Schneier also believes Rijndael is breakable.
: Let's read what he actually said: [snip]
: Now what makes you think that he said it was breakable.
How about the bit where he wrote (from the URL above):
``I believe that within the next five years someone will discover an
academic attack against Rijndael.''
...?
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: ---- As I study Rinjdael...
Reply-To: [EMAIL PROTECTED]
Date: Sat, 21 Oct 2000 13:10:59 GMT
Eric Lee Green <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] wrote:
:> That narrows the choice to a) use Rijndael, and provide advesaries
:> with complete documentation of the algorithm, and test vectors. Or b)
:> use an equally strong system and make advesaries guess the algorithm.
: Or c), say nothing, and make adversaries guess as to what algorithm they're
: using. Could you tell, just by looking at a file, whether it was
: encrypted via Rijndael, 3DES, IDEA, or NSA256?
I can partly distinguish between sets of files encrypted with the above
algorithms. All I do is look at the size of the blocks.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: GCHQ Challenge
Reply-To: [EMAIL PROTECTED]
Date: Sat, 21 Oct 2000 13:16:11 GMT
Pom <[EMAIL PROTECTED]> wrote:
: Probably a dumb question - has anyone seen the GCHQ Challenge at
: www.gchq.gov.uk - I stumbled accross it, and immediately found one clue -
: can anyone point me towards any info on this?
Solution: http://widget.ecn.purdue.edu/~simmo/gchq.html
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Counting one bits is used how?
Reply-To: [EMAIL PROTECTED]
Date: Sat, 21 Oct 2000 13:33:15 GMT
Rob Warnock <[EMAIL PROTECTED]> wrote:
[Galois/Fibonacci LFSRs]
: I have at least one text that claims that the two feedback styles
: can generate the same output-bit-stream sequence if one style uses
: the reciprocal polynomial of the other.
This is news to me. http://www.dacafe.com/Book/CH14/CH14.7.htm
suggests that there are four ways of building an LFSR out of
a primitive polynomial (and its reciprocal) and that they all produce
different random sequences. Maybe there's a trick I don't know about.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Free gift.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Encrypting large blocks with Rijndael
Date: Sat, 21 Oct 2000 13:43:08 GMT
On Fri, 20 Oct 2000 12:57:40 -0600, John Myre <[EMAIL PROTECTED]>
wrote, in part:
>Fine. Under what circumstances would the increase in
>security over 128-bit blocks be justified?
Probably fairly seldom, in practice.
If you are using a 256-bit session key with 128-bit blocks of data,
however, you might want to exchange it using Rijndael with a 256-bit
block size if you are using a symmetric key-exchange key in your
protocol.
That is one area where the flexibility of having different block sizes
might be useful.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Rob Warnock)
Crossposted-To: comp.lang.perl.misc
Subject: Re: Rijndael in Perl
Date: 21 Oct 2000 09:12:19 GMT
Runu Knips <[EMAIL PROTECTED]> wrote:
+---------------
| > attacker looks at what's "left behind" (tempfiles, diskswapping...).
|
| Is it actually possible with Windows or Linux to get memory which isn't
| swappable ? As an ordinary user process, or as a administrator process ?
+---------------
Most Unixes -- e.g., Linux, FreeBSD, SGI's Irix, many others -- have
"mlock(2)" or "mpin(2)" or "plock(2) or something similar [Irix has
all three!]:
NAME
mlock, munlock - lock or unlock pages in memory
SYNOPSIS
#include <sys/types.h>
#include <sys/mman.h>
int mlock(const void *addr, size_t len);
int munlock(const void *addr, size_t len);
DESCRIPTION
mlock locks the pages associated with the address range (addr, addr +
len) into memory. The super-user can lock as many pages as it wishes,
other users are limited to a per process maximum {PLOCK_MAX}.
...
Dunno 'bout Windows, though...
-Rob
=====
Rob Warnock, 31-2-510 [EMAIL PROTECTED]
Network Engineering http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
1600 Amphitheatre Pkwy. PP-ASEL-IA
Mountain View, CA 94043
------------------------------
** 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
******************************
