Но сначала, когда я говорю «Сильная криптография», какого черта я имею в виду?
Сильная криптография или криптографически стойкие являются общими терминами применяемых криптографических систем или компонентов, которые считаются высоко устойчивыми к криптоанализу .
http://en.wikipedia.org/wiki/Strong_cryptography
Таким образом, Сильная Криптография не является какой-то эзотерической концепцией, к которой вы не имеете никакого отношения: Сильная Криптография — это просто набор определений и алгоритмов, которые были рассмотрены экспертами , секретными правительственными агентствами и сторонними организациями и которые трудно сломать.
Я неоднократно замечал, что разработчик «изобретает» схему криптографии для определенной цели. Вот в чем дело, криптографии тысячи лет. Если вы когда-нибудь «изобрели» свой собственный способ «шифрования» данных, скорее всего, вы просто заново изобрели то, что было обнаружено тысячи лет назад. Если вы хотите избежать ошибок, которые WEP совершил с беспроводной связью, Microsoft сделала с XBox или Sony сделала с PS3, эта серия блогов поможет вам избежать смущения и даст вам что-то впечатляющее на следующей коктейльной вечеринке.
Наконец, я просто хотел упомянуть, что это действительно очень личная тема, с которой у меня долгая история. Я обнаружил, что моей первой потребностью в криптографии было раздача заметок моим друзьям, когда мы играли в «Шпионов» по соседству, и нам нужно было обезопасить расположение наших секретных фортов. К сожалению, мой однобуквенный заменительный шифр, должно быть, был взломан каким-то одаренным парнем, поскольку наш дом на дереве был разрушен этим летом … После прочтения Секретного Кодекса Элвина мы создали 2-3 комплекта колес Цезаря и больше никогда не теряли секретный форт!
Ниже мы рассмотрим один из самых полезных примитивов Strong Cryptography: функцию Hash. Эти маленькие звери удивительны и имеют множество применений!
Итак, что такое хэш-функция? Рад, что вы спросили, давайте процитируем неослабную Википедию:
Хеш-функция — это любая четко определенная процедура или математическая функция, которая преобразует большой объем данных, возможно, переменного размера, в небольшой элемент данных, обычно одно целое число, которое может служить индексом для массива (см. Ассоциативный массив). Значения, возвращаемые хеш-функцией, называются хеш-значениями, хеш-кодами, хеш-суммами, контрольными суммами или просто хешами.http://en.wikipedia.org/wiki/Hash_function
Вздох, у Википедии были хорошие удобные определения для простых людей, так как это не так, позвольте мне дать мое собственное определение:
(Очень плохая) хеш-функция может быть такой простой, как «делить все на два, пока не останется одна цифра, округляя вверх по ходу». Мы могли бы эту функцию ƒ (ƒ означает ƒ отсутствие хеш-функции), и поэтому ƒ (48) = 6 или ƒ (451) = 8.
Простой способ использовать эту функцию — это защитить сайт. Когда пользователь создает учетную запись, он выбирает номер в качестве пароля (p). В процессе создания аккаунта мы вычисляем новое число (c = ƒ (p)) и сохраняем его для пользователя. Мы заканчиваем с (c) числом, 0-9, в базе данных для каждого пользователя.
Чтобы проверить предоставленный пароль (пароли) к базе данных, мы просто оцениваем (c == ƒ (s)).
Эта хеш-функция really на самом деле не очень полезна в реальном мире, так как наше пространство ключей имеет только 9 возможностей, оно ужасно масштабируется, и тривиально перепроектировать, но если мы заменим отказную функцию fail на что-то лучшее, мы в итоге получим безопасная система!
Технические свойства идеального алгоритма хеширования
- Он должен представлять собой истинную функцию многие-к-одному . Он должен принимать входные данные и создавать идентификационные данные, которые могут быть воспроизведены точно каждый раз. Для каждого открытого текста существует ровно одно хеш-значение. Для каждого хеш-значения существует бесконечное количество открытых текстов.
- Входной открытый текст может быть любой длины. Да, но смотри следующий пункт:
- Выходное значение хеша всегда имеет одинаковый размер, что означает его фиксированную длину. Таким образом, если вы дадите алгоритму открытый текст размером 50 байт или 765 кбайт, длина значения хеша (выходной) будет, как говорится, 16 байт. Точная длина вывода зависит от конструкции алгоритма.
- Всегда выдают одно и то же значение хеш-функции (вывод) для одного и того же открытого текста (ввод). Поэтому, если вы хешируете цитату: «Я придерживаюсь принципа, что государственный долг является публичным проклятием», вы должны получить значение vjPWnnLiB0BLrqUuJjtpEM5KClg = каждый раз. Это называется идентификацией, дактилоскопией или хэшированием открытого текста.
- Небольшое изменение в открытом тексте приведет к значительному изменению значения хеш-функции. Поэтому, если вы измените цитату Мэдисона на « Я исхожу из принципа, что государственный долг не является публичным проклятием», хеш-значение теперь равно: g + 8o7vlQAGjvlst + XsOEwIzF0Qc = .
- Постоянный и «односторонний», означающий, что значение hashValue не может быть преобразовано в открытый текст.
- Учитывая конкретное значение hashValue, чрезвычайно трудно найти открытый текст, который будет генерировать желаемое значение hashValue. Эти последние две точки работают вместе … По сути, наша функция far далека от идеальной. Допустим, у вас есть (р = 5). Очень легко рассчитать входные данные, которые будут производить (5 = ƒ (s)). Вы можете использовать любой из (s = {10, 20, 40}). Идеальная функция должна сделать это чрезвычайно сложно !!!
SHA1, стандартный алгоритм хеширования
SHA-1 (Secure Hash Algorithm — 1) — это довольно сложный алгоритм хеширования, который, как известно, на момент написания этой статьи был безопасным для большинства приложений (параноик должен использовать SHA-256 или SHA-512). Мы можем предоставить любой открытый текст в SHA-1 и получить в ответ согласованное 20-байтовое значение хеша. Вот как это сделать — Ruby:
|
01
02
03
04
05
06
07
08
09
10
11
|
exabrial@arclight:~$ irb>> require 'base64'=> true>> require 'openssl'=> true>> shaBytes = Digest::SHA1.digest('Give me liberty, or give me death!')=> "\367\241\266`30 \2656\214G343\266\276\204\225cB\370\r">> puts Base64.encode64(shaBytes)96G2YBggtTaMRxwztr6ElWNC+A0==> nil>> exit |
Вы можете использовать онлайн-калькулятор хешей, чтобы проверить, правильно ли хеширована цитата Патрика Генри. Давай, я подожду …
|
1
|
SHA-1(Base64) : 96G2YBggtTaMRxwztr6ElWNC+A0= |
Если мы слегка изменим текст, скажем: « Дайте мне свободу или позвольте мне съесть пирог! «Мы получим совершенно другой результат:
|
1
|
SHA-1(Base64) : M2vPzwTPc7ALM+OkiGAwCkS1DY4= |
На самом деле, просто изменив случай с первым персонажем « дай мне свободу или дай мне смерть! «Будет производить совершенно другое hashValue:
|
1
|
SHA-1(Base64) : g1UFdWJfXWfkIVz42uLLxrJv58g= |
Ввод алгоритма хеширования действительно бесконечен
Помните, как мы говорили, что ввод хеш-функции может быть бесконечным? Как насчет всего текста Декларации независимости (12kb)? Если вы загрузите файл в онлайн-калькулятор, который мы использовали, результат будет 20 байтов:
|
1
|
SHA-1(Base64): mGnTR5dnrXrMqEMVoLKCMzWEHjU= |
Вот быстрая Java-программа, которая поможет выполнить те же вычисления:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
|
import java.io.InputStreamReader;import java.nio.CharBuffer;import java.security.MessageDigest;import org.apache.commons.codec.binary.Base64;public class SHA1Hasher { public static void main(String[] args) throws Exception { MessageDigest md = MessageDigest.getInstance("SHA1"); InputStreamReader insr = new InputStreamReader(SHA1Hasher.class.getResourceAsStream("/usdeclar.txt")); CharBuffer charBuff = CharBuffer.allocate(16000); String plainText; byte[] hashBytes; String hashValue; insr.read(charBuff); plainText = charBuff.flip().toString(); hashBytes = md.digest(plainText.getBytes()); hashValue = Base64.encodeBase64String(hashBytes); System.out.println("SHA-1(Base64): " + hashValue); }} |
Реальное использование хеш-алгоритмов, сценарий 1: безопасное хранение паролей учетных записей в базе данных
Вам было поручено создать сайт для американского колониального сопротивления. Британцев предостаточно, и они случайным образом проверяют базы данных каждого на предмет подозрительной активности. Отцы-основатели имеют неудачную привычку выбирать патриотические пароли типа «Я <3Америка». Как можно замаскировать пароли британских патрулей, чтобы секреты того, кто лоялен Короне, а кто революционер, держатся в секрете?
Лучше всего создать «таблицу соленых паролей», например:
| USERNAME | PASSWORD_HASH | ПОВАРЕННАЯ СОЛЬ |
|---|---|---|
| tjefferson43 | HiE0AZhRWAs6Mmd7dVqppM1WtJc = | WTg68cVxPI |
Что мы будем делать, это хранить хэш пароля, плюс некоторый случайный текст, называемый солью (чтобы добавить энтропию к паролю пользователя). Итак, оригинальный пароль Томаса Джефферсона: I <3America теперь становится I <3AmericaWTg68cVxPI и постоянно хешируется в: HiE0AZhRWAs6Mmd7dVqppM1WtJc =.
Итак, как вы обрабатываете логин, теперь, когда нет открытого текста? Вы выполняете тот же расчет: возьмите имя пользователя из формы входа и найдите соль. Затем возьмите незашифрованный пароль из формы входа и объедините соль из базы данных, чтобы преобразовать исходную строку. Хешируйте эту строку, и если она совпадает с хешем базы данных, вы знаете, что был указан правильный пароль! Оригинальный патриотический пароль Джефферсона полностью замаскирован, поэтому эти противные Тори никогда не узнают его истинной верности! Yarr!
Но что если другой патриот (Пол Ревер) выберет тот же пароль, но его поймают англичане? Разве британские регулярные власти не могли бы просто сделать вывод, что любой, имеющий такой же хэш пароля, тоже патриот (и его повесят)?
Поскольку мы добавили соль (энтропию) в открытый текстовый пароль, мы никогда не будем иметь одинаковый хэш дважды в нашей базе данных. Допустим, Пол Ревер создает учетную запись с тем же паролем: I <3America , но мы следовали обязательной практике использования SecureRandom для создания новой соли:
| USERNAME | PASSWORD_HASH | ПОВАРЕННАЯ СОЛЬ |
|---|---|---|
| tjefferson43 | HiE0AZhRWAs6Mmd7dVqppM1WtJc = | WTg68cVxPI |
| paulrevere1776 | aktJ / 0cn69Y41vssNfZDHY1CsdE = | sWVUaTGa6e |
Таким образом, пароль Пола Ревера I <3America становится I <3AmericasWVUaTGa6e , который хэшируется в: aktJ / 0cn69Y41vssNfZDHY1CsdE = и сохраняется. Позже, когда Пола Ревера поймали и обнаружили, что он патриот, секрет Джефферсона защищен от соления и перемешивания.
Подводя итог преимуществам:
- Нарушение базы данных означает, что ваши учетные записи все еще защищены.
- Невозможно сказать, если два человека имеют одинаковый пароль.
- Нет ограничений на длину пароля пользователя.
- Ваш столбец базы данных может быть фиксированной длины вместо varchar.
- SHA1 был создан людьми, которые умнее вас (и меня). Вы можете сдуть свое эго и использовать свои мозги.
Да, Ной Вебстер был американским революционером: он был сотрудником ополчения Коннектикута, редактором газеты Федералист, автором американских авторских прав, среди прочего. Позже он начал писать словарь, но важная часть в том, что он был очень трудным заданием, когда дело дошло до преподавания.
Итак, скажем, Ной Вебстер нанял вас, чтобы написать программу для проверки орфографии его учеников. Поскольку он так непреклонно верил в правильное написание, важно, чтобы каждый студент получал 100%. Зная, что это немного нереально, он позволит студентам проходить тест столько раз, сколько они хотят, пока они не получат 100%. Тест состоит в том, что мистер Вебстер диктует небольшой отрывок текста классу и заставляет его правильно ввести его в вашу программу. Программа должна сказать им, правильно ли они все написали. Это позволит им выяснить правильный ответ, прежде чем сдавать окончательный ответ.
Еще одна важная часть американской истории заключалась в том, что Ной Вебстер был фанатом Руби; Вы должны написать это в Ruby. Это создает проблему, потому что студенты будут выполнять вашу программу, вы не можете просто вставить правильный ответ в вашу программу, или они могут посмотреть на исходный код.
Используя хеш, вы можете встроить хеш правильного текста в программу и сравнить входные данные учащихся с хешем.
Мистер Вебстер начинает испытание, говоря своим ученикам:
Прежде чем постоянная армия сможет править, люди должны быть разоружены; как они есть почти в каждом королевстве европы. Верховная власть в Америке не может навязывать несправедливые законы мечом; потому что весь народ вооружен и представляет собой силу, превосходящую любые группы регулярных войск, которые могут быть под любым предлогом подняты в Соединенных Штатах.
Правильный хеш: 6 + IHAAJ1i0KmoPaowU1i0xSjcO4 =
Зная, что вы знаете сейчас, вы можете закончить программу для мистера Вебстера? Оставьте свой ответ в комментариях!
Сегодня мы углубимся в некоторые темы хеширования. Также я принимаю предложения по темам в своих сообщениях … В прошлый раз это были отцы-основатели США, на этой неделе это трагедии.
В нашей последней статье мы узнали, что такое хеш-функция и как для каждого ввода существует только один соответствующий выход. Мы собираемся применить эту концепцию к двум обычным ситуациям, когда требуется конфиденциальность.
Общая ситуация № 1: ситуация в Вероне
Допустим, у вас есть Ромео, которому нужно отправить Меркуцио по электронной почте следующее сообщение: «Мне приснился сон сегодня вечером». К сожалению для Ромео, все интернет-провайдеры в Вероне принадлежат семье Монтегю (не намного лучше, чем Comcast). Ромео не возражает, если Монтекки могут прочитать его сообщение, но у него, конечно, есть проблема, что они изменят его сообщение. Как мог Ромео быть уверенным, что его сообщение было доставлено без изменения семьей Монтегю?
Ну, вы можете запустить сообщение через хеш-функцию и прикрепить к сообщению хеш. Однако Монтекки могли просто изменить сообщение и прикрепить новое хеш-значение. Чтобы обойти это, я полагаю, что Ромео мог вычислить хеш, а затем сказать Меркуцио в частном порядке, каково было значение хеша. Однако это лишило бы смысла отправлять ему электронные письма, поскольку в частном порядке он мог просто сообщить Меркуцио содержание сообщения.
Есть идеи?
Представляем новый MAC (не то, что вы думаете)
К счастью, есть простое решение: коды аутентификации сообщений или MAC. Функция MAC — это «хеш-функция с ключом», так что вы можете назвать ее двоюродным братом обычной хеш-функции. На самом деле, функции MAC и хэш-функции практически взаимозаменяемы! В последней статье мы рассмотрели свойства хэш-функции. Так что же отличает функцию MAC от хэш-функции?
- Вы должны обладать секретным ключом, чтобы получить хеш-значение.
- Функция MAC не должна показывать «подсказки» о секретном ключе, даже если злоумышленник выбирает ввод.
|
01
02
03
04
05
06
07
08
09
10
11
12
|
private static final byte[] keybytes = new byte[] { (byte) 0xfc, (byte) 0x4f, (byte) 0xbe, (byte) 0x23, (byte) 0x59, (byte) 0xf2, (byte) 0x42, (byte) 0x37, (byte) 0x4c, (byte) 0x80, (byte) 0x44, (byte) 0x31, (byte) 0x20, (byte) 0xda, (byte) 0x20, (byte) 0x0c }; public static void main(String[] args) throws Exception { Mac mac = Mac.getInstance("HMACSHA1"); Key key = new SecretKeySpec(keybytes, "HMACSHA1"); mac.init(key); byte[] hashValue = mac.doFinal("The lady doth protest too much, methinks".getBytes()); String encodedHashValue = Base64.encodeBase64String(hashValue); System.out.println(encodedHashValue); } |
Вышеупомянутая программа производит этот вывод:
|
1
|
oOUKVR5hDRh4n0H+beVO4JvMw64= |
Если вы используете другой ключ (давайте изменим последний байт на 0x0d ), вы получите совершенно другой хеш:
|
1
|
cDdJwEBm9qIni9A7QfIQ1e9G8qo= |
Так как же относиться к Ромео и Меркуцио? Сначала они встречаются наедине и создают секретный ключ. И Ромео, и Меркуцио узнают секретный ключ. Затем, когда они хотят отправить электронное письмо, они запускают сообщение через функцию MAC и создают подпись. Наконец, получатель пропускает сообщение через ту же функцию MAC, используя тот же ключ. Если вычисленная подпись совпадает с подписью в сообщении, они могут быть уверены, что сообщение не было подделано во время передачи.
MAC на самом деле просто обертка
Обратите внимание на следующую строку в приведенной выше реализации:
|
1
|
Mac mac = Mac.getInstance("HMACSHA1"); |
Как вы помните ранее, SHA1 — довольно стандартный алгоритм хеширования. Ну вот и вся история: функция MAC — это просто оболочка вокруг стандартной хеш-функции. HMAC-часть HMACSHA1 — это метод упаковки. Существуют и другие реализации MAC, такие как VMAC, но они используются реже. VMAC работает немного лучше, чем HMAC. Поскольку HMAC и VMAC являются просто оболочками, вы можете взять практически любую хеш-функцию и превратить их в ключевую хеш-функцию. Используя старших братьев SHA1, мы можем запустить ту же цитату через программу:
- HMACSHA256: POP9cefgoEC9pUaWXqQ8lBbW9CdMi1k3t7LXAGYl87s =
- HMACSHA512: ALFIpPMbphQJ7KZQHacGIFH3T2qI5AKUqaD8lDilNnjajGL29cZdp68sLeQTjDKD + cIAfZN86udfRdecGeTm0A ==
Распространенная ситуация № 2: Пересмотр хранения паролей в базе данных
Ранее мы определились со следующей структурой таблицы
| USERNAME | PASSWORD_HASH | ПОВАРЕННАЯ СОЛЬ |
|---|---|---|
| tjefferson43 | HiE0AZhRWAs6Mmd7dVqppM1WtJc = | WTg68cVxPI |
| paulrevere1776 | aktJ / 0cn69Y41vssNfZDHY1CsdE = | sWVUaTGa6e |
Добавим еще один столбец:
| USERNAME | PASSWORD_HASH | ПОВАРЕННАЯ СОЛЬ | MAC_KEY |
|---|---|---|---|
| tjefferson43 | RFu51fVI / 0y8gmPXkjo0Op9FRHU = | WTg68cVxPI | KvzpFe690vsVcW1jLqQ1vg == |
| paulrevere1776 | SmZedewg1JD7kRhndEW2cRmcyGw = | sWVUaTGa6e | FgIpIDFi9kJgXvkp44ua4Q == |
Так что мы здесь сделали? Вместо того, чтобы использовать прямую функцию sha-1 для хранения представления пароля пользователя, мы теперь используем HMACSHA1. Что это делает для вас? Немного. Лучший вопрос в том, что это делает для хакеров … Это делает их жизнь чрезвычайно трудной!
MAC защищает вас от хакеров (опять же, не то, что вы думаете)
В нашей первоначальной настройке таблицы хакер мог использовать две формы атак для взлома наших паролей. Он мог использовать радужную атаку (да, это действительно так называется… Нет, я не знаю почему) или атаку грубой силой (не путать с атакой Брюса ).
Радужная атака использует мультитерабайтную базу данных для обратного просмотра нашего алгоритма хеширования. База данных создается заранее, возможно, сотрудничающими сторонами и тысячами отдельных компьютеров, чтобы разделить рабочую нагрузку. Даже при совместных усилиях для создания полезных таблиц требуются месяцы. Однако с готовой радужной таблицей злоумышленник может просмотреть выходные данные хеш-функции, чтобы получить произвольный ввод, который выдает тот же хеш, что и реальный пароль пользователя. Хлоп! Приятно то, что использование HMACSHA1 делает это невозможным для хакера. Поскольку наш алгоритм хеширования был введен по-разному для каждого пароля пользователя, им пришлось бы совместно восстанавливать радужную таблицу для каждой отдельной записи, что на практике делает радугу очень и очень сложной!
Атака грубой силы связана с атакой радуги. Атака грубой силы пробует случайные комбинации букв и цифр или даже обычных английских слов, пока не найдет ввод, который даст правильный вывод. К сожалению, HMACSHA1 обеспечивает немного дополнительной защиты от атак методом перебора. Однако, поскольку для их работы требуются мощные вычислительные системы, они встречаются реже. Есть только два способа защиты от атак грубой силы:
- Применяйте правильные правила для паролей:
- 12 персонажей
- Нет английских слов
- как минимум 2 числа
- минимум 2 символа
- как минимум 2 заглавные буквы
- Используйте SHA-512 или SHA-256 вместо SHA-1.
Если вам понравилась эта статья, все, что я спрашиваю, если вы проголосуете за меня на DZone и HackerNews . До следующего раза, спасибо за чтение!
Ссылка: Введение в сильную криптографию — p0 , Введение в сильную криптографию — p1.0 — Хеш-функции, американские патриоты и Введение в сильную криптографию — p1.1 — Хеширование с помощью ключей, Хэш-атаки, MAC, Шекспир от нашего партнера JCG