Notes

References

[1] AJTAI, M. Generating hard instances of lattice problems. In Proc. 28th ACM
Symp. on Theory of Computing (1996), ACM, pp. 99–108.

[2] ANDERSON, R. The classification of hash functions. In Proc. Codes and
Cyphers: Cryptography and Coding IV (1995), pp. 83–93.

[3] AUGOT, D., FINIASZ, M., GABORIT, P., MANUEL, S., AND SENDRIER, N. SHA-
3 proposal: FSB. Submission to NIST. http://www-rocq.inria.fr/secret/
CBCrypto/fsbdoc.pdf., October 2008.

[4] AUGOT, D., FINIASZ, M., AND SENDRIER, N. A new dedicated 256-bit
hash function: FORK-256. In Progress in Cryptology–MyCrypt 2005 (2005),
vol. 3615 of Lecture Notes in Computer Science, Springer-Verlag, pp. 64–83.

[5] BARKER, E., AND KELSEY, J. Recommendation for random number generation
using deterministic random bit generators (revised, 2007. NIST Special
Publication 800-90.

[6] BEKER, H., AND PIPER, F. Cipher systems: the protection of communications.
Northwood, 1982.

[7] BELLARE, M. New proofs for NMAC and HMAC: Security without collision
resistance. In Advances in Cryptology–CRYPTO 2006 (2006), vol. 4117 of
Lecture Notes in Computer Science, Springer-Verlag, pp. 602–619.

[8] BELLARE, M., CANETTI, R., AND KRAWCZYK, H. Keying hash functions for
message authentication. In Advances in Cryptology–CRYPTO 1996 (1996),
vol. 1109 of Lecture Notes in Computer Science, Springer-Verlag, pp. 1–15.

[9] BELLARE, M., CANETTI, R., AND KRAWCZYK, H. HMAC: Keyed-hashing for
message authentication. Tech. rep., IETF, 1997. RFC 2104.

[10] BELLARE, M., AND ROGAWAY, P. Random oracles are practical: A paradigm
for designing efficient protocols. In ACM Conference on Computer and Communications
Security (1993), pp. 62–73.

[11] BENTAHAR, K., PAGE, D., SAARINEN, M.-J., SILVERMAN, J., AND SMART, N.
LASH, 2006. 2nd NIST Cryptographic Hash Workshop.

[12] BIERE, A., HEULE, M., MAAREN, H. V., AND WALSH, T. Handbook of Satisfiability.
IOS Press, 2009.

[13] BIHAM, E., AND SHAMIR, A. Differential Cryptanalysis of the Data Encryption
Standard. Springer-Verlag, 1993.

[14] BIHAM, E., AND SHAMIR, A. Differential fault analysis of secret key cryptosystems.
In Advances in Cryptology–CRYPTO ’97 (1997), vol. 1294 of Lecture
Notes in Computer Science, Springer-Verlag, pp. 513–525.

[15] BIRYUKOV, A., AND WAGNER, D. Slide attacks. In Proc. Fast Software Encryption
1999 (1999), vol. 1636 of Lecture Notes in Computer Science, Springer-
Verlag, pp. 245–259.

[16] BIRYUKOV, A., AND WAGNER, D. Advanced slide attacks. In Advances in
Cryptology–EUROCRYPT 2000 (2000), vol. 1807 of Lecture Notes in Computer
Science, Springer-Verlag, pp. 589–606.

[17] BLACK, J., ROGAWAY, P., AND SHRIMPTON, T. Black-box analysis of the
block-cipher-based hash-function constructions from PGV. In Advances in
Cryptology–CRYPTO 2002 (2002), vol. 2442 of Lecture Notes in Computer Science,
Springer-Verlag, pp. 320–335.

[18] BONEH, D., DEMILLO, R. A., AND LIPTON, R. J. On the importance of checking
protocols for faults. In Advances in Cryptology–EuroCrypt ’97 (1997),
vol. 1233 of Lecture Notes in Computer Science, Springer-Verlag, pp. 37–51.

[19] BROWN, D. R. L., ANTIPA, A., CAMPAGNA, M., AND STRUIK, R. ECOH: the
elliptic curve only hash. Tech. rep., Certicom Corp., Nov. 2008. First Round
NIST SHA-3 Candidate.

[20] CHANG, D., HONG, S., KANG, C., KANG, J., KIM, J., LEE, C., LEE, J., LEE, J.,
LEE, S., LEE, Y., LIM, J., AND SUNG, J. ARIRANG. Submission to NIST. http:
//ehash.iaik.tugraz.at/uploads/2/2c/Arirang.pdf, October 2008.

[21] CLOTE, P., AND KRANAKIS, E. Boolean Functions and Computation Models.
Springer-Verlag, 2002.

[22] CONTINI, S., AND A.K. LENSTRA, R. S. VSH, an efficient and provable collision
resistant hash function. In Advances in Cryptology–EUROCRYPT 2006
(2006), vol. 4004 of Lecture Notes in Computer Science, Springer-Verlag,
pp. 165–185.

[23] CONTINI, S., LENSTRA, A. K., AND STEINFELD, R. VSH, an efficient and provable
collision resistant hash function, 2005. IACR ePrint Archive 2005/193.

[24] CONTINI, S., MATUSIEWICZ, AND PIEPRZYK, J. Extending FORK-256 attack
to the full hash function. In Information and Communications Security, 9th
International Conference, ICICS 2007 (2008), vol. 4861 of Lecture Notes in
Computer Science, Springer-Verlag, pp. 296–305.

[25] CONTINI, S., MATUSIEWICZ, K., PIEPRZYK, J., STEINFELD, R., JIAN, G., AN,
L., AND WANG, H. Cryptanalysis of LASH. In Proc. Fast Software Encryption
2008 (2008), vol. 5086 of Lecture Notes in Computer Science, Springer-Verlag,
pp. 207–223.

[26] COPPERSMITH, D. Analysis of ISO/CCITT Document X.509 Annex D. Tech.
rep., IBM Research Division, Yorktown Heights, N.Y., June 1989.

[27] CORON, J.-S., AND JOUX., A. Cryptanalysis of a provably secure cryptographic
hash function, 2004. IACR ePrint Archive 2004/013.

[28] COURTOIS, N. T. General principles of algebraic attacks and new design
criteria for components of symmetric ciphers. In AES 4 Conference, Bonn May
10-12 2004 (2005), vol. 3373 of Lecture Notes in Computer Science, Springer-
Verlag, pp. 67–83.

[29] COURTOIS, N. T., AND BARD, G. V. Algebraic cryptanalysis of the data encryption
standard. In Cryptography and Coding 2007 (2007), vol. 4887 of
Lecture Notes in Computer Science, Springer-Verlag, pp. 152–169.

[30] COURTOIS, N. T., NOHL, K., AND O’NEIL, S. Algebraic attacks on the crypto-
1 stream cipher in MIFARE Classic and Oyster cards, 2008. IACR ePrint
Archive 2008/166.

[31] COURTOIS, N. T., AND PIEPRZYK, J. Cryptanalysis of block ciphers with
overdefined systems of equations. In ASIACRYPT 2002 (2002), vol. 2501
of Lecture Notes in Computer Science, Springer-Verlag, pp. 152–169.

[32] DAMG°A RD, I. A design principle for hash functions. In Advances in
Cryptology–CRYPTO 1989 (1990), vol. 435 of Lecture Notes in Computer Science,
Springer-Verlag, pp. 416–427.

[33] DEN BOER, B., AND BOSSELAERS, A. Collisions for the compression function
of MD5. In Advances in Cryptology–EUROCRYPT 1993 (1994), vol. 765 of
Lecture Notes in Computer Science, Springer-Verlag, pp. 293–304.

[34] DIERKS, R., AND RESCORLA, E. The transport layer security (TLS) protocol–
version 1.1, 2006. Internet Engineering Task Force RFC 4346.

[35] DOBBERTIN, H. Cryptanalysis of MD5 compress, 1996. Presented at EUROCRYPT
’96 rump session, May 14, 1996.

[36] FERGUSON, N., LUCKS, S., SCHNEIER, B., WHITING, D., BELLARE, M.,
KOHNO, T., CALLAS, J., AND WALKER, J. The Skein hash function family,
2008. Submission to NIST.

[37] FILIOL, E. A new statistical testing for symmetric ciphers and hash functions.
In Proc. ICICS 2002 (2002), vol. 2513 of Lecture Notes in Computer Science,
Springer-Verlag, pp. 342–353.

[38] FINIASZ, M., GABORIT, P., AND SENDRIER, N. Improved fast syndrome based
cryptographic hash functions, 2007. ECRYPT Hash Function Workshop 2007.

[39] FRIEDMAN, W. F. The index of coincidence and its applications in cryptology.
No. 22. Riverbank Laboratories, Department of Ciphers, 1922.

[40] GIVANT, S., AND HALMOS, P. Introduction to Boolean Algebras. Undergraduate
Texts in Mathematics. Springer-Verlag, 2009.

[41] GOLDREICH, O. Foundations of Cryptography, Vol. 1, Basic Tools. Cambridge
University Press, 2007.

[42] GOLDREICH, O., GOLDWASSER, S., AND HALEVI, S. Collision-free hashing
from lattice problems. Tech. Rep. TR96-042, Electronic Colloquium on Computational
Complexity (ECCC), 1996.

[43] GOLDREICH, O., GOLDWASSER, S., AND MICALI, S. How to construct random
functions. Journal of the ACM 33, 4 (1986), 792–807.

[44] GREENWOOD, P. G., AND NIKULIN, M. S. A guide to chi-squared testing. Wiley
series in probability and statistics. Wiley, 1996.

[45] GROSSMAN, E. K., AND TUCKERMAN, B. Analysis of a Feistel-like cipher weakened
by having no rotating key. Tech. rep., IBM Thomas J. Watson Research
Centre, 1977.

[46] GUO, J., MATUSIEWICZ, K., KNUDSEN, L. R., LING, S., AND
WANG, H. Practical pseudo-collisions for hash functions ARIRANG-
224/384. Available online at http://ehash.iaik.tugraz.at/uploads/9/
9a/Arirang-pseudo-sha3zoo.pdf., 2009.

[47] GUTMANN, P. C. Secure file system (SFS) version 1.0 documentation, 1993.
Available at: http://www.cs.auckland.ac.nz/~pgut001sfs/.

[48] HANDSCHUH, H., KNUDSEN, L. R., AND NACCACHE, D. Analysis of SHA-1 in
encryption mode. In Topics in Cryptology–RSA-CT 2001 (2001), vol. 2020 of
Lecture Notes in Computer Science, Springer-Verlag, pp. 70–83.

[49] HANDSCHUH, H., AND NACCACHE, D. SHACAL, 2000. Available at: http:
//www.cryptonessie.org.

[50] HANDSCHUH, H., AND NACCACHE, D. SHACAL: A family of block ciphers,
2002. Available at: http://www.cryptonessie.org.

[51] H°A STAD, J. On using RSA with low exponent in a public key network. In
Advances in Cryptology–CRYPTO 1985 (1985), vol. 218 of Lecture Notes in
Computer Science, Springer-Verlag, pp. 403–408.

[52] HILTGEN, A. P. Towards a better understanding of one-wayness: Facing
linear permutations. In Advances in Cryptology–EUROCRYPT’98 (1998),
vol. 1403 of Lecture Notes in Computer Science, Springer-Verlag, pp. 319–33.

[53] HONG, D., CHANG, D., SUNG, J., LEE, S., HONG, S., LEE, J., MOON, D.,
AND CHEE, S. A new dedicated 256-bit hash function: FORK-256. In Proc.
Fast Software Encryption 2006 (2007), vol. 4047 of Lecture Notes in Computer
Science, Springer-Verlag, pp. 195–209.

[54] HONG, D., CHANG, D., SUNG, J., LEE, S., HONG, S., LEE, J., MOON, D., AND
CHEE, S. New FORK-256, 2007. IACR ePrint Archive 2007/185.

[55] HONG, D., KIM, W.-H., AND KOO, B. Preimage attack on ARIRANG. Cryptology
ePrint Archive, Report 2009/147. http://eprint.iacr.org/2009/147.
pdf., 2009.

[56] JOUX, A. Multicollisions in iterated hash functions. application to cascaded
constructions. In Advances in Cryptology–CRYPTO 2004 (2004), vol. 3152 of
Lecture Notes in Computer Science, Springer-Verlag, pp. 306–316.

[57] KALISKI, B. S., AND ROBSHAW, M. J. B. Fast block cipher proposal. In Proc.
Fast Software Encryption 1993 (1994), vol. 809 of Lecture Notes in Computer
Science, Springer-Verlag, pp. 33–40.

[58] KELSEY, J., AND KOHNO, T. Herding hash functions and the Nostradamus
attack, 2005. IACR ePrint Archive 2005/281.

[59] KELSEY, J., AND SCHNEIER, B. Second preimages on n-bit hash functions for
much less than 2n work. In Advances in Cryptology–EUROCRYPT 2005 (2005),
vol. 3495 of Lecture Notes in Computer Science, Springer-Verlag, pp. 474–490.

[60] KNUTH, D. E. The Art of Computer Programming, vol. 2: Seminumerical Algorithms,
2 ed. Addison-Wesley, 1981.

[61] KNUTH, D. E. The Art of Computer Programming, vol. 3: Sorting and Searching,
2 ed. Addison-Wesley, 1981.

[62] KOCHER, P. C. Timing attacks on implementations of Diffie-Hellman, RSA,
DSS, and other systems. In Advances in Cryptology–CRYPTO 1996 (1996),
vol. 1109 of Lecture Notes in Computer Science, Springer-Verlag, pp. 104–113.

[63] KOCHER, P. C., E, J. J., AND JUN, B. Differential power analysis. In Advances
in Cryptology–CRYPTO 1999 (1999), vol. 1666 of Lecture Notes in Computer
Science, Springer-Verlag, pp. 388–397.

[64] LUCKS, S. Design principles for iterated hash functions, 2004. IACR ePrint
Archive 2004/253.

[65] MATSUI, M. Linear cryptoanalysis method for DES cipher. In Advances in
Cryptology – EUROCRYPT 1993 (1994), vol. 765 of Lecture Notes in Computer
Science, Springer-Verlag, pp. 386–397.

[66] MATUSIEWICZ, CONTINI, S., AND PIEPRZYK, J. Weaknesses of the FORK-256
compression function, 2006. IACR ePrint Archive 2006/317.

[67] MATUSIEWICZ, PEYRIN, T., BILLET, O., CONTINI, S., AND PIEPRZYK, J.
Cryptanalysis of FORK-256. In Proc. Fast Software Encryption 2007 (2007),
vol. 4593 of Lecture Notes in Computer Science, Springer-Verlag, pp. 19–38.

[68] MAURER, U. Indistinguishability of random systems. In Advances in Cryptology
– EUROCRYPT 2002 (2002), vol. 2332 of Lecture Notes in Computer
Science, Springer-Verlag, pp. 110–133.

[69] MENDEL, F., LANO, J., AND PRENEEL, B. Cryptanalysis of reduced variants of
the FORK-256 hash function. In Topics in Cryptology–CT-RSA 2007 (2007),
vol. 4377 of Lecture Notes in Computer Science, Springer-Verlag, pp. 85–100.

[70] MENEZES, A., VAN OORSCHOT, P., AND VANSTONE, S. Handbook of Applied
Cryptography, first ed. CRC Press, 1996.

[71] MERKLE, R., AND HELLMAN, M. Hiding information and signatures in trapdoor
knapsacks. IEEE Trans. Information Theory 24, 5 (September 1978),
525–530.

[72] MIYAGUCHI, S., OHTA, K., AND WATA, M. I. 128-bit hash function (N-hash).
NTT Review 6, 2 (1990), 128–132.

[73] MORRIS, R., AND THOMPSON, K. Password security: A case history. Communications
of the ACM 22 (November 1979), 594–597.

[74] MURPHY, S. The power of NIST’s statistical testing of AES candidates. Tech.
rep., Royal Holloway, University of London, Apr. 2000. AES Comment to
NIST.

[75] NICHOLS, R. K., AND LEKKAS, P. C. Wireless Security–Models, Threats, and
Solutions. McGraw-Hill, 2002.

[76] NISHIMURA, K., AND SIBUYA, M. Probability to meet in the middle. Journal
of Cryptology, 2 (1990), 13–22.

[77] NIST. FIPS PUB 180-1: Secure hash standard, 1995. Federal Information
Processing Standards Publication.

[78] NIST. FIPS PUB 180-2: Digital signature standard (DSS), 2000. Federal
Information Processing Standards Publication.

[79] NIST. FIPS PUB 180-2: Secure hash standard, 2001. Federal Information
Processing Standards Publication.

[80] NIST. Announcing the development of new hash algorithm(s) for the revision
of federal information processing standard (FIPS) 180–2, secure hash
standard. Federal Register 72, 14 (2007), 2861–2863.

[81] NIST. Cryptographic hash function competition, May 2009. Available at:
http://csrc.nist.gov/groups/ST/hash/sha-3/.

[82] PALE, E., AND AHTOKARI, R. Suomen Radiotiedustelu 1927 – 1944. Viestikoelaitoksen
kilta, 1997. In Finnish. Published by the Guild of the Communications
Research Establishment (Finnish Signals Intelligence).

[83] POLLARD, J. A Monte Carlo method for factorization. BIT Numerical Mathematics
15, 3 (1975), 331–334.

[84] PRENEEL, B. Analysis and design of cryptographic hash functions. PhD thesis,
Katholieke Universiteit Leuven (Belgium), January 1993.

[85] PRENEEL, B., GOVAERTS, R., AND VANDEWALLE, J. Hash functions based
on block ciphers: A synthetic approach. In Advances in Cryptology–CRYPTO
1993 (1993), vol. 773 of Lecture Notes in Computer Science, Springer-Verlag,
pp. 368–378.

[86] QUISQUATER, J.-J., AND DEESCAILLE, J.-P. How easy is collision search?
application to DES. In Advances in Cryptology–EUROCRYPT 1989 (1990),
vol. 434 of Lecture Notes in Computer Science, Springer-Verlag, pp. 429–434.

[87] RIJMEN, V., AND BARRETO, P. Whirlpool, 2004. Seventh hash function of
ISO/IEC 10118-3:2004.

[88] RIVEST, R. The MD4 message-digest algorithm, 1990. Internet Engineering
Task Force RFC 1186.

[89] RIVEST, R. The MD5 message-digest algorithm, 1992. Internet Engineering
Task Force RFC 1321.

[90] RIVEST, R. L. The MD6 hash function – a proposal to NIST
for SHA-3. Submission to NIST, October 2008. Available at:
http://groups.csail.mit.edu/cis/md6/submitted-2008-10-27/
Supporting_Documentation/md6_report.pdf.

[91] ROGAWAY, P. Formalizing human ignorance: Collision-resistant hashing
without the keys. In Proc. INDOCRYPT 2006 (2006), vol. 4341 of Lecture
Notes in Computer Science, Springer-Verlag, pp. 211–228.

[92] ROGAWAY, P., AND SHRIMPTON, T. Cryptographic hash-function basics:
Definitions, implications, and separations for preimage resistance, secondpreimage
resistance, and collision resistance. In Proc. FSE 2004 (2004),
vol. 3017 of Lecture Notes in Computer Science, Springer-Verlag, pp. 371–388.

[93] RSA. RSA-1024 factoring challenge. Available at: http://www.
rsasecurity.com/rsalabs/node.asp?id=2093.

[94] RUKHIN ET. AL., A. A statistical test suite for random and pseudorandom
number generators for cryptographic applications. Tech. Rep. 800-22, National
Institute of Standards and Technology, 2001.

[95] SAARINEN, M.-J. O. A chosen key attack against the secret S-boxes of GOST,
1998. Unpublished manuscript. Available from http://citeseer.ist.psu.
edu/saarinen98chosen.html.

[96] SAARINEN, M.-J. O. Cryptanalysis of block ciphers based on SHA-1 and MD5.
In Proc. Fast Software Encryption 2003 (2003), vol. 2887 of Lecture Notes in
Computer Science, Springer-Verlag, pp. 36–44.

[97] SAARINEN, M.-J. O. Chosen-IV statistical attacks against eSTREAM ciphers.
In Proc. SECRYPT 2006, International Conference on Security and Cryptography,
Setubal, Portugal, August 7-10, 2006. (2006).

[98] SAARINEN, M.-J. O. d-monomial tests are effective against stream ciphers.
In State of the Art in Stream Ciphers (SASC) 2006 Workshop Record. Leuven,
Belgium, February 2-3, 2006. (2006).

[99] SAARINEN, M.-J. O. Security of VSH in the real world. In Progress in
Cryptology–INDOCRYPT 2006 (2006), vol. 4329 of Lecture Notes in Computer
Science, Springer-Verlag, pp. 95–103.

[100] SAARINEN, M.-J. O. Linearization attacks against syndrome based hashes.
In Proc. INDOCRYPT 2007 (2007), vol. 4859 of Lecture Notes in Computer
Science, Springer-Verlag, pp. 1–9.

[101] SAARINEN, M.-J. O. A meet-in-the-middle collision attack against the new
FORK-256. In Proc. INDOCRYPT 2007 (2007), vol. 4859 of Lecture Notes in
Computer Science, Springer-Verlag, pp. 10–17.

[102] SASAO, T., AND DEBNATH, D. Generalized Reed-Muller expressions: Complexity
and an exact minimization algorithm. IEICE Trans. Fundamentals E79,
12 (1996), 2123–2130.

[103] SCHNORR, C. P. Block reduced lattice bases and successive minima. Combinatorics,
Probability and Computing, 3 (1994), 507–533.

[104] SHANKS, D. Class number, a theory of factorization and genera. In Proc.
Symp. Pure Math. (1979), AMS, pp. 415–550.

[105] SHANKS, J. Computation of the Fast Walsh-Fourier Transform. IEEE Transactions
on Computers C-18 (May 1969), 459–459.

[106] SNEDECOR, G. W., AND COCHRAN, W. G. Statistical Methods, 8 ed. Iowa
State University Press, 1989.

[107] STONE, M. H. The theory of representation for boolean algebras. Transactions
of the American Mathematical Society 40, 1 (July 1936), 37–111.

[108] VAN OORSCHOT, P., AND WIENER, M. Parallel collision search with cryptanalytic
applications. Journal of Cryptology 12, 1 (1999), 1–28.

[109] WAGNER, D. A slide attack on SHA-1, 2001. Unpublished manuscript and
personal communication. 04/06/01.

[110] WAGNER, D. A generalized birthday problem. In Advances in Cryptology–
CRYPTO 2002 (2002), vol. 2442 of Lecture Notes in Computer Science,
Springer-Verlag, pp. 288–303.

[111] WANG, X., LAI, X., FENG, D., CHEN, H., AND YU, X. Cryptanalysis of the
hash functions MD4 and RIPEMD. In Advances in Cryptology–EUROCRYPT
2005 (2005), vol. 3494 of Lecture Notes in Computer Science, Springer-Verlag,
pp. 1–18.

[112] WANG, X., YIN, Y., AND YU, H. Finding collisions in the full SHA-1. In
Advances in Cryptology–CRYPTO 2005 (2005), vol. 3621 of Lecture Notes in
Computer Science, Springer-Verlag, pp. 17–36.

[113] WANG, X., AND YU, H. How to break MD5 and other hash functions. In
Advances in Cryptology–EUROCRYPT 2005 (2005), vol. 3494 of Lecture Notes
in Computer Science, Springer-Verlag, pp. 19–35.

[114] WANG, X., YU, H., AND YIN, Y. L. Efficient collision search attacks on SHA-0.
In Advances in Cryptology–CRYPTO 2005 (2005), vol. 3621 of Lecture Notes
in Computer Science, Springer-Verlag, pp. 1–16.

[115] WEGENER, I. The complexity of Boolean functions. Wiley, Teubner, 1987.
Wiley-Teubner series in Computer Science.

[116] WINTERNITZ, R. A secure one-way hash function built from DES. In Proc.
IEEE Symposium on Information Security and Privacy (1984), IEEE Press,
pp. 88–90.

[117] YLONEN, R., AND LONVICK, C. The secure shell (SSH) authentication protocol,
2006. Internet Engineering Task Force RFC 4252.

[118] YLONEN, R., AND LONVICK, C. The secure shell (SSH) connection protocol,
2006. Internet Engineering Task Force RFC 4254.

[119] YLONEN, R., AND LONVICK, C. The secure shell (SSH) protocol architecture,
2006. Internet Engineering Task Force RFC 4251.

[120] YLONEN, R., AND LONVICK, C. The secure shell (SSH) transport layer protocol,
2006. Internet Engineering Task Force RFC 4253.

[121] ZHEGALKIN, I. I. On the technique of calculating propositions in symbolic
logic”. Matematicheskii Sbornik, 43 (1927), 9–28. In Russian.