Cryptography-Digest Digest #206, Volume #13 Wed, 22 Nov 00 09:13:00 EST
Contents:
Re: A poorman's cipher (Mok-Kong Shen)
Re: Entropy paradox (Tom St Denis)
Re: Entropy paradox (Tom St Denis)
Re: Pseudo random sequence generation for xor encryption (OTP) (Tom St Denis)
New Dynamic Algo + Contest + Doc (Sylvain Martinez)
Re: ---- Internet Voting Questions ([EMAIL PROTECTED])
Re: vote buying... (Jeffrey Williams)
Re: New Dynamic Algo + Contest + Doc (Paul Crowley)
Re: Randomness from key presses and other user interaction (Alfons Adriaensen)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: A poorman's cipher
Date: Wed, 22 Nov 2000 13:33:46 +0100
Michael Scott wrote:
>
> "Mok-Kong Shen" <[EMAIL PROTECTED]> wrote:
> >
> > Addendum (III)
> >
> > Globally, it may be observed that, while the common block
> > ciphers work vertically in the sense of first attempting
> > to achieve as much diffusion as possible within a small
> > number of bits inside a block and then attempting to
> > achieve diffusion throughout the message via block chaining,
> >......
>
> That's why Rijdael/Square is such a nice idea. By arranging the state as a
> block of 4x4 bytes much tighter coupling is acheived between the individual
> elements and hence much quicker diffusion. I wonder has anyone extrapolated
> the idea to "CUBE", or perhaps a tesseract?
As explained, our scheme follows a different principle
('philosophy') than what is done with block ciphers. In fact,
one can either view a message as being treated as a single
block or view the message as being processed with stream
techniques (in both cases with a variable number of passes
or rounds).
M. K. Shen
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Entropy paradox
Date: Wed, 22 Nov 2000 12:30:05 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Tom St Denis wrote:
> >
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > >
> > > This is a re-formulation of an issue that I questioned
> > > previously. Suppose one has m perfectly random bits and
> > > uses that in some appropriate way to get a BBS generator
> > > to generate u bits, with u >> m. We know that (accepting
> > > certain plausible assumptions) the u bits are provably
> > > secure. It seems thus that we have obtained more entropy
> > > that way, i.e. having obtained an amount of additional
> > > entropy from nothing. How is this apparent paradox to be
> > > properly explained? (Or does each bit of the generated
> > > sequence have in average m/u bits of entropy?) Thanks in
> > > advance.
> >
> > Hmm there can't be any more entropy then that contained in the
factors
> > of the BBS modulus. The outputted bits may appear random but are no
> > more random then the size of the modulus. Look at RC4 for
example. It
> > may be able to output 2^30 bits, but in reality there are only 2^k
bits
> > required to distinguish the output from random (k << 2^30).
>
> So if BBS generates u bits and I take m bits out of it,
> how much entropy is in there? Thanks.
There is no more entropy then in the moduli and original starting point
of the BBS generator. The new bits made are NOT RANDOM they just
appear that way. Thus, entropy is not increasing.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Entropy paradox
Date: Wed, 22 Nov 2000 12:31:55 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> I suppose that BBS and its assumptions and proof are known.
> I assume that you do the best so that all the entropy in
> the given m bits are incorporated into the generator. In
> other words, BBS is viewed as a black box with m bits as
> input and u bits as output. Is this concept clear? Or do
> you contend the correctness of the assumptions and/or
> the proof of BBS? Thanks.
The output of BBS is not random though. So no new entropy is created.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Pseudo random sequence generation for xor encryption (OTP)
Date: Wed, 22 Nov 2000 12:35:10 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Ivan Skytte J�rgensen wrote:
> >
> > What is the best way of producing a pseudo random sequence for use
with
> > xor encryption?
>
> Standard texts on crypto have materials on PRNGs. I have
> a scheme of building a compound PRNG consisting of an
> arbitrary number of constituent PRNGs (of arbitrary type)
> on my web page. PRNGs are deterministic and hence 'in
> principle' always crackable, though I haven't yet seen
> a feasible way of cracking my compound PRNG 'in practice'.
What Knuth calls Algorithm.M is a good way to take too long perioded
PRNGs and turn them into one long perioded non-linear PRNG. You can
take too parallel LFSRs (i.e using word-wise xor and such) or two LFGs
and make a stream cipher.
The big problem is how to key the suckers. I generally would use a
hash and rehash or something like that...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Sylvain Martinez <[EMAIL PROTECTED]>
Subject: New Dynamic Algo + Contest + Doc
Date: Wed, 22 Nov 2000 12:52:20 GMT
NOTE: I've posted this message yesterday but with the wrong title,
sorry!
Hi sci.crypt !
BUGS is a relatively new private key algorithm. It does not claim to be
the best algorithm in the world, because as any "home-made" cryptography
algorithm it can't be. It is just the result of a strong interests I've
got in cryptography.
Nevertheless, it is not that bad...
Before you skip or *clonk* this thread please let me explain why I think
this BUGS algorithm could be interesting and why I am doing it for.
And why there is a new version 4.0.0 !
- I think BUGS is interesting because it is different from the current
cryptography algorithms available (not that they are bad ;o), it is a
DYNAMIC algorithm. This means that the algorithm will behave differently
in function of the password/key used to crypt a file. I know other
algorithms could also be defined as "dynamic" but I think this one is
the one of the most "Dynamic" out there.
- I am interested in cryptography, I am not an expert, I am not even an
"amateur". I like the "Unix spirit" and I just wanted to create
something opensource/multiplatform. I like challenges, I know
that before you create your own algorithm you need to at least read many
books and try to crack some algorithms first. I've just read books
(nearly forgot to put an 's' at the end ;o).
In order to interests as most people as possible I did not just create
an algorithm on its own. I've created many applications arround on Unix
and Windows and a long documentation. I have even started 2 contests
(�100 to win) just to see how far this BUGS algorithm can go.
If you are still interested here comes the technical bit.
(I would have went straight to the point if I didn't know how careful
you have to be before posting something on sci.crypt ...
and I'm sure it won't be enough ;o)
-- BUGS v4.0.0 --
http://www.bcrypt.com
Platform: Unix, Windows (tested on solaris,linux,true64,bsd,hpux,cgi)
Dynamic private key algorithm.
I will first describe how the algorithm works in a nutshell and then
give a full description of the key generation process
A) In a nutshell
-To crypt a file you enter a password that will be converted into a
key. This key is generated from the password by a series of bits swap
and bits operations (AND,NOR,OR, etc) and then a random
number is generated (using ISAAC algorithm or "bad" standard C rand())
The bits swap+operations will change in function of the password itself.
-The key will then be reused to generate other similar keys, in order
to get a buffer of keys (default = 16 keys).
-2 keys from the key buffer will be mixed together anf the result
KEY_TEMP will be used as a password to generate a new key: KEYX which
will be XORed to one block of the file (the size of this block is the
same as the key's length)
The sequence in which the blocks are XORed is function of the password.
-The key which has just been used, KEYX, will replace one of the 2 keys
used in the buffer in order to "re-populate" the buffer.
-Once all the blocks of the file have been XORed the block shuffle (BS)
can start.
-By default the BS is 4 bytes. The file will be divided into blocks the
size of BS (ie. 4 bytes), then in function of the password 2 blocks will
be picked up pseudo-randomly from the file, mixed together and the
result XORed to another pseudo-randomly chosen block of the file. This
allows the algorithm to crypt the file with its own data.
-You can make all this cryptography process much more complex by
changing few parameters:
In the previous example you were working with all the data of the file
(I mean that you could start to XOR the first block of the file and then
jump to the LAST block) but you can also specify a BLOCK CRYPT, which if
set to 50 bytes for example, will only work within the first 50 bytes of
the file and then with the 50 following bytes, and so on.
The size of the block shuffle (BS) can be changed as well and can be set
to dynamically change at each round in function of the password !
-Dynamic is one of the KEYWORD of this algorithm.
I hope I am not miss-using this word.
But during the key generation the number of round (cycle where the bits
will be swapped) can change dependanding of the password you've entered,
the distance between 2 bits to be swapped will also depand on your
password.
During the XOR process, the size of the Key Buffer can also change in
function of your password.
The algorithm has been carefully tested against bugs and should be
pretty stable now.
It is quite slow. but I believe it is relatively secure, at least secure
enough to protect your data against anybody who hasn't got access to
government's computer ;o)
Many people tried to crack the previous algorithm and sent me reports
about what could be done to make it better, this version is the results
of these comments. One person especially spent a lot of times and energy
analasysing the strength of this algorithm (as I don't really know if he
wants to be named on this forum, I'll call him Simon).
He has also participated into the optimisation of this new algorithm.
The tests done to crack the algorithm were first to find any weaknesses
into the algorithm itself and then a mix between brute
force and "intelligent" reverse ingeneering. I can't really speak about
that because:
a) I'm not one of the guy who done it and I'm not too familiar with it
anyway
b) There are 2 contests still going on and even if the money prize is
not that great some people are still doing it for the
fun/challenge/principle of it.
For more information please go to the WEBSITE:
http://www.bcrypt.com
direct Unix Download: http://www.bcrypt.com/crypto/bugs-4.0.0.tgz
direct Doc Download:
http://www.bcrypt.com/crypto/doc/fullbugs_40.zip
direct Windows download:
http://www.bcrypt.com/crypto/bcrypt4_1.zip
Online Documentation: http://www.bcrypt.com/crypto/doc/index/html
Here is a more detailed explanation about the KEY GENERATION process.
You enter a password, this password will be converted into a KEY as
follow:
1.1) pwd converted into an integer array
1.2) all the numbers of this array will be added together and the
result(sort of checksum) will be added to each integer of the array
This checksum number will change each time it is added as follow:
NB_BITS = how many bits are used by your INTEGER type
SHIFT = this number will be generated from the integer of the array
nb_toadd = (nb_toadd >> SHIFT) | (nb_toadd << (NB_BITS - SHIFT))
1.3)The number of ROUND will change in function of your password (the
maximum value is double the default value) and it will affect the
number of cycle done for this part of the key generation.
During one cycle (ROUND) at least half of the bits of the key will be
swapped. Also at least half of the bits will have had a Logical
operation for example:
bit1, bit2
bit1 = bit1 & bit2
bit2 = bit1 | bit2
The swap and Logical operation are bilateral (the first of the 2 bits
will be once chosen from the "left" and then from the "right", "left",
etc)
To be able to have SWAP between bits distant from a lot of bits and
also from only few bits, 2 modulo swap will be generated and used
alternatively to decide what will be the maximum bits distance betweem
2 bits. There are a SMALL_MODULO_SWAP and a BIG_MODULO_SWAP
by default the SMALL_MOD = your keylength / 2
and the BIG_MOD = your keylength
You can decide or not to dynamically change these modulo in function
of your password at each round. The SMALL_MOD value will still be
between (1 and your_keylength/2) and BIG_MOD
between (1 and your_keylength) but these values will change at each
round.
1.4) A random number will be added to the KEY.
We first generate a random number using ISAAC and then XOR the result
to the key, then use the random number into a LFSR to generate another
pseudo random number, and so on.
This is not a really important step, as it does not really add any
security to BUGS. (according to "Simon" :)
That's it. There is much more information on my website
(http://www.bcrypt.com)
I guess I'm gonna get flamed (at least because this post is far too
long) but I'm just interested into what people who know cryptography
thinks about this little algorithm. I'm not looking for fame or
fight but just feedback.
Hope you'll enjoy it.
Sylvain.
--
---
Unix security administrator
BUGS crypto project: http://www.bcrypt.com
http://www.encryptsolutions.com
--
---
Unix security administrator
BUGS crypto project: http://www.bcrypt.com
http://www.encryptsolutions.com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: ---- Internet Voting Questions
Date: Wed, 22 Nov 2000 13:21:32 GMT
Have a look at
http://australianit.com.au/common/storyPage/0,3811,1009980%255E501,00.html
and also the second half of
http://australianit.com.au/common/storyPage/0,3811,1435580%255E506,00.html
and also
http://election.com/uk/index.htm
On Fri, 17 Nov 2000 22:26:27 GMT, Greggy <[EMAIL PROTECTED]>
wrote:
>
>
>I have been talking with some people here at work about internet voting
>(in light of Florida's voting problems) and I was suggesting some
>solutions that could give greater confidence to the overall integrity
>of the ballot.
>
>One person stated that really the voting process is quite simple and
>could be done over a secured browser. I thought that if he was right
>we should have seen it by now, but he said people are not excited with
>giving their credit card number over the internet either.
>
>So I thought I should ask:
>
>Are there any serious internet based voting proposals that are being
>considered or were considered, especially using a web server and
>browser?
>
>If they have not been considered to be adequate solutions, what where
>the problems?
>
>Does anyone know where I can find some information on the current
>programs underway to implement an internet based voting system anywhere
>in the US?
>
>Any opinions from this NG are very much appreciated...
>
>--
>I prefer my fourth amendment rights over a dope free
>society, even if the latter could actually be achieved.
>
>Al Gore - quite possibly America's greatest threat today
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
------------------------------
From: Jeffrey Williams <[EMAIL PROTECTED]>
Subject: Re: vote buying...
Date: Wed, 22 Nov 2000 07:31:07 -0600
"Tony T. Warnock" wrote:
> Jeffrey Williams wrote:
>
> > Sorry if I wasn't clear. I believe that to be fair, honest, and trustworthy, a
>voter
> > would have to present a national ID card containing a picture of the owner and an
> > indication of the citizenship of the owner (the latter could be implicite if, and
>only
> > if, such cards were issued only to US citizens). The card would presumably be a
> > smartcard which the voting authority could validate with a central database.
>
> Having a National ID Card would at least create opportunities for counterfeiters.
Yes and no. If it were a smartcard, and there were a central database, you could
conceivably set things up so that potential counterfeiters would have to hack the
database
(provided, of course, that the id card was always verified against the central database
before the holder was given any privilege associated with the card).
Realistically, the database would not be on-line. While you might use the internet as
a
pipeline from a card reader to the database, the actions performed based on input from
a
card reader would be extremely limited.
I'm not saying that such a system cannot be defeated; anything man can invent, man can
defeat. But it can be made to be very difficult.
At any rate, it would still be better than the current system which has few, if any,
checks
and balances, and where said checks and balances are applied in a slap-dash manner.
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: New Dynamic Algo + Contest + Doc
Date: Wed, 22 Nov 2000 13:33:44 GMT
Sylvain Martinez wrote:
> BUGS is a relatively new private key algorithm. It does not claim to be
> the best algorithm in the world, because as any "home-made" cryptography
> algorithm it can't be. It is just the result of a strong interests I've
> got in cryptography.
Please read Bruce Schneier's Memo to the Amateur Cipher Designer:
http://www.counterpane.com/crypto-gram-9810.html#cipherdesign
Your claims to security are laughable when there is *no* discussion of
security in the algorithm documentation! Not even a cursory mention of
linear or differential cryptanalysis! At least give reasons why you
believe that your algorithm is resistant to these attacks yourself
before asking anyone else to look at it. Look at weak key and related
key attacks too.
Your web pages describe this algorithm as "reasonably secure", and you
offer a program for download in binary which uses it. In this you do
the world of security a great disservice.
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: [EMAIL PROTECTED] (Alfons Adriaensen)
Subject: Re: Randomness from key presses and other user interaction
Date: 22 Nov 2000 13:36:15 GMT
In article <[EMAIL PROTECTED]> [EMAIL PROTECTED] (Terry Ritter) writes:
>...
>
> Uncompensated quartz oscillators are extremely predictable, at least
> when compared to any real ability of software to measure or detect
> unpredictable variation.
>
>...
>
> In general terms, "jitter" refers to an unexpected time variation with
> respect to a voltage level (an edge or a crossing). In the context of
> crystal oscillators, "jitter" refers to extremely small phase
> variations generally caused by noise (thermal plus other transistor
> noise) in analog to digital conversion. This variation is tiny,
> bipolar around the mean frequency, occurs on a cycle-by-cycle basis,
> and is not additive. Crystal oscillator noise jitter does not change
> the average oscillation frequency.
>
> On the other hand, "drift" refers to a slow, characteristic frequency
> change, generally caused by thermal effects on the physical quartz
> itself. Drift effects are fairly small, but are much larger than
> jitter, and might at least be detected over a long measurement. But
> they are also reproducible with respect to crystal temperature, and
> generally follow a similar path during warm up after power on. This
> is predictable change.
>
>...
All this is true, but you seem to ignore a third phenomenon : phase noise,
which is neither 'jitter' nor 'drift'.
I'm no specialist in this domain, and if you want to know what phase noise
really is, you should talk to someone who designs frequency and time standards,
or oscillators for deep space communication systems.
But the nature of phase noise is such that for any oscillator, even if you
know its complete history up to now, and you have perfect control over
temperature and a very accurate ageing model, you can only predict its phase
for some limited period into the future.
This may seem contradictory, but there is no simple relation between long
term stability and phase noise. For example, frequency standards based on
molecular resonance, such as a Cesium standard, have the best long term
stability you can buy, but typically have very bad phase noise, even worse
than a quartz oscillator.
All this means that you *can* use phase measurements to obtain random bits.
--
Fons Adriaensen
ALCATEL SPACE
------------------------------
** 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
******************************
