Cryptography-Digest Digest #973, Volume #12 Sat, 21 Oct 00 21:13:01 EDT
Contents:
Re: Visual Basic (Sundial Services)
Re: Quasi philosphical question regarding Index of Coincidence (John Savard)
Re: Dense feedback polynomials for LFSR (Joaquim Southby)
Re: Storing an Integer on a stream ([EMAIL PROTECTED])
Re: Storing an Integer on a stream ([EMAIL PROTECTED])
Re: BIOS password, will it protect PC with PGPDisk against tampering ? ("Jonathan")
Re: Hypercube structure / balanced block mixing (Benjamin Goldberg)
Re: How about the ERIKO-CHAN cipher? (Benjamin Goldberg)
----------------------------------------------------------------------------
Date: Sat, 21 Oct 2000 16:45:31 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Visual Basic
Yes, bit, they exist and someone has already posted one.
What's more practical is to get (or buy) a cipher package that, ideally,
is packaged as an ActiveX (OCX) control. Then simply call its methods
appropriately. DLLs (dynamic link libraries) can also be called from VB
although it takes a little bit more work.
Cipher algorithms usually require so much "bit twiddling" that it is
much more efficient for the cipher core to be done in a compiled
language. Visual Basic is simpler for the less compute-intensive tasks.
>binary digit wrote:
>
> Anyone know where I can find some encryption algorithms that have been coded
> in Vb and have good documentation on them?
==================================================================
Sundial Services :: Scottsdale, AZ (USA) :: (480) 946-8259
mailto:[EMAIL PROTECTED] (PGP public key available.)
> Fast(!), automatic table-repair with two clicks of the mouse!
> ChimneySweep(R): "Click click, it's fixed!" {tm}
> http://www.sundialservices.com/products/chimneysweep
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Quasi philosphical question regarding Index of Coincidence
Date: Sat, 21 Oct 2000 23:46:06 GMT
On Sat, 21 Oct 2000 20:23:11 GMT, [EMAIL PROTECTED] wrote, in part:
>If your faced with a cryptogram which includes both upper and lower case
>letters, who would you calc the IC? Would you first convert all the
>letters to one case and look only at frequency? Or do you consider "I"
>as a seperate symobol from "i"?
That depends strongly on the particular encoding scheme used. 8-bit
ASCII? A 52-character set? A Huffman encoding?
Using a 52-character set just to allow upper- and lower- case would be
awfully wasteful, and thus it would weaken the cipher used, by
providing redundancy.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Joaquim Southby <[EMAIL PROTECTED]>
Subject: Re: Dense feedback polynomials for LFSR
Date: 21 Oct 2000 23:56:41 GMT
In article <[EMAIL PROTECTED]> Trevor L. Jackson,
[EMAIL PROTECTED] writes:
>There's a logical gap here. In order to claim something "looks more random"
>one must provide a criteria by which one detects the degree of randomness. My
>criteria leads to the conclusion that fractional LFSR periods are far less
>random looking than their maximal versions because the missing bit patterns are
>glaring artifacts.
>
>So, I'll show you mine if you show me yours (tersely). What "looks random" to
>you?
>
I was speaking in regards to the randomness postulates as expressed by
Golomb. The output over a period of a maximal-length LFSR meets those
postulates exactly. A random stream of bits will approach those
postulates, but is not likely to meet them exactly; this holds true for
the output of the sub-maximal LFSR.
What criteria do you use that would make the missing bit patterns stand
out? (That's not a challenge -- I'm really interested.)
>> Can you see any possible uses for a sub-maximal LFSR now?
>>
>> If you think about LFSR's in terms of state spaces, you might realize
>> that the two types we're discussing differ only in the number of state
>> spaces. All LFSR's have at least two state spaces; one of these is the
>> space that contains the single state of zero. The maximal-length LFSR
>> has two state spaces: one is that zero state space and the other consists
>> of all the states between 1 and 2^n - 1. The sub-maximal LFSR has more
>> than 2 state spaces. Of the non-degenerative (by this I mean an LFSR
>> that returns to its original state -- those that have an odd number of
>> taps or that do not include the output bit in the tap sequence will not
>> do so) sub-maximal LFSR's I've had time to investigate, every one has an
>> even number of state spaces; at least one of those spaces' size was equal
>> to a power of 2 minus 1.
>
>The parenthetical remark is confusing. An even number of taps implies that
>there are two degenerate states corresponding to all zeros and all ones. But
>the rest of the states may form a maximal length cycle, which yields an odd
>number of cycles.
>
I've found that an odd number of taps leads to an output sequence that
loops through a portion of the sequence, rather than the entire sequence.
Ex.: a 5-bit register with taps 5,3,1 and an init vector of 1. The
state sequence looks like: 1, 16, 24, 12, 22, 11, 21, 26, 29, 30, 15, 7,
3, 17 8, 4, 18, 25 , 12, 22, 11, ... The first four states are left out
of the loop.
>Also, not including the output bit in the tap list means that you have a
>smaller register than you thought. Assuming the contrary leads to a
>contradiction. Take a small register, say 10 bits and add a pipeline of 90
>unused bitcells to the output yielding a register of length 100. Clearly the
>"exhaust pipe" has no effect on the state of the register. The effective
>length is still 10 bits. The output bit is *defined* to be the last downstream
>bit that is part of the feedback.
>
I see your point. My statement came from having a different definition
of the MSB of the register, the direction of shifting, and the definition
of the tap sequence. If someone defines the MSB of the register to be on
the left, the shift direction to the right, and the tap sequence 5,3 to
mean the MSB and the middle bit, then any register state less than 3
leads to the all-zero state rather quickly. (This isn't meant to weasel
away from your argument. I ran across this in a company who defined
their shift registers this way; we had to adapt the standard nomenclature
for tap sequences (n, A, B, C) to fit their definition.)
>> 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.
>
>Think about LFSRs with inverters in the feedback. You'll find that only the
>parity of the inverter count matters. You'll also find that the degenerate
>cases are those with alternating bits 0xAAA... and 0x555.... That change
>eliminates the bias of more ones than zeros that afflicts a normal,
>non-inverted LFSR.
>
Ow, I can do sparse feedbacks on a normal LFSR in my head. This
inversion thing is going to take some practice.
The parity thing makes sense. Inverting pairs of taps (and by extension
an even number of taps) would make no difference because you wouldn't be
changing the parity of the argument to the feedback function. Inverting
an odd number of taps on a maximal length LFSR does eliminate the +1 bias
seen on the normal LFSR, but it simply replaces it with a +0 bias because
the zero state would be allowable whereas the FFF... state would not.
What did you mean by the alternating bits? Were you describing the
register state? The tap sequence?
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Storing an Integer on a stream
Date: Sat, 21 Oct 2000 23:55:31 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> If I'm writing a file, whose format is a 64 bit file length, followed
by
> some amount of data, followed by some [random] padding, which of the
> following is the best way to store that length value:
>
> 1) 8 base-256 digits. With this format, we always use 8 bytes.
> 2) Some number of base-255 digits, with leading 0 digits stripped,
> terminated by the value 255. With this format, we always use at least
1
> byte (for a value of 0, which is written as just the terminator
(255)),
> but generally use 2..9 bytes.
> 3) Some number of base-128 digits, with leading 0 digits stripped, all
> but the last prefixed by a 0 bit, and the last prefixed by a 1 bit.
> With this format, values 0..127 use 1 byte, 128..(128**2-1) uses 2
> bytes, etc, with 9 bytes being used for a 63 bit value, and 10 bytes
> used for a 64 bit value.
>
> Since this file will be encrypted, any file lengths that are
> significantly less than 2**64, which is most files, will give some
known
> plaintext of leading 0s with method 1. I made a suggestion of using
> method 3, to avoid this problem, but someone (I forget who) said that
> method 2 was more space efficient. Does anyone have any comments?
Both
> on space-efficiency and on difficulty of using it for trial
decryptions.
>
> By the way, I think I should mention that in the perl programming
> language, the builtin functions pack() and unpack() have a template
type
> for method 2, which (If I recall correctly) uses the letter 'w' and is
> refered to as Berweiss-encoding of an integer.
>
> --
> ... perfection has been reached not when there is nothing left to
> add, but when there is nothing left to take away. (from RFC 1925)
>
base 10 in BCD and use any non-decimal digit to end
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Storing an Integer on a stream
Date: Sun, 22 Oct 2000 00:17:06 GMT
Now this one seems absurdly obvious to me.
If, let's say, the max padding you use is 65535 bytes, you only need to
put the last 16 bits of the data length in the header. If it is, say,
65536 bytes, you need to put in the last 17 bits of the data length.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Jonathan" <[EMAIL PROTECTED]>
Subject: Re: BIOS password, will it protect PC with PGPDisk against tampering ?
Date: Sun, 22 Oct 2000 11:01:59 +1000
The WHOLE DISK (registry, system files, swapfile etc can be done). I have
tried a beta of SAFEBOOT and was very pleased. The passphrase screen kicks
in just after booting and before windoze starts to load. (supports multiboot
systems/partition encrypt as well). Controlbreak claim 1% reduction in speed
using RC5 1024 bit OTFE. I absolutely agree with this. NTFSDOS saw nothing
but spaghetti. Essentially the whole thing can run on software although
smartcards etc. are supported. The recovery system is flawless. (P.S. This
is not spam. I was just so impressed with the trial run I gave it). P.S.
SAFEGUARD apparently supports Blowfish, IDEA, 3DES and has a EAL3 rating,
however, no demos are available (as far as I know). J.
"pgp651" <Use-Author-Address-Header@[127.1]> wrote in message
news:[EMAIL PROTECTED]...
> -----BEGIN PGP SIGNED MESSAGE-----
>
> Will these drives run the installed Win95 on them ?
> Because all will be encrypted, how this will compare in speed with Win95
on not
> encrypted drive ?
> Should user expect serious degradation in speed ?
> Has this solution admin super key ?
> Is the software source code available or is this hardware solution ?
>
> On Fri, 20 Oct 2000, "Jonathan" <[EMAIL PROTECTED]> wrote:
> >How about strong encrypt the whole system drive with something like
safeboot
> >www.controlbreak.nl or safeguard http://www.utimaco.com . With these
> >utilities you can't get acces to the drive period. (even if you try
ntfsdos
> >or bios tricks.)
> >
>
> ~~~
> This PGP signature only certifies the sender and date of the message.
> It implies no approval from the administrators of nym.alias.net.
> Date: Sat Oct 21 22:25:20 2000 GMT
> From: [EMAIL PROTECTED]
>
> -----BEGIN PGP SIGNATURE-----
> Version: 2.6.2
>
> iQEVAwUBOfIX0U5NDhYLYPHNAQH4ngf/VJDq4T3/gIPCvzCJSfFaTjatv2B3dH0d
> QTYyCkK44r4QzAjLHAyiiZDUGBxocAAV4QlOBZbMNU2nwtyropqmfMaRA1RmXJkH
> FS4B3QpRQn6mr8NGlH8AMCmV+9hBYt7TRq4VZDKs/KNC1TvXcqD4n20nts1XQJ+P
> JxMR2/ptvD45wX2uL8nA5xVTdPiqybBc7nAUDMTU/thfkz9rjXzKomj1QmaLd4ch
> gYnMo+8Yj0lSoIE5R1ZWk7g931ZlyqmjDeGzi5KHkPRU6Kjvs84xNE6mBPGqDRYd
> FK15MFC10+89+fHUk14mH2uy7j9zOwq0ELnYIOvMXvNPi9O9hAOrdw==
> =erxm
> -----END PGP SIGNATURE-----
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Hypercube structure / balanced block mixing
Date: Sun, 22 Oct 2000 01:09:41 GMT
Benjamin Goldberg wrote:
>
> The structure of edges in a hypercube, and the structure of mixing
> pairs used in balanced block mixing are identical. I wanted to create
> a cipher which used a hypercube like structure, when I noticed the
> similarity, and then decided to look up ciphers which used balanced
> block mixing. The one I found, TC2, uses a global static array to
> specify pairs of indices. Does anyone know how to use ordinary loops
> (no global data) to list the edges of an arbitrary sized hypercube?
> I've tried myself (using 3 nested loops) but I can't seem to get it
> right. I suspect it will require 4 nested loops, but I'm not sure
> how.
>
> It might be only doable with a recusive function; I hope not.
After posting this, I did discover a recursive function for printing out
the edges of a hypercube, and suspect that this (or a stack) is the only
way of getting a hypercube functionally (without a lookup table).
void hypercube(int start, int order) {
if( order <= 0 )
return;
else {
int i, half = 1 << --order;
hypercube( start, order );
hypercube( start+half, order );
for( i = 0; i < half; ++i )
printf("%d, %d\n", start+i, start+i+half);
}
}
This function, annoyingly, prints the edges in a depth first order.
Anyone know an easy way to turn such a thing into a breadth first
listing?
> The reason for my asking is that my expanded key is 512 bytes, and I
> want to use an order-10 hypercube to do balanced block mixing in the
> key schedule, and I *don't* want to have a global array containing
> 10*512 integer values.
>
> --
> "Mulder, do you remember when I was missing -- that time that you
> *still* insist I was being held aboard a UFO?"
> "How could I forget?"
> "Well, I'm beginning to wonder if maybe I wouldn't have been
> better off staying abo-- I mean, wherever it was that I was
> being held." [from an untitled spamfic by [EMAIL PROTECTED]]
--
"Mulder, do you remember when I was missing -- that time that you
*still* insist I was being held aboard a UFO?"
"How could I forget?"
"Well, I'm beginning to wonder if maybe I wouldn't have been
better off staying abo-- I mean, wherever it was that I was
being held." [from an untitled spamfic by [EMAIL PROTECTED]]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: How about the ERIKO-CHAN cipher?
Date: Sun, 22 Oct 2000 01:09:49 GMT
David Wagner wrote:
>
> >Then you take your key, a 20-digit (or longer) integer, take its
> >square root, and starting at the decimal point, you take every digit
> >less than 6 until you have as many digits as are in your message.
> > Then you modulo-6-add this to the digits of your message.
>
> (An aside: Why do I keep seeing this suggestion? What is its
> appeal?)
The appeal is that it is easy to do with pencil and paper, and produces
a stream of values which look random to the human eye. Similarly, LFSRs
are easy to implement with a computer, and produce a stream of values
which look random to the human eye.
> I don't recommend to use square roots. If you reveal every digit
> of the square root, it is very easy to recover the key with a short
> stretch of known keystream by using continued fractions.
If you reveal N sequential bits of an LFSR with an order N polynomial,
key recovery is trivial. I wouldn't recommend using a pure LFSR any
more than I would recommend using a pure sqrt stream.
Regardless, it's not the key that's recovered, it's the "seed" that's
recovered, which was made by combining the key with the initialization
value. Since the IV is in the clear, it's advisable to somehow combine
the two numbers securely.
> What makes you think that just omitting some of the digits is enough
> to patch things up to prevent generalizations of this attack from
> working?
For the same reason that applying self shrinking to your LFSR is enough
to prevent attacks to it.
> How do you know there isn't some crazy lattice attack, for instance?
Aren't lattice attacks for knapsack problems? Knapsack problems are [in
general] breakable/broken [NTRU being a possible exception]. Some
systems using the knapsack problem as a basis were made slightly harder
by making the construction of the lattice more difficult, but the
lattice solution was always applicable, and, with effort, any knapsack
system could be gotten into lattice form.
You are suggesting that the decimated sqrt stream in "Eriko-chan" is no
more difficult to break than a pure sqrt stream. I believe that the
difference between LFSRs and SSLFSRs applies to sqrt and decimated sqrt
streams.
> Have you done any mathematical analysis at all? This stuff is very
> subtle, and you should spend an order of magnitude more time on
> analysis than you do on design.
Entirely true that more analysis should be done than design. I believe
that if a newbie posts a (breakable/broken) cipher, it is better to tell
him that it is breakable, and give a pointer (URL or book reference) to
information that tells him how to break that kind of problem, than it is
to post precisely how the cipher is broken.
For instance, your statement that pure sqrt are bad because there are
correlations, is better than saying "I can break it this way." However,
you should still give references to how correlations on sqrt streams
work, and more importantly, you should *make sure* that it *can* be
broken that way before actually stating it as an inarguable fact.
> This general methodology -- the original scheme is broken, so you add
> a minimal patch until you yourself can't break it, and maybe repeat
> a couple of times if the revisions get broken, too -- well, it strikes
> me as a pretty risky way to design ciphers. It's a mindset, but IMHO
> it's important.
True, but... the problem with "repeat ... if the revisions get broken"
is that when someone else broke them, and you generally don't learn
much, if anything from the break, except maybe how to fix *that one
break*. That's the true part.
Here's the but... If you are told that it is broken by attacks of the
type described in xyzzy, then you can't try to patch the break until you
read xyzzy, and see the break yourself. This promotes learning. It
also means that, in the process of learning how *a* break works, you
learn how other breaks work (and thus hopefully how to defend against
them). Once you've defended against attack A, you may also see attacks
B and C, which you learned about reading the document, and which you can
attempt to defend against without having to ask the NG for another
review of the modified cipher.
The mindset in the 'but' is almost identical, except that you aren't
told the break, you're told how to learn how to do the break. I suppose
it's like in elementary school, where the teacher says to not call out
the answer as soon as you've got it, but wait until everyone else [or at
least, most of everyone else] has figured it out, too. Giving a break
to a newbie's cipher is like calling out. Saying you've got a break is
like raising your hand. If the college grad walks into the kindergarten
room, and tells everyone the answers to the questions, noone will learn.
The same applies to crypto. Tell newbies where to learn, and they will;
tell them the answers, and they won't learn.
--
"Mulder, do you remember when I was missing -- that time that you
*still* insist I was being held aboard a UFO?"
"How could I forget?"
"Well, I'm beginning to wonder if maybe I wouldn't have been
better off staying abo-- I mean, wherever it was that I was
being held." [from an untitled spamfic by [EMAIL PROTECTED]]
------------------------------
** 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
******************************
