<<

. 7
( 11 .)



>>

[19] Kelsey, J., B. Schneier, and D. Wagner (1999). “Mod
and linear cryptanalysis.” Fast Software Encryp-
n cryptanalysis, with applications against RC5P
tion, Third International Workshop, Cambridge,
and M6.” Fast Software Encryption, Sixth Inter-
UK, February 1996, Lecture Notes in Computer
national Workshop, Rome, Italy, March 1999, Lec-
Science, vol. 1039, ed. D. Gollman. Springer-Verlag,
ture Notes in Computer Science, vol. 1636, ed. L.
Berlin, 205“218.
Knudsen. Springer-Verlag, Berlin, 139“155.
[33] Matsui, M. (1997). “New block encryption algo-
[20] Kilian, J. and P. Rogaway (1996). “How to protect
rithm MISTY.” Fast Software Encryption, Fourth
DES against exhaustive key search.” Advances in
International Workshop, Haifa, Israel, January
Cryptology”CRYPTO™96, Lecture Notes in Com-
1997, Lecture Notes in Computer Science, vol.
puter Science, vol. 1109, ed. Neal Koblitz. Springer-
1267, ed. E. Biham. Springer-Verlag, Berlin, 54“
Verlag, London, 252“267.
68.
[21] Knudsen, L.R. (1994). “Block Ciphers”Analysis,
[34] Matsui, M. and A. Yamagishi (1992). “A new
Design and Applications.” PhD Thesis, Aarhus
method for known plaintext attack of FEAL ci-
University, Denmark.
pher.” Advances in Cryptology”EUROCRYPT™92,
[22] Knudsen, L.R. (1995). “Truncated and higher order
Lecture Notes in Computer Science, vol. 658, ed.
differentials.” Fast Software Encryption”Second
R. Rueppel. Springer-Verlag, Berlin, 81“91.
International Workshop, Leuven, Belgium, Lec-
[35] National Bureau of Standards (1977). “Data en-
ture Notes in Computer Science, vol. 1008, ed. B.
cryption standard.” Federal Information Process-
Preneel. Springer-Verlag, Berlin, 196“211.
ing Standard (FIPS), Publication 46, National Bu-
[23] Knudsen, L.R. and W. Meier (2001). “Correla-
reau of Standards, U.S. Department of Commerce,
tions in RC6 with a reduced number of rounds.”
Washington, DC.
Fast Software Encryption, 7th International Work-
[36] National Bureau of Standards (1980). “DES modes
shop, FSE 2000, New York, USA, April 2000, Lec-
of operation.” Federal Information Processing
ture Notes in Computer Science, vol. 1978, ed.
Standard (FIPS), Publication 81, National Bu-
B. Schneier. Springer-Verlag, Berlin, 94“108.
reau of Standards, U.S. Department of Commerce,
[24] Knudsen, L.R. and M.P.J. Robshaw (1996). “Non-
Washington, DC.
linear approximations in linear cryptanalysis.” Ad-
[37] National Institute of Standards and Technology.
vances in Cryptology”EUROCRYPT™96, Lecture
Advanced encryption algorithm (AES) develop-
Notes in Computer Science, vol. 1070, ed. U.
ment effort. http://www.nist.gov/aes
Maurer. Springer-Verlag, Berlin, 224“236.
[38] NIST (2001). “Advanced encryption standard.”
[25] Knudsen, L.R. and D. Wagner (2001). “Integral
FIPS 197, US Department of Commerce, Washing-
cryptanalysis.” FSE 2002. To appear in proceed-
ton, DC, November 2001.
ings from Springer-Verlag, Berlin.
48 Blow¬sh


32 bits 32 bits
[39] Nyberg, K. (1993). “Differentially uniform map-
pings for cryptography.” Advances in Cryptology” Pi
EUROCRYPT™93, Lecture Notes in Computer Sci-
S-box 1
ence, vol. 765, ed. T. Helleseth. Springer-Verlag,
Berlin, 55“64.
[40] Nyberg, K. and L.R. Knudsen (1993). “Provable S-box 2
32 bits
security against differential cryptanalysis.” Ad-
vances in Cryptology”CRYPTO™92, Lecture Notes S-box 3 32 bits
in Computer Science, vol. 740, ed. E.F. Brickell.
Springer-Verlag, Berlin, 566“574.
S-box 4
[41] Nyberg, K. and L.R. Knudsen (1995). “Provable se-
curity against a differential attack.” The Journal
of Cryptology, 8 (1), 27“38.
[42] Preneel, B. (1993). “Analysis and Design of Crypto-
graphic Hash Functions.” PhD Thesis, Katholieke
Universiteit Leuven.
[43] Shannon, C.E. (1949). “Communication theory of
secrecy systems.” Bell System Technical Journal,
28, 656“715. Fig. 1. One round of Blow¬sh
[44] Stinson, D.R. (1995). Cryptography”Theory and
Practice. CRC Press, Inc., Boca Raton, FL. into two 32-bits words. First, a round key is XORed
[45] Tuchman, W. (1979). “Hellman presents no short- to the left word. The result is then input to four
cut solutions to DES.” IEEE Spectrum, 16 (7), 40“
key-dependent 8 — 32-bit S-boxes, yielding a 32-
41.
bit output word which is XORed to the right word.
[46] van Oorschot, P.C. and M.J. Wiener (1996).
Both words are swapped and then fed to the next
“Improving implementable meet-in-the-middle at-
iteration.
tacks of orders of magnitude.” Advances in
The use of key-dependent S-boxes distinguishes
Cryptology”CRYPTO™96, Lecture Notes in Com-
Blow¬sh from most other ciphers, and requires
puter Science, vol. 1109, ed. Neal Koblitz. Springer-
a rather complex key-scheduling algorithm. In
Verlag, Berlin, 229“236.
[47] Vaudenay, S. (1995). “An experiment on DES” a ¬rst pass, the lookup tables determining the
S-boxes are ¬lled with digits of π, XORed with
Statistical cryptanalysis.” Proceedings of the 3rd
ACM Conferences on Computer Security, New bytes from a secret key which can consist of 32“
Delhi, India. ACM Press, New York, 139“147. 448 bits. This preliminary cipher is then used to
[48] Vaudenay, S. (1998). “Provable security for block ci-
generate the actual S-boxes. Although Blow¬sh
phers by decorrelation.” STACS™98, Lecture Notes
is one of the faster block ciphers for suf¬ciently
in Computer Science, vol. 1373, eds. M. Morvan,
long messages, the complicated initialization pro-
C. Meinel, and D. Krob. Springer-Verlag, Berlin,
cedure results in a considerable ef¬ciency degra-
249“275.
dation when the cipher is rekeyed too frequently.
[49] Vaudenay, S. (1999). “Resistance against general
The need for a more ¬‚exible key schedule was one
iterated attacks.” Advances in Cryptology”EURO-
of the factors that in¬‚uenced the design of Two¬sh,
CRYPT™99, Lecture Notes in Computer Science,
vol. 1592, ed. J. Stem. Springer-Verlag, Berlin. an Advanced Encryption Standard (see Rijndael/
[50] Wagner, D. (1999). “The boomerang attack.” Fast AES) ¬nalist which was inspired by Blow¬sh.
Software Encryption, Sixth International Work- Since the publication of Blow¬sh, only a few
shop, Rome, Italy, March 1999, Lecture Notes in cryptanalytical results have been published. A
Computer Science, vol. 1636, ed. L.R. Knudsen.
¬rst analysis was made by Vaudenay [4], who re-
Springer-Verlag, Berlin 156“170.
vealed classes of weak keys for up to 14 rounds
of the cipher. Rijmen [2] proposed a second-
order differential attack on a four-round variant of
Blow¬sh. In a paper introducing slide attacks [1],
BLOWFISH Biryukov and Wagner highlighted the importance
of XORing a different subkey in each round of
Blow¬sh [3] is a 64-bit block cipher designed by
Blow¬sh.
Bruce Schneier and published in 1994. It was in-
tended to be an attractive alternative to DES (see Christophe De Canni` re
e
Data Encryption Standard) or IDEA. Today, the
References
Blow¬sh algorithm is widely used and included
in many software products.
Blow¬sh consists of 16 Feistel-like iterations. [1] Biryukov, A. and D. Wagner (1999). “Slide attacks.”
Each iteration operates on a 64-bit datablock, split Proceedings of Fast Software Encryption”FSE™99,
BLS short digital signatures 49


Output (g, y, H) as the public key and (g, ±, H)
Lecture Notes in Computer Science, vol. 1636, ed.
L.R. Knudsen. Springer-Verlag, Berlin, 245“259. as the private key.
Signing. To sign a message m ∈ {0, 1}— using the
[2] Rijmen, V. (1997). “Cryptanalysis and Design of It-
private key (g, ±, H) output H(m)± ∈ G as the
erated Block Ciphers.” PhD Thesis, Katholieke Uni-
versiteit Leuven. signature.
[3] Schneier, B. (1994). “Description of a new variable-
Verifying. To verify a message/signature pair
length key, 64-bit block cipher (Blow¬sh).” Fast
(m, s) ∈ {0, 1}— — G using the public key
Software Encryption, FSE™93, Lecture Notes in
(g, y, H) test if e(g, s) = e(y, H(m)). If so, accept
Computer Science, vol. 809, ed. R.J. Anderson.
the signature. Otherwise, reject.
Springer-Verlag, Berlin, 191“204.
For a valid message/signature pair (m, s)
[4] Vaudenay, S. (1996). “On the weak keys of Blow¬sh.”
we have that s = H(m)± and therefore e(g, s) =
Fast Software Encryption, FSE™96, Lecture Notes
e(g, H(m)± ) = e(g±, H(m)) = e(y, H(m)). The second
in Computer Science, vol. 1039, ed. D. Gollmann.
Springer-Verlag, Berlin, 27“32. equality follows from the bilinearity of e(, ). Hence,
a valid signature is always accepted. As mentioned
above, the system is existentially unforgeable un-
der a chosen message attack in the random or-
BLS SHORT DIGITAL acle model, assuming the computational Dif¬e“
SIGNATURES Hellman assumption holds in G. Observe that a
signature is a single element in G whereas DSS
signatures are pairs of elements. This explains the
It is well known that a digital signature scheme
reduction in signature length compared to DSS.
that produces signatures of length can have se-
Recently, Boneh and Boyen [1] and Zhang
curity at most 2 . In other words, it is possible to
et al. [4] describe a more ef¬cient system produc-
forge a signature on any message in time O(2 ) just
ing signatures of the same length as BLS. How-
given the public key. It is natural to ask whether
ever, security is based on a stronger assumption.
we can construct signatures with such security,
Key generation is identical to the BLS system, ex-
i.e., signatures of length where the best algo-
cept that the hash function used is H : {0, 1}— ’
rithm for creating an existential forgery (with con-
Zq . A signature on a message m ∈ {0, 1}— is s =
stant success probability) under a chosen message
g1/(±+H(m)) ∈ G. To verify a message/signature pair
attack takes time O(2 ). Concretely, is there a sig-
(m, s) test that e(yg H(m) , s) = e(g, g). We see that
nature scheme producing 80-bit signatures where
signature length is the same as in BLS signatures.
creating an existential forgery (with probability
1/2) takes time approximately 280 ? However since e(g, g) is ¬xed, signature veri¬ca-
tion requires only one computation of the bilin-
DSS signatures and Schnorr signatures provide
ear map as opposed to two in BLS. Security of
security O(2 ) with signatures that are 4 -bits
the system in the random oracle model is based
long. These signatures can be shortened [3] to
on a nonstandard assumption called the t-Dif¬e“
about 3.5 -bits without much affect on security.
Hence, for concrete parameters, = 80, shortened Hellman-inversion assumption. Loosely speaking,
the assumption states that no ef¬cient algorithm
DSS signatures are 280-bits long. 2 t
given g, g x , g(x ) , . . . , g(x ) as input can compute
Boneh et al. [2] describe a short signature
g1/x . Here t is the number of chosen message
scheme where 170-bit signatures provide approx-
imately 280 security, in the random oracle model. queries that the attacker can make. Surprisingly,
Hence, for = 80, these signatures are approxi- a variant of this system can be shown to be existen-
tially unforgeable under a chosen message attack
mately half the size of DSS signatures with com-
without the random oracle model [1].
parable security. The system makes use of a group
G where (i) the computational Dif¬e“Hellman
Dan Boneh
problem is intractable, and (ii) there is an ef¬-
ciently computable, nondegenerate, bilinear map
References
e : G — G ’ G1 for some group G1 . There are sev-
eral examples of such groups from algebraic ge-
[1] Boneh, Dan and Xavier Boyen (2004). “Short sig-
ometry where the bilinear map is implemented
natures without random oracles.” Proceedings of
using the Weil pairing. Given such a group G of Eurocrypt 2004, Lecture Notes in Computer Sci-
prime order q, the digital signature scheme works ence, vol. 3027, eds. C. Cachin and J. Camenisch.
as follows: Springer-Verlag, Berlin, 56“73.
Key Generation. [2] Boneh, Dan, Ben Lynn, and Hovav Shacham (2004).
1. Pick an arbitrary generator g ∈ G. “Short signatures from the Weil pairing.” J. of
2. Pick a random ± ∈ {1, . . . , q} and set y = g± ∈ G. Cryptology. Extended abstract in Proceedings of
3. Let H be a hash function H : {0, 1}— ’ G. ASIACRYPT 2001, Lecture Notes in Computer
50 Blum“Blum“Shub pseudorandom bit generator


p = q = 3 mod 4. Set N = pq ∈ Z. Integers N of
Science, vol. 2248, ed. C. Boyd. Springer-Verlag,
Berlin. this type (where both prime factors are distinct
[3] Naccache, David and Jacques Stern (2000). “Signing and are 3 mod 4) are called Blum integers. Next
pick a random y in the group Z— and set s =
on a postcard.” Proceedings of Financial Cryptogra-
N
phy 2000. —
y ∈ Z N. The secret seed is (N, s). As we will see
2
[4] Zhang, Fangguo, Reihaneh Safavi-Naini, and Willy
below, there is no need to keep the number N
Susilo (2004). “An ef¬cient signature scheme from
secret.
bilinear pairings and its applications.” Proceedings
Generate. Given an input ∈ Z and a seed (N, s)
of PKC 2004.
we generate a pseudorandom sequence of length

<<

. 7
( 11 .)



>>