Алгоритмы / Хэш-функция SHA-256
SHA-256 представляет собой однонаправленную функцию для создания цифровых отпечатков фиксированной длины (256 бит, 32 байт) из входных данных размером до 2,31 эксабайт (2⁶⁴ бит) и является частным случаем алгоритма из семейства криптографических алгоритмов SHA-2 (Secure Hash Algorithm Version 2) опубликованным АНБ США в 2002 году.
Хеш-функции семейства SHA-2 построены на основе структуры Меркла — Дамгарда.
Исходное сообщение после дополнения разбивается на блоки, каждый блок — на 16 слов. Алгоритм пропускает каждый блок сообщения через цикл с 64 итерациями. На каждой итерации 2 слова преобразуются, функцию преобразования задают остальные слова. Результаты обработки каждого блока складываются, сумма является значением хеш-функции. Так как инициализация внутреннего состояния производится результатом обработки предыдущего блока, то нет возможности обрабатывать блоки параллельно. Графическое представление одной итерации обработки блока данных:
На текущий момент известны методы для конструирования коллизий до 31 итерации. Ввиду алгоритмической схожести SHA-2 с SHA-1 и наличия у последней потенциальных уязвимостей принято решение, что SHA-3 будет базироваться на совершенно ином алгоритме. 2 октября 2012 года NIST утвердил в качестве SHA-3 алгоритм Keccak.
«Привет, мир»: разбираем каждый шаг хэш-алгоритма SHA-256
Дополните код нулями, пока данные не станут равны 512 бит, минус 64 бита (в результате 448 бит):
Добавьте 64 бита в конец в виде целого числа с порядком байтов от старшего к младшему (big-endian), представляющего длину входного сообщения в двоичном формате. В нашем случае это 88, или «1011000».
Теперь у нас есть ввод, который будет делиться на 512 без остатка.
Шаг 2 — Инициализируйте значения хэша (h)
Теперь мы создаем 8 хэш-значений. Это жестко запрограммированные константы, которые представляют собой первые 32 бита дробных частей квадратных корней из первых восьми простых чисел: 2, 3, 5, 7, 11, 13, 17, 19.
Шаг 3 — Инициализация округленных констант (k)
Как и в предыдущем шаге, мы создадим еще несколько констант. На этот раз их будет 64. Каждое значение (0—63) представляет собой первые 32 бита дробных частей кубических корней первых 64 простых чисел (2—311).
Шаг 4 — Цикл фрагментов
Следующие шаги будут выполняться для каждого 512-битного «фрагмента» из наших входных данных. Поскольку фаза «Привет, мир» короткая, у нас есть только один фрагмент. В каждой итерации цикла мы будем изменять хэш-значения h0-h7, что приведет нас к конечному результату.
Шаг 5 — Созданием расписание сообщений (w)
Скопируйте входные данные из шага 1 в новый массив, где каждая запись представляет собой 32-битное слово:
Добавьте еще 48 слов, инициализированных нулем, чтобы у нас получился массив w [0… 63]
Измените обнуленные индексы в конце массива, используя следующий алгоритм:
Для i из w[16…63]:
- s0 = (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)
- s1 = (w[i- 2] rightrotate 17) xor (w[i- 2] rightrotate 19) xor (w[i- 2] rightshift 10)
- w[i] = w[i-16] + s0 + w[i-7] + s1
В расписании сообщений осталось 64 слова (w):
Шаг 6 — Сжатие
Инициализируйте переменные a, b, c, d, e, f, g, h и установите их равными текущим значениям хэш-функции соответственно h0, h1, h2, h3, h4, h5, h6, h7.
Запустите цикл сжатия, который изменит значения a… h. Выглядит он следующим образом:
- S1 = (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
- ch = (e and f) xor ((not e) and g)
- temp1 = h + S1 + ch + k[i] + w[i]
- S0 = (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
- maj = (a and b) xor (a and c) xor (b and c)
- temp2 := S0 + maj
- h = g
- g = f
- e = d + temp1
- d = c
- c = b
- b = a
- a = temp1 + temp2
Все вычисления выполняются еще 63 раза, меняя переменные a-h. К счастью, мы не делаем это вручную. В итоге мы получили:
Шаг 7 — Измените окончательные значения
После цикла сжатия, во время цикла фрагментов, мы изменяем хеш-значения, добавляя к ним соответствующие переменные a-h. Как и ранее, все сложение производится по модулю 2 ^ 32:
Шаг 8 — Финальный хэш
Наконец, соединяем все вместе.
Мы прошли каждый шаг (за исключением нескольких итераций) SHA-256 в подробностях. Если хотите увидеть весь путь, что мы совершили, в форме псевдокода, заходите на WikiPedia.
What is SHA-256?
Curated backend podcasts, videos and articles. All free.
If you’re looking to become a backend developer, or just stay up-to-date with the latest backend technologies and trends, you found the right place. Subscribe below to get a copy of our newsletter, The Boot.dev Beat, each month in your inbox. No spam, no sponsors, totally free.
SHA-2 (Secure Hash Algorithm 2), of which SHA-256 is a part, is one of the most popular hash algorithms around. A cryptographic hash, also often referred to as a “digest”, “fingerprint” or “signature”, is an almost perfectly unique string of characters that is generated from a separate piece of input text. SHA-256 generates a 256-bit (32-byte) signature.
Toward the end of this article, I’ll break down each step of SHA 256’s cryptographic algorithm, and work through a real example by hand. If you’re interested in learning cryptography with hands-on code examples, you can also check out my “Learn Cryptography” course on Boot.dev.
�� Generate a SHA 256 hash
If you’re not familiar with SHA-256, try this online generator. Enter any message and click the “hash” button.
�� What is SHA-256?
SHA-256 is a standard hash function, so the real question is, “what’s a hash function”?
A cryptographic hash function generates a “fingerprint” of an input string. For example, if we were to hash the entire text of JRR Tolkien’s “The Lord of The Rings” series using the SHA 256 algorithm, we would get a 256-bit output unique to that book’s text. If we changed even a single letter in the book, the output hash would be wildly different.
It’s worth noting that the output of a hash is “almost unique” because there are a finite number of output strings. After all, the output of SHA-256 is always 256 bits long, which means it has a fixed size. The number of possible inputs, however, is infinite, meaning some inputs will hash to the same output. When this happens, it’s called a “collision”, and it is nearly impossible. After all, in SHA-256 there are 2^256 possible outputs. Let me write out that number for you:
Three main purposes of a hash function are:
- To scramble data deterministically
- To accept an input of arbitrary length and output a fixed-length result
- To manipulate data irreversibly. The input cannot be derived from the output
SHA-2 is a strong family of hash functions because, as you would expect, it serves all the purposes mentioned above.
�� My Explanation of Some Real-World Uses for SHA
�� What is SHA-256 used for?
SHA-256 is useful in so many circumstances! It’s a fast and secure hash function, here are some of the most common ways that it’s used:
- To create website authentication schemes, using JWTs, HMACs and MACs
- To create digital signatures
- To secure blockchains like Bitcoin and Ethereum
- In anti-viruses, to compare the fingerprints of files and programs
- In version control systems like Git to check if data has changed
�� Can I use SHA-256 to hash passwords?
While it’s possible, you absolutely should not use SHA 256 to hash passwords! SHA-256 is designed to be computed very quickly, which means that if someone were to perform a brute force attack on your user’s passwords, they wouldn’t be safe. Instead you’ll want to use a key derivation function, which is just a password-hashing algorithm that’s designed to slow down attackers.
�� Is SHA-256 still considered secure?
SHA-2 is known for its security (it hasn’t broken down like SHA-1) and its speed. In cases where keys are not generated, such as proof-of-work Bitcoin mining, a fast hash algorithm like SHA-2 often has the upper hand. SHA-256 is formally defined in the National Institute of Standards and Technology’s FIPS 180-4. Along with standardization and formalization comes a list of test vectors that allow developers to ensure they’ve implemented the algorithm properly. As of 2022, SHA-256 is plenty secure to use in your applications.
�� How does the SHA-256 algorithm work?
Let’s go through an example of the SHA-256 hashing algorithm step-by-step, by hand. If you can stay awake through this whole walkthrough, you’ll understand all of its nuts and bolts.
�� Step 1 — Pre-Processing
- Convert “hello world” to binary:
- Append a single 1:
- Pad with 0’s until data is a multiple of 512, less 64 bits (448 bits in our case):
- Append 64 bits to the end, where the 64 bits are a big-endian integer representing the length of the original input in binary. In our case, 88, or in binary, “1011000”.
Now we have our input, which will always be evenly divisible by 512.
�� Step 2 — Initialize Hash Values (h)
Now we create 8 hash values. These are hard-coded constants that represent the first 32 bits of the fractional parts of the square roots of the first 8 primes: 2, 3, 5, 7, 11, 13, 17, 19
�� Step 3 — Initialize Round Constants (k)
Similar to step 2, we are creating some constants (Learn more about constants and when to use them here). This time, there are 64 of them. Each value (0-63) is the first 32 bits of the fractional parts of the cube roots of the first 64 primes (2 — 311).
�� Step 4 — Chunk Loop
The following steps will happen for each 512-bit “chunk” of data from our input. In our case, because “hello world” is so short, we only have one chunk. At each iteration of the loop, we will be mutating the hash values h0-h7, which will be the final output.
�� Step 5 — Create Message Schedule (w)
- Copy the input data from step 1 into a new array where each entry is a 32-bit word:
- Add 48 more words initialized to zero, such that we have an array w[0…63]
- Modify the zero-ed indexes at the end of the array using the following algorithm:
- For i from w[16…63]:
- s0 = (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)
- s1 = (w[i- 2] rightrotate 17) xor (w[i- 2] rightrotate 19) xor (w[i- 2] rightshift 10)
- w[i] = w[i-16] + s0 + w[i-7] + s1
Let’s do w[16] so we can see how it works:
This leaves us with 64 words in our message schedule (w):
�� Step 6 — Compression
- Initialize variables a, b, c, d, e, f, g, h and set them equal to the current hash values respectively. h0, h1, h2, h3, h4, h5, h6, h7
- Run the compression loop. The compression loop will mutate the values of a…h. The compression loop is as follows:
- for i from 0 to 63
- S1 = (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
- ch = (e and f) xor ((not e) and g)
- temp1 = h + S1 + ch + k[i] + w[i]
- S0 = (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
- maj = (a and b) xor (a and c) xor (b and c)
- temp2 := S0 + maj
- h = g
- g = f
- f = e
- e = d + temp1
- d = c
- c = b
- b = a
- a = temp1 + temp2
Let’s go through the first iteration, all addition is calculated modulo 2^32:
That entire calculation is done 63 more times, modifying the variables a-h throughout. We won’t do it by hand but we would have ender with:
�� Step 7 — Modify Final Values
After the compression loop, but still, within the chunk loop, we modify the hash values by adding their respective variables to them, a-h. As usual, all addition is modulo 2^32.
�� Step 8 — Concatenate Final Hash
Last but not least, slap them all together, a simple string concatenation will do.
Done! We’ve been through every step (sans some iterations) of SHA-256 in excruciating detail 🙂
I’m glad you’ve made it this far! Going step-by-step through the SHA-256 algorithm isn’t exactly a walk in the park. Learning the fundamentals that underpin web security can be a huge boon to your career as a computer scientist, however, so keep it up!
�� The Pseudocode
If you want to see all the steps we just did above in pseudocode form, then here it is, straight from WikiPedia:
�� Are SHA-2 and SHA-256 the same?
SHA-2 is an algorithm, or a generalized idea of how to hash data. SHA-2 has several variants, all of which use the same algorithm but use different constants. SHA-256, for example, sets additional constants that define the behavior of the SHA-2 algorithm, one of these constants is the output size, 256. The 256 and 512 in SHA-256 and SHA-512 refer to the respective digest size in bits.
�� What’s the difference between SHA-1 and SHA-2?
SHA-2 is a successor to the SHA-1 hash and remains one of the strongest hash functions in use today. SHA-256, as opposed to SHA-1, hasn’t been compromised. For this reason, there’s really no reason to use SHA-1 these days, it isn’t safe. The flexibility of output size (224, 256, 512, etc) also allows SHA-2 to pair well with popular KDFs and ciphers like AES-256.
�� Who designed SHA 256?
The NSA, or National Security Agency, designed and published SHA-256 and the rest of the SHA-2 family of hash functions in 2001. You might be wondering:
“Because the United State Government helped create SHA-256, do they have some sort of “back-door” to break the encryption protocol?”
The answer is “no”. The algorithm is open-source, so anyone can verify its security. While there may be exploitable vulnerabilities, no one has found them yet. At present, there isn’t much you can do to SHA-256 apart from attempting a brute-force attack.
Sorry, you have been blocked
This website is using a security service to protect itself from online attacks. The action you just performed triggered the security solution. There are several actions that could trigger this block including submitting a certain word or phrase, a SQL command or malformed data.
What can I do to resolve this?
You can email the site owner to let them know you were blocked. Please include what you were doing when this page came up and the Cloudflare Ray ID found at the bottom of this page.
Cloudflare Ray ID: 7e9235cd2f7c2fd1 • Your IP: Click to reveal 138.199.34.5 • Performance & security by Cloudflare