Cryptography-Digest Digest #482, Volume #12 Fri, 18 Aug 00 22:13:00 EDT
Contents:
Re: 215 Hz five-qubit quantum processor (Maynard Handley)
How strong is this algorithm? (Jeff Davies)
Re: 215 Hz five-qubit quantum processor (Bill Unruh)
Re: How many bits of strength does the ZIP encryption have? (Bill Unruh)
Re: How many bits of strength does the ZIP encryption have? ([EMAIL PROTECTED])
Re: 1-time pad is not secure... (Tim Tyler)
Re: Intermittent stream cipher? ("Scott Fluhrer")
Re: Java Random Numbers ("Scott Fluhrer")
Re: Cryptography and Content Protection ("Scott Fluhrer")
Re: OTP using BBS generator? (Tim Tyler)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Maynard Handley)
Crossposted-To: comp.arch
Subject: Re: 215 Hz five-qubit quantum processor
Date: Fri, 18 Aug 2000 16:24:09 -0700
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
>Because of Godel's proof, of course, some theorems don't have proofs
>within a given formal system, and yet can be seen to be true through
>metamathematics or through enlarging the formal system. So even a
>quantum computer that proves mathematical theorems wouldn't abolish
>creativity in mathematics.
Hmm. I don't think that's really the issue with Godel. No-one ever doubted
that there's a creativity involved in coming up with "interesting" formal
systems.
I would contend that what's interesting about Godel is more that certain
things ARE true, but can't be PROVED true. The standard example is always,
of course, Goldbach's conjecture, "Every even number greater than two can
be written as the sume of two primes". Our natural feeling is that either
this is false, ie there is some (large) even number that can't be
expressed this way, or that it is true "for a reason", that we can prove
it. But maybe it just is what it is---true, but not provable.
Maynard
------------------------------
From: Jeff Davies <[EMAIL PROTECTED]>
Subject: How strong is this algorithm?
Date: Sat, 19 Aug 2000 00:47:16 +0100
I have an idea for a non-profit electronic cash system (a bank)
for which I have devised I think a new algorithm.
Can anyone tell me how to evaluate how strong this is??
Full details of business plan and crypto method below:
Jeff Davies
[EMAIL PROTECTED]
ELECTROCASH PROPOSAL 0.02
=========================
Revisions:
0.01 to 0.02:
18.8.2000 SJD
- Mission statement added,
- progress to date added,
- encryption notes modified.
- RMS idea to use Government bonds to finance added.
Mission:
"To provide an electronic cash system that is instantaneous, based on
totally free
standards, very secure, and self financing".
Progress to date:
=================
www.electrocash.org already purchased (by S.J. Davies).
Yep, that's right, it's going to be a non-profit making organisation.
In the UK, S.J. Davies is setting up a Registered Charity to be the
legal
corporate presence of Electrocash in the UK.
1. Charity Commission, (+44) 0870-333-0123
Phoned 18.8.2000 for forms.
"Will be sent out today to SY24 5BZ".
2. Companies House UK, Cardiff (+44) 029-2038-8588.
Phoned 18.8.2000 for starter pack for company limited by guarantee.
"Will be sent out today to SY24 5BZ" - SJ Davies postcode".
Also, name is available.
To Do:
======
1. Identify a means of distributing the keys. Perhaps this is floppy
disks for
older computers, Compact Flash or SMART cards or Memory Sticks for other
devices.
2. Identify people to be trustees of UK charity arm of electrocash -
perhaps Richard
Branson?
3. Finish implementing a test system. Java Client is currently in
progress.
4. Look at survival rates for UDP packets across the internet.
Description:
============
In the bank, there are never any charges.
This is because income is derived totally from investment of a
proportion of the
credited funds in government bonds.
There is no credit since all money is transferred instantly between
accounts.
There might be a BACS gateway (British Automated Clearing System) to the
system to allow people to transfer
to/from people who do not have accounts at Electrocash.
This idea is public licence:
Technology
================
All technology is non-proprietary, and any Electrocash technology is
Public Licenced to:
1. prevent another standard usurping Electrocash technology
2. prevent another company patenting Electrocash technology and
enforcing the patent by
superior legal resources.
Implementation
=====================
1. All transactions are processed instantaneously (1 second max).
You cannot spend money you haven't got.
No bank letters, no charges.
2. The servers
.. run Linux or FreeBSD perhaps clustered, perhaps Beowulf cluster.
Perhaps Bastille Linux.
Core parts (IO) are very controlled and the code audited.
All daemons like telnet, ftp, inetd super server are disabled.
Routing disabled in
kernel. Only the transaction port is active. (You can't even ping).
Perhaps long
term, the Ether driver is restricted to this port only as well.
Customer Account balances are held in RAM. (100 million customer's
balances as
a fixed point 32 bit uint value would take 400 megabytes in a world
where 2 gig
of RAM is pretty commonplace on big servers).
A single 100 megabit link could carry (based on 100% utilisation
which might be achievable
if there is only an incoming router and a single system on a segment
- ie no collisions),
6000 transactions per second (based on single 1500 byte udp packet
per transaction).
If 10 million people make 200 transactions per day based around a
core 10 hours of the day,
this is two billion transactions per day, and represents three
million megabytes of data
per day (note the active part or each packet is very very small).
The ten hour day is 360,000 seconds, and so, there are about 5500
transactions per second.
i.e. a single 100 megabit link can carry the transactions of 10
million people.
Obviously there are many factors which might lower this, but with
parallel systems,
and faster than 100 megabit (fibre etc), one can imagine that it will
not be difficult
to grow such simple technology.
3. "Java Clients"
The clients are Java based, open a socket and send an encrypted
message consisting of
SOURCE_ACCOUNT, DESTINATION_ACCOUNT, CASH_AMOUNT. Note heavy
checksums ensure
correct accounts are specified.
4. The encryption technology is as follows:
Note I have called this proposal "256 bit" however, I think it is
stronger than traditional
256 bit methods. Instead of changing a pattern of bits larger than a
character into an
equivalent, random values scramble the message bits into a random
packet 128 times larger.
Electrocash will use Symmetric keys. Traditionally, asymmetric keys
are used to prevent possibility of
compromisation of the person's key from the server, where a third
party could pretend to
be the person. However, Clients are at the time of writing, far more
vulnerable than
the server. As a result, the private key is probably more likely to
be lost than public key.
So, as asymmetric are less strong per bit (2300 bit asymmetric is
equivalent
to about 256 bit symmetric in strength), multiple symmetric keys
will be used with
Electrocash.
The key works as follows: for each bit in the packet (encrypted
packet length is 256 bits)
there is a 16 bit word specifying it's position in a larger word
where unmapped bits have
random values. At the outset, the upper two bits of the 16 bit word
will not be used,
as a single udp packet of around (max) 1500 bytes is standard on
networks sent.
Naturally, therefore, the encrypted bit position can be one of 4096
(from it's original
position within 256 bits).
Each key has 256 off 16 bit words (totalling 512 bytes) positioning
the encrypted bits
within the larger packet. The values in the key are originally
generated by Electrocash
Server using a psuedo-random binary sequence generator (cannot
repeat within 256 values).
The unencrypted part of the packet gives a 16 bit integer choosing
the key from
the 2048 supplied every month in a 1 megabyte smartcard (or
similar).
Each key is used for only one transaction (this might be modified if
it proves unworkable).
Per user, 2048 keys are created per month, and distributed by
snailmail on a smartcard or similar.
There is no certification mechanism, as this can be bruteforced. you
can't rely on client's being secure.
The encryption algorithm is created outside the US, so that it is
not subject to US export restrictions.
As no data is stored in encrypted form, this should comply with UK
"Rights of the People Bill".
When Client talks to server, first unencrypted message specifies
account number and encryption key to use
from the 2048 sent. There is never a need for personal accounts for
the same encryption key
to be used twice. So when a key is used, it is discarded.
This makes bruteforcing impossible. The client used might be
compromised. In the case of a compromised client
money lost is at the account holder's own risk.
Ultimately, mobile phones are the target market, using JINI,
Javasoft's embedded java product.
As RMS suggested that the level of encryption might be a bit a bit
excessive, if this
is a new idea, I'd like to call it "Jeff's Hammer". If it isn't new,
i'd like to use
the name for the implementation.
5. "Micropayments"
for online services in future years will be effected through a
download a buffer of ecash to
a micropayments centre where the micropayments occur. Micropayments
will not go directly to Electrocash.
6. "Reviewing previous transactions":
Interfaces with the same ip address as the system that holds the
current account
balances will be present on other machines connected to the same
segment.
(Note the router routing in new transactions is the only device to
"talk" on the
segment, all others listen).
These other machines simply record each transaction against both
accounts in a
binary file for each account.
(Note the transaction is about 256 bits unencrypted - 4 bytes.).
This means if a million account holders had 20000 transactions on
file, (say 2 years)
then this would take 80 billion bytes or 80 gig of disk space.
Currently in
terms of ordinary PC IDE hard disks, this represents around �500
(about $700 or 700 euros).
Backups could be effected by mirror across a VPN across the world.
Regular auditing and checksums ensure data integrity.
Jeff Davies
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Crossposted-To: comp.arch
Subject: Re: 215 Hz five-qubit quantum processor
Date: 18 Aug 2000 23:37:45 GMT
In <8njj0f$p3q$[EMAIL PROTECTED]> "Dennis O'Connor" <[EMAIL PROTECTED]>
writes:
]"Bill Unruh" <[EMAIL PROTECTED]> wrote ...
]> In <8nctf9$5tf$[EMAIL PROTECTED]> [EMAIL PROTECTED] (Paul Rubin)
]writes:
]> ]The class of problems a quantum computer can probablistically solve in
]> ]P-time is called QBP. It's believed to be larger than P but it still
]> ]is no larger than NP. Factoring and other search-type problems sit
]> ]inside QBP, but sorry, the classical halting problem is still undecidable.
]>
]> No, search is still non-polynomial. Grovers speedup was to sqrt(N) which
]> is still very non-polynoimial in the length of N.
]Hmm, I don't know what you mean by "Non-polynomial".
]I will not presume you don't know this, Bill, but for
My comment was shorthand. As far as is known a database search is of
order N where N are the number of elements in the database. Since such a
database is often the totality of the outputs of an algorithm whose
input is ln(N) long, the search takes exponential time in the length of
that input. The Grover algorithm shows that on a quantum computer you
can do this in sqrt(N)= exp(ln(N)/2) steps, which is still exponential
in the input length. Ie, the Grover algorithm improves on exhaustive
search, but not by much. It is not a general way for a QC to solve all
exhaustive search problems in polynomial time. Since the suspicion is
that problems which are in NP but not P will take something like
exponential steps in the length of the input, this was why I said that
the Grover Algorithm does not realy do anything as far as the solution
classes of problems is concerned. Ie, I was refering specifically to
your statememt that "search problems sit inside QBP. I would not
consider them to do so.
]the benefit of those who don't understand the terminology,
]"NP" stands for "Non-deterministic Polynomial (time)",
]and refers to the set of algorithms that can be solved in
]polynomial time or less by a non-deterministic Turing
]machine. A non-deterministic Turing machine can sort
]of be described as a Turing machine that "goes both ways
]at all branches" until it finds an answer. Another equivalent
]of a non-determinist Turing machine is a large (potentially
]infinite) set of deterministic Turing machines, one for each
]possible answer, that take all the possible answers and,
]working in parallel, check which one is true. This latter
]is due to the property of NP that says "If finding the
]solution to a problem is NP (take polynomial-bounded
]time on a non-deterministic Turing machine), then checking
]whether a particular value is a solution to a problem is P
](takes polynomial time on a deterministic Turing machine),
]and vice versa.
]A quantum computer operates by starting with a wave
]function that includes all possible solutions to a problem,
]and then "collapsing" that wave function to a correct
]solution. This makes it akin to a non-deterministic
]Turing machine.
]A Turing machine, BTW, is particular kind of computer
]used in theoretical studies of algorithms. All computers
]generally in use are equivalent in capability to a
]deterministic finite-memory Turing machine. Quantum
]computers would be equivalent I believe to a
]non-deterministic finite-memory Turin machine.
]This was a bit rushed, so I hope if I've blundered anywhere
]someone will point it out.
]--
]Dennis O'Connor [EMAIL PROTECTED]
]Vanity Web Page: http://www.primenet.com/~dmoc/
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: How many bits of strength does the ZIP encryption have?
Date: 18 Aug 2000 23:41:21 GMT
In <[EMAIL PROTECTED]> Christian Ghisler
<chris@ghisler=remove.com> writes:
>Dear crypto experts!
>What strength (in bits) does the ZIP encryption have, compared e.g.
>with DES (56 bit) or IDEA (128 bit)? ZIP encryption uses three 32 bit
>keys, so the strengh is probably somewhere between 32 and 96 bit. I'm
>not talking about known plain text attacks here, just cryptographic
>strength with no known plaintext.
>From what I have read here, I suspect the answer is something like 20
bits. Zip encryption is apparently very easily broken. Do NOT use it for
anything of any value.
(I assume I will be corrected if my memory has failed me.)
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: How many bits of strength does the ZIP encryption have?
Date: Sat, 19 Aug 2000 00:17:57 GMT
In article <8nkhj1$oq4$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Bill Unruh) wrote:
> In <[EMAIL PROTECTED]> Christian Ghisler
<chris@ghisler=remove.com> writes:
>
> >Dear crypto experts!
>
> >What strength (in bits) does the ZIP encryption have, compared e.g.
> >with DES (56 bit) or IDEA (128 bit)? ZIP encryption uses three 32 bit
> >keys, so the strengh is probably somewhere between 32 and 96 bit. I'm
> >not talking about known plain text attacks here, just cryptographic
> >strength with no known plaintext.
>
> From what I have read here, I suspect the answer is something like 20
> bits. Zip encryption is apparently very easily broken. Do NOT use it
for
> anything of any value.
> (I assume I will be corrected if my memory has failed me.)
You need 13 bytes of plaintext/ciphertxt and about an hour.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Reply-To: [EMAIL PROTECTED]
Date: Sat, 19 Aug 2000 01:01:04 GMT
Darren New <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> If following a MWI, there are many "me"s and many "post"s. All have
:> equal rights and status. By saying "this" post, you haven't uniquely
:> identified anything, since there are many posts which are all claiming
:> to be "this" post.
: To be less silly (and to add something that should have been in the previous
: post), if there's nothing random about MWI, what determines which
: conciousness sees which pattern of random bits? Since the parallel worlds
: cannot interact with each other once "collapsed", making a 2-bit random pad
: gives you four worlds which do not communicate. Which one are "you" on, when
: you look at the pad? Saying "all of them" doesn't help, because then you've
: not only eliminated "random", you've eliminated "unpredictable", and since
: everything now is predictable, you have eliminated "secret". Since there is
: *always* a world in which you will try the correct key on the first try, how
: do you do cryptography if you look at the world that way?
I don't really understand what the issue you're trying to raise is.
The MWI is probably best seen as avoiding wave functions "collapsing".
In it, wave functions remain eternally super-imposed and never collapse.
Whatever you're trying to get at, I'm pretty sure this isn't the right
venue to discuss it.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Intermittent stream cipher?
Date: Fri, 18 Aug 2000 18:16:30 -0700
Darren New <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> > I would like to know where I might find a cipher algorithm that allows
me to
> > stream plaintext input on an intermittent basis. The application is
logging
> > messages to a file which must be encrypted. The file has to remain
> > encrypted at all times.
>
> Why not just use something like RC4. To add a line, run the generator thru
> as many bytes as you already have in the file, and then pick up the stream
> from there? If your log file is 3000 bytes long now, run RC4 for 3000
bytes
> (or 3000+256, or whatever) and then start using the output to xor with the
> new message?
That has the problem that, if the log file gets large, you end up running
RC4 a lot to get to the right state. If your log file is one megabyte, you
generate one megabyte of RC4 output to append a single line. What would
make more sense is to take a block cipher and run it in counter mode. That
is, divide the file up into N byte chunks (where N is the block size: 8 for
blowfish and 16 for twofish), and for each chunk, take the offset of that,
encrypt it, and xor the resulting ciphertext into your data to form the
value to store. To store an additional line, all you need to do is generate
the ciphertext that corresponds to the blocks the new line takes up.
--
poncho
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Java Random Numbers
Date: Fri, 18 Aug 2000 18:20:01 -0700
Daniel Leonard <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
On Fri, 18 Aug 2000, Scott Fluhrer wrote:
>>
>> <[EMAIL PROTECTED]> wrote in message
news:8nje9h$pis$[EMAIL PROTECTED]...
>> > Java implementation of Random Number Generator.
>> Is this supposed to be another implementation of the exact same random
>> number generator you published earlier? If so, have you run test vectors
to
>> verify that it is the same generator? It looks like it has a few bugs.
In
>> particular, I believe that char's in Java are always 8 bits, and so
anytime
>> you try to store something in the "upper 8 bits", it gets lost.
>
>In java, primitive data type are well defined (as opposed to C - see the
>blowfish thread).
>
>byte -> 8 bit
>char -> 16 bit
>short -> 16 bit
>int -> 32 bit
>long -> 64 bit
>
>they are and will always be those sizes
Sorry about that. Maybe I should have learned more about Java before
commenting...
--
poncho
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Cryptography and Content Protection
Date: Fri, 18 Aug 2000 18:29:35 -0700
Adriano Prado <[EMAIL PROTECTED]> wrote in message
news:8njsbt$b7n$[EMAIL PROTECTED]...
> Ok, let me be clearer...
>
> What is my 'system':
>
> Alice is a point-of-sale printer (the one used in supermarket).
> Bob is a computer.
>
> What I need:
> The printer respond to a set of defined commands.
> This commands are sent by the computer via a RS-232 serial port.
>
> There are some of these commands that are restrict, the computer has
> to send a key that is unique to each printer so it can be accepted.
> That is, the same computer communicates with more than one printer,
> but for each one it has to send a specific key.
>
> So, if one wants to use such set of commands, he has to call me,
> send the serial number of the machine, and then I compute the key.
> I pass the key by fax or e-mail. He then enter with the key in the
> communication program who will send (the key) to the printer.
> The printer should be able to see if the key is right for its serial
> number.
If that's the case, who's the attacker? What is he trying to do? If you
can basicly trust everything (the computer, the serial line), then it's all
straightforward -- no real crypto necessary. However, until you have a
solid attack model, I can't state that definitively.
--
poncho
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Reply-To: [EMAIL PROTECTED]
Date: Sat, 19 Aug 2000 01:40:26 GMT
Bryan Olson <[EMAIL PROTECTED]> wrote:
: Terry Ritter wrote:
:> Bryan Olson wrote:
:>Then you should not have disagreed with Tim Tyler's point [...]
: First, I have no idea what "Tim Tyler's point" [...] was.
Backtracking, Bryan almost certainly refers to:
TT> AFAICS, BBS was never suppsed to be "absolutely secure" in the
TT> first place. Saying a problem is as hard as factoring does not
TT> provide any sort of "absolute security".
TR> The assumption is made that factoring is hard, so in that situation,
TR> BB&S should be "proven absolutely secure." [...]
If "proven absolutely secure" has any meaning at all for a pseudo
random number generator, I would hope that it means that no algorithm
works better than a brute force key search through all possible seeds.
As I understand it, we know that attempts to factor the modulus are
a better attack on BBS than brute force seed search - so the system
already falls short of what is possible in terms of security.
Besides, you can hardly rest an "absolute" proof on something unproven,
such as the difficulty of factoring. Factoring is /believed/ to be hard -
but there's no absolute proof. Indeed, the quantum computation
cheerleaders would have us believe that factoring may soon prove to be
much, much easier than people had previously thought.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
** 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
******************************
