Prof. Golic je avtor stevilnih clankov iz kriptografije (spodaj sem jih prepisal nekaj z diska, ki vsebuje vse clanke s Crypto in Eurocrypt conferenc od 1981-1997, ki bo kmalu (upam!) na voljo preko interneta v MK). Na koncu pa sem pripel se en clanek iz decembrskega Crypto-grama: European Cellular Encryption Algorithms, kjer naletimo na Golicevo ime v povezavi z rabijanjem GSM/A5-1 algoritma. ------------------------------------------------------------------------------- Golic, J. D. Eurocrypt '90, A noisy clock-controlled shift register cryptanalysis concept based on sequence comparison approach, Golic, J. D. and Mihaljevic, M. J. Eurocrypt '91, The number of output sequences of a binary sequence generator, Golic, J. D. Eurocrypt '91, A comparison of cryptoanalytic principles based on iterative error-correction, Mihaljevic, M. J. and Golic, J. D. Eurocrypt '92, Correlation via linear sequential circuit approximation of combiners with memory, Golic, J. D. Eurocrypt '92, Convergence of a Bayesian iterative error-correction procedure on a noisy shift register sequence, Mihaljevic, M. J. and Golic, J. D. Eurocrypt '92, A generalized correlation attack with a probabilistic constrained edit distance, Golic, J. D. and Petrovic, S. V. Eurocrypt '94, Embedding and probabilistic correlation attacks on clock-controlled shift registers, Golic, J. D. and O'Connor, L. Eurocrypt '95, Towards fast correlation attacks on irregularly clocked shift registers, Golic, J. D. Eurocrypt '96, Fast low order approximation of cryptographic functions, Golic, J. D. Eurocrypt '97, Linear Statistical Weakness of Alleged RC4 Keystream Generator, Golic, J. D. Eurocrypt '97, Cryptanalysis of Alleged A5 Stream Cipher, Golic, J. D. Crypto '97, Edit Distance Correlation Attack on the Alternating Step Generator, Golic, J. D. and Menicocci, R. ------------------------------------------------------------------------------- CRYPTO-GRAM December 15, 1999 by Bruce Schneier Founder and CTO Counterpane Internet Security, Inc. schneier@counterpane.com http://www.counterpane.com A free monthly newsletter providing summaries, analyses, insights, and commentaries on computer security and cryptography. Back issues are available at http://www.counterpane.com. To subscribe or unsubscribe, see below. Copyright (c) 1999 by Bruce Schneier ** *** ***** ******* *********** ************* In this issue: "Security Is Not a Product; It's a Process" Sarah Flannery's Public-Key Algorithm ECHELON Technology Counterpane -- Featured Research News New U.S. Crypto Export Regulations -- Draft Counterpane Internet Security News The Doghouse: Egg Fast Software Encryption 2000 Comments from Readers European Cellular Encryption Algorithms ** *** ***** ******* *********** ************* European Cellular Encryption Algorithms There's been a lot of bad information about what kinds of encryption are out there, what's been broken, and how bad the situation really is. Here's a summary of what's really going on. GSM is the world's most widely used mobile telephony system (51% market share of all cellular phones, both analog and digital), with over 215 million subscribers in America, Europe, Asia, Africa, and Australia. In the US, GSM is employed in the "Digital PCS" networks of such telecommunications giants as Pacific Bell, Bell South, and Omnipoint. There are four cryptographic algorithms in the GSM standard, although not all the algorithms are necessarily implemented in very GSM system. They are: A3, the authentication algorithm to prevent phone cloning A5/1, the stronger of the two voice-encryption algorithms A5/2, the weaker of the two voice-encryption algorithms A8, the voice-privacy key-generation algorithm (Remember, these voice-encryption algorithms only encrypt voice between the cellphone and the base station. It does not encrypt voice within the phone network. It does not encrypt end to end. It only encrypts the over-the-air portion of the transmission.) These algorithms were developed in secret, and were never published. "Marc Briceno" (with the Smartcard Developer Association) reverse-engineered the algorithms, and then Ian Goldberg and David Wagner at U.C. Berkeley cryptanalyzed them. Most GSM providers use an algorithm called COMP128 for both A3 and A8. This algorithm is cryptographically weak, and it is not difficult to break the algorithm and clone GSM digital phones. The attack takes just 2^19 queries to the GSM smart-card chip, which takes roughly 8 hours over the air. This attack can be performed on as many simultaneous phones in radio range as your rogue base station has channels. The Berkeley group published their COMP128 analysis in April 1998. They also demonstrated that all A8 implementations they looked at, including the few that did not use COMP128, were deliberately weakened. The algorithm takes a 64-bit key, but ten key bits were set to zero. This means that the keys that secure the voice-privacy algorithms are weaker than the documentation indicates. They published and analyzed A5/2 in August 1999. As the weaker of the two voice-encryption algorithms, it proved to be very weak. It can be broken in real-time without any trouble; the work factor is around 2^16. Supposedly this algorithm was developed with "help" from the NSA, so these weaknesses are not surprising. The Berkeley group published A5/1 in May 1999. The first attack was by Jovan Golic, which gives the algorithm a work factor of 2^40. This means that it can be broken in nearly real-time using specialized hardware. Currently the best attack is by Biryukov and Shamir. Earlier this month they showed that they can find the A5/1 key in less than a second on a single PC with 128 MB RAM and two 73 GB hard disks, by analyzing the output of the A5/1 algorithm in the first two minutes of the conversation. All GSM providers and equipment vendors are part of the GSM Association. The algorithms were designed and analyzed by the secretive "SAGE" group (which is really part of ETSI). We don't know who the people are or what their resumes look like. What we do know is that the SAGE security analyses of the ciphers are online at ETSI's homepage in PDF format. Read it; it's entertaining. A5/1 is purported to be a modified French naval cipher. This is mentioned in the leaked Racal document. What's most interesting about these algorithms is how robustly lousy they are. Both voice-encryption algorithms are flawed, but not obviously. The attacks on both A5/1 and A5/2 make use of subtle structures of the algorithm, and result in the ability to decrypt voice traffic in real time on average computer equipment. At the same time, the output of the A8 algorithm that provides key material for A5/1 and A5/2 has been artificially weakened by setting ten key bits to zero. And also, the COMP128 algorithm that provides the keying material that is eventually weakened and fed into the weakened algorithms is, itself, weak. And remember, this encryption only encrypts the over-the-air portion of the transmission. Any legal access required by law enforcement is unaffected; they can always get a warrant and listen at the base station. The only reason to weaken this system is for *illegal* access. Only wiretaps lacking a court authorization need over-the-air intercepts. The industry reaction to this has been predictably clueless. One GSM spokesman claimed that it is impossible to intercept GSM signals off the air, so the encryption breaks are irrelevant. Notwithstanding the fact that GSM interception equipment was once sold openly -- now it's illegal -- certainly the *phone* can receive signals off the air. Estimated cost for a high-quality interception station is well under $10K. GSM analysis: http://www.scard.org/gsm/ http://www.jya.com/crack-a5.htm GSM Association Web site: http://www.gsmworld.com News reports: http://wired.lycos.com/news/politics/0,1283,32900,00.html http://www.nytimes.com/library/tech/99/12/biztech/articles/07code.html ** *** ***** ******* *********** ************* CRYPTO-GRAM is a free monthly newsletter providing summaries, analyses, insights, and commentaries on computer security and cryptography. To subscribe, visit http://www.counterpane.com/crypto-gram.html or send a blank message to crypto-gram-subscribe@chaparraltree.com. To unsubscribe, visit http://www.counterpane.com/unsubform.html. Back issues are available on http://www.counterpane.com. Please feel free to forward CRYPTO-GRAM to colleagues and friends who will find it valuable. Permission is granted to reprint CRYPTO-GRAM, as long as it is reprinted in its entirety. CRYPTO-GRAM is written by Bruce Schneier. Schneier is founder and CTO of Counterpane Internet Security Inc., the author of "Applied Cryptography," and an inventor of the Blowfish, Twofish, and Yarrow algorithms. He served on the board of the International Association for Cryptologic Research, EPIC, and VTW. He is a frequent writer and lecturer on computer security and cryptography. Counterpane Internet Security, Inc. is a venture-funded company bringing innovative managed security solutions to the enterprise. http://www.counterpane.com/ Copyright (c) 2000 by Bruce Schneier ==============================================================================