Джон Ке́лси () — американский специалист по криптографии и компьютерной безопасности, дизайнер и соавтор нескольких алгоритмов шифрования. Является одним из авторов алгоритма Ярроу.
Биография На данный момент Джон Келси работает в области криптографии уже около 17 лет, начиная с 1994 года. За это время он успел поучаствовать во множестве исследований. Написал большое число статей, работал консультантом, помогал писать стандарты, создавал и делал рецензии на текущие коды программ. С другой стороны принимал участие в разнообразных конференциях, делал обзоры статей и участвовал в программистских комитетах. В настоящее время является дизайнером целого ряда алгоритмов и протоколов, некоторые из которых были взломаны, другие — успешно продолжают оставаться не взломанными до сих пор.
Главный интерес Джона Келси концентрируется вокруг использования криптографии и компьютерной безопасности для решения настоящих мировых проблем в данной сфере. Келси добился успехов в области генерации случайных чисел, криптоанализа и дизайна блоков шифров и хеш-функций, а также в дизайне криптографических протоколов и электронного голосования.
Интересно, что Джон Келси никогда не учился криптографии в школе, исключая несколько недель изучения RSA в алгоритмах класса. Он не окончил школу, вместо этого был поглощен криптографией. Правда, до начала написания книг, многочисленных статей и непосредственного участия в проектах ещё было далеко.
Свою карьеру в области криптографии Джон Келси начал в Counterpane Systems, Bruce Schneier’s company, крипто-консалтинговой компании. Позже Келси работал консультантом на Certicom. Сейчас Джон работает в NIST с 2003 года. Занимается развитием области генерации случайных чисел, электронного голосования и стандартов для хеш-функций.
Библиография
Рецензированные публикации 1. Praveen Gauravaram, John Kelsey, Lars R. Knudsen, Søren S. Thomsen: "On hash functions using checksums, " to appear, International Journal of Information Security.
2. John Kelsey , Andrew Regenscheid , Tal Moran, and David Chaum: «Attacking Paper-Based E2E Voting Systems», to appear, Best of WOTE, 2009.
В этой статье разрабатываются методы построения электронного голосования и предупреждения нападения на систему голосования. Авторы статьи также демонстрируют различные вариации нападения на сервер голосования, которые позволят изменить результат голосования без обнаружения криптоаналитика в некоторых случаях. Кроме того, рассматриваются некоторые общие виды атак на серверные системы голосования.
3. Elena Andreeva, Charles Bouillaguet, Orr Dunkelman, and John Kelsey: «Herding, Second Preimage and Trojan Message Attacks Beyond Merkle-Damgaard» SAC 2009.
Данная статья представляет новые методы атак для анализа структуры хеш-функций, которые не основаны на классической системе Меркл—Дамгард. Статья явно показывает herding-атаки для конкатенации хешей и некоторых хеш-функций, которые обрабатывают каждый блок сообщения несколько раз. Используя этот метод, демонстрируется вторая атака прообраза (общепризнано «hash-twice»), которая обрабатывает две конкатенирующие копии сообщения. Далее рассматривается, как применима herding-атака на дерево хешей. Наконец, представляется новый вид атаки — троян-сообщение атака, что позволяет производить вторичные прообразы неизвестных сообщений (из малоизвестных мест), когда они добавляются с фиксированным суффиксом. Ключевые слова: herding-атака, вторичная атака прообраза, троян-сообщение атака, Zipper хеш, конкатенирующий(каскадный) хеш, хеш-дерево.
4. Praveen Garuvarum, John Kelsey: «Linear-XOR and Additive Checksums Don’t Protect Damgaard-Merkle Hashes from Generic Attacks.» CT-RSA 2008: 36-51.
5. Elena Andreeva, Charles Bouillaguet, Pierre-Alain Fouque, Jonathan J. Hoch, John Kelsey, Adi Shamir, Sébastien Zimmer: «Second Preimage Attacks on Dithered Hash Functions». EUROCRYPT 2008: 270—288.http://www.schneier.com/paper-preimages.pdf
В этой статье корректируются результаты Dean [Dea99] для обеспечения вторичного прообраза атаки на всех n-битовых итерирующих хеш-функциях с Меркл—Дамгард усилением и n-битовых промежуточных состояний, разрешающих второе сообщение. Также рассматриваются более доступные методы поиска мультколлизий, чем метод Joux [Jou04]. Оба этих результаты базируются на расширяемых сообщениях — моделей для производства сообщений различной длины, которые все сталкиваются на промежуточном хеш-результате сразу после процесса отправки сообщения. Авторы статьи реализуют алгоритм для поиска расширяемых сообщений для любой n-битной хеш-функции, построенной с помощью структуры Меркла—Дамгарда, который требует только малый результат работы на одиночном столкновении в хеш-функции.
6. John Kelsey, Tadayoshi Kohno: «Herding Hash Functions and the Nostradamus Attack». EUROCRYPT 2006: 183—200.
Статья рассказывает о разработке новых общих долгосрочных сообщений второго нападения прообраза, основанного на сочетании методов во второй атаке прообраза Dean и Kelsey and Schneier с herding-атаки Келси и Коно. В статье демонстрируется, что эти общие атаки применимы к хеш-функций, используя структуры Меркла—Дамгарда, только с чуть более большей работой, чем ранее известные атаки. Они позволяют обеспечивать чрезвычайно больший контроль над содержанием найденного второго прообраза. Кроме того, доказывается, что новая атака относится к нескольким хеш-функции, конструкция которых не уязвима для ранее известных атак, включая сглаживание хеш-предложение Rivest, Shoup’s UOWHF и ROX хеш-структуру. Авторы анализируют свойства сглаживания последовательности, а также разрабатывают компромисс временной памяти, который позволяет применить второе нападение прообразом для широкого круга dithering-последовательностей, в том числе последовательностей, которые намного сильнее, чем в предложениях Rivest. Наконец, презентуется существование второй атаки прообраза, и применение новой атаки для большей эффективности на нескольких целевых сообщениях, учитывая совокупность многих сообщений. Ключевые слова: Криптоанализ, хеш-функция, dithering.
7. John Kelsey, Stefan Lucks: «Collisions and Near-Collisions for Reduced-Round Tiger». FSE 2006: 111—125.
Статья описывает collision-finding атаку на 16 раундах Tiger хеш-функции, требующей времени около 2^44 функции сжатия вызовов. Ещё одно нападение генерирует pseudo-near столкновений, но в течение 20 раундов Tiger с работой меньше, чем 2^48 функция сжатия вызовов. Так как Tiger, только 24 раундов, эти атаки могут вызвать несколько вопросов о безопасности Tiger. При разработке этих атак, адаптируются идеи сообщения модификации атаки и нейтрального бита, разработанных с помощью анализа MD4 хеш-семьи, совершенно различных дизайнов хеш-функций. Ключевые слова: Tiger, хеш-функция, столкновения, атака.
8. John Kelsey, Bruce Schneier: «Second Preimages on n-Bit Hash Functions for Much Less than 2n Work». EUROCRYPT 2005: 474—490.
9. Niels Ferguson, Doug Whiting, Bruce Schneier, John Kelsey, Stefan Lucks, Tadayoshi Kohno: «Helix: Fast Encryption and Authentication in a Single Cryptographic Primitive». FSE 2003: 330—346 2002.
Helix представляет собой высокоскоростной потоковый шифр со встроенной функциональностью MAC. На процессоре Pentium II он примерно в два раза быстрее Rijndael или Twofish, и сравним по скорости с RC4. Накладные расходы на шифрование, аутентификацию сообщения низкие, что делает его пригодным для небольших сообщений. Он эффективен как и в аппаратном так и в программном обеспечении, и с некоторыми предварительными результатами может эффективно менять ключи для каждого сообщения без дополнительных затрат. Ключевые слова: потоковый шифр, MAC, аутентификация, шифрование.
10. John Kelsey: «Compression and Information Leakage of Plaintext». FSE 2002: 263—276.
11. Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Michael Stay, David Wagner, Doug Whiting: Improved Cryptanalysis of Rijndael. FSE 2000: 213—230.
12. John Kelsey, Tadayoshi Kohno, Bruce Schneier, «Amplified Boomerang Attacks Against Reduced-Round MARS and Serpent». FSE 2000: 75-93.
В данной статье вводится новая криптоаналитическая методика, основанная на бумеранге Вагнера и внешних, внутренних атаках. Сначала описывается новая атака в терминах исходной атаки бумеранга, а затем демонстрируется её использование на ядре MARS и Serpent. Атака прерывается на одиннадцатом раунде на ядре MARS с 2^65 выбранными открытыми текстами, 2^70 памяти, и 2^229 частичных расшифровок. Атака на Serpent продолжалась в течение восьми раундов с 2^114 выбранными открытыми текстами, 2^119 памяти, и 2^179 частичными расшифровками.
13. John Kelsey, Bruce Schneier, David Wagner, Chris Hall: «Side Channel Cryptanalysis of Product Ciphers». Journal of Computer Security 8(2/3): (2000) 1999.
Опираясь на работы Кохера, в статье вводится понятие стороннего канала криптоанализа: криптоанализ, использующий реализацию данных. Обсуждаются понятие атаки по стороннему каналу и уязвимости их использования, демонстрируются атаки по стороннему каналу против трех шифров — временная атака против IDEA, processor-flag атака против RC5, и Hamming weight атака против DES. Затем обобщаются исследования других криптосистем.
14. John Kelsey, Bruce Schneier, David Wagner: «Mod n Cryptanalysis, with Applications Against RC5P and M6». Fast Software Encryption 1999: 139—155. В данной статье вводится понятие «mod n криптоанализ», форма разделения атаки, которая эффективна против шифров, которые основаны на модульном дополнении и бите вращения для их безопасности. Также демонстрируется эта атака с mod 3 атакой против RC5P, RC5 вариант, использующий ещё XOR. Авторы показывают, что и mod 5 и mod 257 атаки на M6 — шифр, предложенный в стандартной FireWire. Ожидается, что mod n криптоанализа может быть применима ко многим другим шифрам и, что общая атака распространяется для других значений n.
15. John Kelsey, Bruce Schneier: «Minimizing Bandwidth for Remote Access to Cryptographically Protected Audit Logs», Recent Advances in Intrusion Detection 1999.
16. John Kelsey, Bruce Schneier: «Key-Schedule Cryptanalysis of DEAL» Selected Areas in Cryptography 1999: 118—134.
17.
18. Bruce Schneier, John Kelsey: «Secure Audit Logs to Support Computer Forensics.» ACM Trans. Inf. Syst. Secur. 2(2): 159—176 (1999).
19. John Kelsey, Bruce Schneier: «The Street Performer Protocol and Digital Copyrights.» First Monday 4(6): (1999).
20. John Kelsey, Bruce Schneier. «Authenticating secure tokens using slow memory access (extended abstract)». In USENIX Workshop on Smart Card Technology, pages 101—106. USENIX Press, 1999.
21. John Kelsey, Bruce Schneier: «Secure Authentication with Multiple Parallel Keys.» CARDIS 1998: 150—156.
22. Chris Hall, David Wagner, John Kelsey, Bruce Schneier: «Building PRFs from PRPs.» CRYPTO 1998: 370—389.
23. John Kelsey, Bruce Schneier, David Wagner, Chris Hall: «Side Channel Cryptanalysis of Product Ciphers.» ESORICS 1998: 97-110.
24.
25. Don Coppersmith, David Wagner, Bruce Schneier, John Kelsey: Cryptanalysis of TWOPRIME. Fast Software Encryption1998: 32-48.
26. Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall: "On the Twofish Key Schedule, " Selected Areas in Cryptography 1998.
27. David Wagner, Leone Simpson, Ed Dawson, John Kelsey, William Millan, Bruce Schneier: «Cryptanalysis of ORYX.» Selected Areas in Cryptography 1998: 296—305.
28. Bruce Schneier, John Kelsey: «Cryptographic Support for Secure Logs on Untrusted Machines», Proceedings of the Seventh USENIX Security Symposium, 1998.
29. Chris Hall, John Kelsey, Vincent Rijmen, Bruce Schneier, David Wagner: «Cryptanalysis of SPEED,» Selected Areas in Cryptography 1998: 319—338.
30. John Kelsey, Bruce Schneier: "Conditional Purchase Orders, " ACM Conference on Computer and Communications Security 1997: 117—124.
31. David Wagner, Bruce Schneier, John Kelsey: «Cryptanalysis of the Cellular Encryption Algorithm», CRYPTO 1997: 526—537.