//
//	CONCLUSIONS 
//
//	I conjecture that the most efficient way to break Blowfish is through exhaustive search of the keyspace. I encourage all cryptanalytic attacks, modifications, and improvements to the algorithm. Attacks on mini versions of Blowfish, those with a 32- or even a 16-bit block size, are also encouraged. Source code in C and test data can be provided to anyone wishing to implement the algorithm, in accordance with U.S. export laws. 
//
//	The software magazine Dr. Dobb's Journal is sponsoring $1000 contest for the best cryptanalysis of Blowfish received before April 1995. Please contact me for details. 
//
//	Blowfish is unpatented, and will remain so in all countries. The algorithm is hereby placed in the public domain, and can be freely used by anyone. 
//
//	ACKNOWLEDGEMENTS 
//
//	Much of the motivation for this algorithm, as well as the design criteria, was developed with Niels Fergusen. I would also like to thank Eli Biham, Agnes Chan, Peter Gutmann, Angel Johnston, Lars Kundsen, and Matt Robshaw for their helpful suggestions. 
//
//	REFERENCES 
//
//	1. E. Biham and A. Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, 1993. 
//
//	2. T.W. Cusick and M.C. Wood, "The REDOC-II Cryptosystem," Advances in Cryptology--CRYPTO '90 Proceedings, Springer- Verlag, 1991, pp. 545-563. 
//
//	3. J. Deamen, R. Govaerts, and J. Vandewalle, "Block Ciphers Based on Modular Arithmetic," Proceedings of the 3rd Symposium on State and Progress of Research in Cryptography, Rome, Italy, 15-16 Feb 1993, pp. 80-89. 
//
//	4. J.-H. Evertse, "Linear Structures in Blockciphers," Advances in Cryptology--EUROCRPYT '87, Springer-Verlag, 1988, pp. 249- 266. 
//
//	5. H. Feistel, "Cryptography and Computer Privacy," Scientific American, v. 228, n. 5, May 73, pp. 15-23. 
//
//	6. GOST 28147-89, "Cryptographic Protection for Data Processing Systems," "Cryptographic Transformation Algorithm," Government Standard of the U.S.S.R., Inv. No. 3583, UDC 681.325.6:006.354. (in Russian) 
//
//	7. X. Lai, J. Massey, and S. Murphy, "Markov Ciphers and Differential Cryptanalysis," Advances in Cryptology--EUROCRYPT '91 Proceedings, Springer-Verlag, 1991, pp. 17-38. 
//
//	8. J.L. Massey and X. Lai, "Device for Converting a Digital Block and the Use Thereof," International Patent PCT/CH91/00117, 16 May 1991. 
//
//	9. J.L. Massey and X. Lai, "Device for the Conversion of a Digital Block and Use of Same," U.S. Patent 5,214,703, 25 May 1993. 
//
//	10. M. Matsui, "Linear Cryptanalysis Method for DES Cipher," Advances in Cryptology--CRYPTO '93 Proceedings, Springer- Verlag, 1994, in preparation. 
//
//	11. R.C. Merkle, "Fast Software Encryption Functions," Advances in Cryptology--CRYPTO '90 Proceedings, Springer-Verlag, 1991, pp. 476-501. 
//
//	12. R.C. Merkle, "Method and Apparatus for Data Encryption," U.S. Patent 5,003,597, 26 Mar 1991. 
//
//	13. S. Miyaguchi, "The FEAL-8 Cryptosystem and Call for Attack," Advances in Cryptology--CRYPTO '89 Proceedings, Springer- Verlag, 1990, pp. 624-627. 
//
//	14. S. Miyaguchi, "Expansion of the FEAL Cipher," NTT Review, v. 2, n. 6, Nov 1990. 
//
//	15. S. Miyaguchi, "The FEAL Cipher Family," Advances in Cryptology--CRYPTO '90 Proceedings, Springer-Verlag, 1991, pp. 627-638. 
//
//	16. National Bureau of Standards, Data Encryption Standard, U.S. Department of Commerce, FIPS Publication 46, Jan 1977. 
//
//	17. National Institute of Standards and Technology, "Clipper Chip Technology," 30 Apr 1993. 
//
//	18. RSA Laboratories, Answers to Frequently Asked Questions About Today's Cryptography, Revision 2.0, RSA Data Security Inc., 5 Oct 1993. 
//
//	19. B. Schneier, "Data Guardians," MacWorld, Feb 1993, 145-151. 
//
//	20. B. Schneier, Applied Cryptography, John Wiley & Sons, New York, 1994. 
//
//	21. J.L Smith, The Design of Lucifer, A Cryptographic Device for Data Communication, RC 3326, White Plains: IBM Research. 
//
//	22. M.J. Weiner, "Efficient DES Key Search," Advances in Cryptology--CRYPTO '93 Proceedings, Springer-Verlag, in preparation. 
//
//	23. M.C. Wood, "Method of Cryptographically Transforming Electronic Digital Data from One Form to Another," U.S. Patent 5,003,596, 26 Mar 1991. 





//	from http://www.schneier.com/
//	The Blowfish Encryption Algorithm -- One Year Later
//	B. Schneier
//
//	Dr. Dobb's Journal, September 1995. 
//
//	DES is the workhorse of cryptography algorithms, and it's long past time to replace the 19-year-old standard. The recent design of a $1M machine that could recover a DES key in 3.5 hours only confirmed what everybody knew: DES's key size is far too small for today. 
//
//	The world only partly trusted DES because it survived the scrutiny of the NSA. Experts trusted DES because it was a published standard, and because it survived 20 years of intensive cryptanalysis by cryptographers around the world. Cryptography is like that: confidence in an algorithm grows as group after group tries to break it and fails. 
//
//	Candidates for a replacement are emerging, but none has taken widespread hold. Triple-DES is the conservative approach; IDEA (used in PGP) is the most promising new algorithm. And there is a bevy of unpatented also-rans: RC4 (once a trade secret of RSA Data Security, Inc. but now publicly available on the Internet), SAFER, and my own Blowfish. 
//
//	I first presented Blowfish at the Cambridge Algorithms Workshop ("Description of a New Variable-Length Key, 64-bit Block Cipher (Blowfish)," Fast Software Encryption, R. Anderson, ed., Lecture Notes in Computer Science #809, Springer-Verlag, 1994) and in Dr. Dobb's Journal (April 1994). From the start Blowfish was intended to be a completely free--unpatented, unlicensed, and uncopyrighted--alternative to DES. Since then it has been analyzed by some people and has started to see use in some systems, both public and private. This article presents new Blowfish code, as well as updates on the algorithm's security. 
//
//	Description of Blowfish
//	Blowfish is a block cipher that encrypts data in 8-byte blocks. The algorithm consists of two parts: a key-expansion part and a data-encryption part. Key expansion converts a variable-length key of at most 56 bytes (448 bits) into several subkey arrays totaling 4168 bytes. (Note: the description in this article differs slightly from the one in the April 1994 issue of Dr. Dobb's Journal; there were typos in steps (5) and (6) of the subkey generation algorithm.) 
//
//	Blowfish has 16 rounds. Each round consists of a key-dependent permutation, and a key- and data-dependent substitution. All operations are XORs and additions on 32-bit words. The only additional operations are four indexed array data lookups per round. 
//
//	Subkeys: 
//
//	Blowfish uses a large number of subkeys. These keys must be precomputed before any data encryption or decryption. The P-array consists of 18 32-bit subkeys: P1, P2,..., P18. There are also four 32-bit S-boxes with 256 entries each: S1,0, S1,1,..., S1,255; S2,0, S2,1,..,, S2,255; S3,0, S3,1,..., S3,255; S4,0, S4,1,..,, S4,255. 
//
//	Encryption and Decryption: 
//
//	Blowfish has 16 rounds. The input is a 64-bit data element, x. Divide x into two 32-bit halves: xL, xR. Then, for i = 1 to 16: 
//
//	xL = xL XOR Pi
//	xR = F(xL) XOR xR
//	Swap xL and xR 
//
//	After the sixteenth round, swap xL and xR again to undo the last swap. Then, xR = xR XOR P17 and xL = xL XOR P18. Finally, recombine xL and xR to get the ciphertext. 
//
//	Function F looks like this: Divide xL into four eight-bit quarters: a, b, c, and d. Then, F(xL) = ((S1,a + S2,b mod 232) XOR S3,c) + S4,d mod 232. 
//
//	Decryption is exactly the same as encryption, except that P1, P2,..., P18 are used in the reverse order. 
//
//	Generating the Subkeys: 
//
//	The subkeys are calculated using the Blowfish algorithm: 
//
//	1. Initialize first the P-array and then the four S-boxes, in order, with a fixed string. This string consists of the hexadecimal digits of pi (less the initial 3): P1 = 0x243f6a88, P2 = 0x85a308d3, P3 = 0x13198a2e, P4 = 0x03707344, etc. 
//
//	2. XOR P1 with the first 32 bits of the key, XOR P2 with the second 32-bits of the key, and so on for all bits of the key (possibly up to P14). Repeatedly cycle through the key bits until the entire P-array has been XORed with key bits. (For every short key, there is at least one equivalent longer key; for example, if A is a 64-bit key, then AA, AAA, etc., are equivalent keys.) 
//
//	3. Encrypt the all-zero string with the Blowfish algorithm, using the subkeys described in steps (1) and (2). 
//
//	4. Replace P1 and P2 with the output of step (3). 
//
//	5. Encrypt the output of step (3) using the Blowfish algorithm with the modified subkeys. 
//
//	6. Replace P3 and P4 with the output of step (5). 
//
//	7. Continue the process, replacing all entries of the P array, and then all four S-boxes in order, with the output of the continuously changing Blowfish algorithm. 
//
//	In total, 521 iterations are required to generate all required subkeys. Applications can store the subkeys rather than execute this derivation process multiple times. 
//
//	C Code:
//	C code for Blowfish starts on page xx. This is improved and corrected code; the code in the April 1994 issue had some bugs and was less efficient than this code. The code is also available electronically; see "Availability," page xx. 
//
//	Cryptanalysis of Blowfish
//	When I first presented Blowfish last year, Dr. Dobb's Journal sponsored a cryptanalysis contest. There were five submissions in total, and I am pleased to present the most interesting results here. 
//
//	John Kelsey developed an attack that could break 3-round Blowfish, but was unable to extend it. This attack exploits the F function and the fact that addition mod 232 and XOR do not commute. Vikramjit Singh Chhabra looked at ways of efficiently implementing a brute-force keysearch machine. 
//
//	Serge Vaudenay examined a simplified variant of Blowfish, with the S-boxes known and not key-dependent. For this variant, a differential attack can recover the P-array with 28r+1 chosen plaintexts (r is the number of rounds). This attack is impossible for 8-round Blowfish and higher, since more plaintext is required than can possibly be generated with a 64-bit block cipher. 
//
//	For certain weak keys that generate weak S-boxes (the odds of getting them randomly are 1 in 214), the same attack requires only 24r+1 chosen plaintexts to recover the P-array (again, assuming the S-boxes are known). With unknown S-boxes, this attack can detect whether a weak key is being used, but cannot determine what it is (neither the S-boxes, the P-array, nor the key itself). This attack only works against reduced-round variants; it is completely ineffective against 16-round Blowfish. 
//
//	Even so, the discovery of weak keys in Blowfish is significant. A weak key is one for which two entries for a given S-box are identical. There is no way to check for weak keys before doing the key expansion. If you are worried, you have to do the key expansion and check for identical S-box entries after you generate a Blowfish key. I don't think it's necessary, though. 
//
//	Conclusion
//	No one has come close to developing an attack that breaks Blowfish. Even so, more cryptanalysis is required before pronouncing the algorithm secure. I invite others to continue analyzing the algorithm.