Re: Bridge
At 11:44 AM 6/25/99 -0700, bram wrote: There are 52! bridge hands, so a random hand has log2(56!) = 226 bits of entropy or 68 decimal digits worth. No, just 52! / (13!)^4 hands, which is around 2^96. The interesting part is to come up with an algorithm that only uses 96 bits. Take the 96 digits as a really big number base two, find it's value modulo 52! ... (Actually 52!/(4*13!)) Doesn't work, though - for values higher than 52!/13!*4 you need to reject the random number and draw again. Otherwise you've got an excessively high probability of repeating the first 2**96 mod 52!/13!*4 hands. The real point, though, is that you never, *ever* need more than about 80 bits of entropy for *any* amount of random numbers if you use a crypographically strong pseudo random number generator. It depends on the application - for encryption keys, it's probably ok, at least for the next N years, unless the structure of selecting your keyspace interacts with the crypto algorithm in a way that decreases the strength of the resulting encryption. It's unlikely in the general case, but it can happen. But for bridge games, if you don't use at least 52!/13!*4 bits, or more if you're using them wastefully, there are hands that _won't_ happen, and those hands can be predictable in ways that are useful to the players, and therefore bias the results of the bridge game as well as complicatng play. If you know the system will never generate a hand where more than one player has more than 10 cards of one suit, and you're holding 10 clubs, this can be fun, but it's less emotionally satisfying than bidding that slam when you're worried that your opponents have 11 spades because the deck wasn't shuffled right :-) Thanks! Bill Bill Stewart, [EMAIL PROTECTED] PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639
Re: Eason/Kawaguchi stego
--
From: David Honig [EMAIL PROTECTED]
To: Jay Holovacs [EMAIL PROTECTED]; Russell Nelson [EMAIL PROTECTED];
[EMAIL PROTECTED]
Subject: Re: Eason/Kawaguchi stego
\begin{nuance}
Except that encrypted LSBs will be perfectly uniformly distributed
and normal noise won't. Its possible to reversibly sculpt crypto
data to have a less conspicuous spectrum.
\end{nuance}
Good stego can choose LSBs from pseudo randomly bit locations. LSBs from
these locations should be indistinguishable from random if appropriate
images are used.
jay
Re: Eason/Kawaguchi stego
At 9:42 AM -0700 6/29/99, Russell Nelson wrote: So you've got a chicken-and-egg problem -- you have to have yet another set of public keys for your stego crypto algorithm. It seems to me you could use an existing public key infrastructure, e.g. PGP, but build a different message format with the stego requirements in mind. Off the top of my head (using PGP 2.6): (size, data) (256, key) - RSA encrypted key padded with pseudo-random padding to 256 bytes. (The size of the RSA key will determine the size of the encrypted session key, and the receiver knows the size of the RSA key.) (8, IV)- The (random) initialization vector (n, data) - The data encrypted with 3DES in CBC mode + whatever padding scheme suits your fancy. I like having the first 8 byes of encrypted data being the length of the data. (m, pad) - Pseudo-random padding to fill out the stego block. - Bill Frantz | The availability and use of secure encryption may | Periwinkle | offer an opportunity to reclaim some portion of | Consulting | the privacy we have lost. - B. FLETCHER, Circuit Judge|
Papers at CHES
--- begin forwarded text Date: Wed, 30 Jun 1999 10:51:22 +0200 (MESZ) From: Christof Paar [EMAIL PROTECTED] To: DCSB [EMAIL PROTECTED] Subject: Papers at CHES Please find below a list of accepted papers and invited presentations at CHES (Workshop on Cryptographic Hardware and Embedded Systems) in Worcester, Massachusetts. For registration information, please visit our web site at http://ece.wpi.edu/Research/crypt/ches Regards, Christof *** Christof Paar, Assistant Professor Cryptography and Information Security (CRIS) Group ECE Dept., WPI, 100 Institute Rd., Worcester, MA 01609, USA fon: (508) 831 5061email: [EMAIL PROTECTED] fax: (508) 831 5491www: http://ee.wpi.edu/People/faculty/cxp.html *** --- Workshop on Cryptographic Hardware and Embedded Systems Worcester, Massachusetts, August 12-13, 1999 http://ece.wpi.edu/Research/crypt/ches --- Accepted Papers: A. Shamir Factoring large numbers with the TWINKLE device J. H. Silverman. Fast multiplication in finite fields GF(2^N) B. Kaliski and M. Liskov Efficient finite field basis conversion involving dual bases H. Wu, M. A. Hasan, and I. F. Blake. Highly regular architectures for finite field computation using redundant basis H. Wu Low complexity bit-parallel finite field arithmetic using polynomial basis K. Itoh, M. Takenaka, N. Torii, S. Temma, and Y. Kurihara Fast implementation of public-key cryptography P. J. Lee, E. J. Lee, and Y. D. Kim How to implement cost-effective and secure public key cryptosystems J. Lopez and R. Dahab Fast multiplication on elliptic curves over GF(2^m) without precomputation L. Gao, S. Shrivastava, and G. E. Sobelman Elliptic curve scalar multiplier design using FPGAs Y. Han, J. Zhang, and P.-C. Tan Direct computation for elliptic curve cryptosystems J.-S. Coron Resistance against differential power analysis attacks for elliptic curve cryptosystems L. Goubin and J. Patarin DES and differential power analysis P. Fahn and P. Pearson IPA: A new class of power attacks T. S. Messerges, E. A. Dabbish, and R. H. Sloan Power analysis attacks of modular exponentiation in smartcards H. Handschuh, . Paillier, and J. Stern Probing attacks on tamper-resistant devices V. Bagini and M. Bucci A design of reliable true random number generator for cryptographic applications D. Maher and B. Rance Random number generators founded on signal and information theory W. P. Choi and L. M. Cheng Modelling the crypto-processor from design to synthesis R. R. Taylor and S. C. Goldsteiny A high-performance flexible architecture for cryptography A. F. Tenca and C. K. Koc A scalable architecture for Montgomery multiplication E. Mosanya, C. Teuscher, H. F. Restrepo, P. Galley, and E. Sanchez CryptoBooster: A reconfigurable and modular cryptographic coprocessor I. Hamer and P. Chow DES cracking on the Transmogrifier 2a M. Hartmann, S. Paulus, and T. Takagi NICE - New Ideal Coset Encryption - D. C. Wilcox, L. G. Pierson, P. J. Robertson, and E. L. Witzke A DES ASIC suitable for network encryption at 10 Gbps and beyond E. Hong, J.-H. Chung, and C. H. Lim Hardware design and performance estimation of the 128-bit block cipher cRYPTON T. Horvath Arithmetic design for permutation groups O. Jung and C. Ruland Encryption with statistical self-synchronization in synchronous broadband networks Invited Talks: -- Brian Snow, National Security Agency, USA We Need Assurance Eberhard von Faber, Debis IT Security Services, Germany Security Evaluation Schemes for the Public and Private Market with a Focus on Smart Card Systems Dale Hopkins, Compaq - Atalla, USA Design of Hardware Encryption Systems for e-Commerce Applications Colin D. Walter, Computation Department - UMIST, U.K. An Overview of Montgomery's Multiplication Technique: How to make it Smaller and Faster David Naccache, Gemplus, France Significance Tests and Hardware Leakage --- Workshop on Cryptographic Hardware and Embedded Systems Worcester, Massachusetts, August 12-13, 1999 --- --- Information:http://ece.wpi.edu/Research/crypt/ches E-Mail: [EMAIL PROTECTED] Program Chairs: Cetin Kaya KocChristof Paar [EMAIL PROTECTED] [EMAIL PROTECTED] --- --- end forwarded text - Robert A. Hettinga mailto: [EMAIL PROTECTED] The Digital Bearer Underwriting Corporation http://www.ibuc.com/ 44 Farquhar Street, Boston, MA 02131 USA "... however it may deserve respect for its usefulness and antiquity,
The Beer Bottle Cipher (some fun summer reading for you...)
The Beer Bottle Cipher
Ron Rivest
6/30/99
Last week an MIT student hacker broke into the famous Yale University
secret drinking society known as "Skull and Bones". He made a
startling discovery that has implications for national security,
saloons, and camp counselors nationwide.
What he discovered gives a surprising explanation for the origin and
meaning of the well-known drinking song "99 Bottles of Beer on the
Wall." The song, familiar to many, starts with the verse:
99 bottles of beer on the wall,
99 bottles of beer.
Take one down,
Pass it around,
98 bottles of beer on the wall.
Successive verses are the same, with the numbers reduced by one each
time. The song ends (sadly, but in glorious harmony) with "No bottles
of beer on the wall".
Apparently, this drinking song describes an encryption procedure used
by Skull and Bones' members to protect sensitive information. The
procedure, called the "Beer Bottle Cipher," was devised in the early
1700's by a mathematically-inclined Skull and Bones member. The song
was crafted as a mnemonic for the procedure.
The MIT student discovered a yellowed manuscript in the SB vault
describing the origin and meaning of the song. ("Lock-picking that
vault was a piece of cake," the student was reported as saying.)
The Skull and Bones society uses the Beer Bottle Cipher to protect
its most valuable information. For example, it protects embarassing
personal secrets revealed by new members at their initiation ceremony.
(Details of the initiation ceremony, such as whether it is actually
held in the nude, as has been reported, were not described in this
manuscript.)
The MIT student has anonymously posted a copy of the manuscript on the
Net. This note gives a technical overview of the cipher.
This discovery may have implications for the current congressional
debate about encryption policy, since current export policy would
now prohibit the singing of this song in the presence of foreigners.
(In recognition of this development, the U.S. Navy has just instructed
its sailors to begin the song with 56 bottles of beer rather than the
conventional 99 bottles of beer when they are in a foreign port, or in
the presence of foreigners. And Louis Freeh is rumored to be asking
Congress to pass a constitutional amendment banning the song altogether.)
We now give the encryption procedure itself.
Suppose we start with "n bottles of beer on the wall". Imagine that
this row of bottles holds an n-digit number---each bottle holds one
decimal digit. (Imagine the bottles lined up left to right, with the
left-most bottle holding the most-significant digit.)
The plaintext to be encrypted is first represented as a number, using
two bottles for each letter (A = 01, B = 02, and so on). A "space" is
represented as 00. Thus, the secret "BALD MOTHER" would be
represented by the number 0201120400131520080518, using 22 bottles.
If, as in this case, the plaintext needs fewer than 99 bottles, then
it uses just the right-most bottles, and the left-most bottles hold
zeros, so the total number of bottles is 99. (For longer secrets,
start out with more bottles, and sing more verses.)
There is also an encryption key, known as the "skull". The skull is a
long secret number known only to the president and vice-president of
the society. (George Bush (senior) is believed to have served as an
SB president, which may help explain his later political successes.)
In addition, there is the "table", which is where the "empties" go.
That is, when you "take one down, pass it around", one bottle is taken
off the wall (from the right end) and put down at the right end of the
row of empties. In the encryption procedure the bottles on the table
are not really empties, since they still contain digits, and the
actual procedure is a bit more complicated.
Anyway, you start with n bottles of beer on the wall holding the
plaintext and end up when the song is over with n empties on the table
holding the ciphertext.
The procedure is complicated enough that you probably should not be
drinking beer when you try to do it. The song helps you keep on
track throughout.
Once you have got set up to encrypt, with the plaintext on the wall,
skull in hand, and table empty, you just sing the song. Each phrase
in the song tells you exactly what to do next. The four phrases are:
"k bottles of beer"
"on the wall"
"Take one down"
"Pass it around"
Each phrase has a meaning, instructing you how to encrypt, as follows:
"k bottles of beer"
-- First you take the left-most bottle of beer on
the wall and move it over to the right-most end.
The k bottles in a row on the wall represent a
k-digit number. As you sing "k bottles of beer"
you multiply that number by the
Re: The Beer Bottle Cipher (some fun summer reading for you...)
At 12:07 -0400 1999.06.30, Ron Rivest described the Beer Bottle Cypher, asking: The actual security of this cipher seems to be an open question... Can it be broken? Have you tried getting an export license for it? Martin Minow [EMAIL PROTECTED]
