Skein

From BitcoinWiki
This is the approved revision of this page, as well as being the most recent.
Jump to: navigation, search
Skein algorithm – Mining, Pool

Skein is a variable-bit hashing algorithm developed by a group of authors headed by Bruce Schneier. The Skein algorithm is executed as a universal cryptographic primitive, based on the block cipher Threefish, working in UBI-hashing mode. The main requirements of the development are optimization for minimal memory usage, cryptographically secure hashing of small messages, resistance to all existing attacks on hash functions, optimization for 64 — bit processors and active use of table accesses.

What is Skein?[edit]

Skein is a cryptographic hash function, which was created in 2008 by a group of authors led by Bruce Schneier and was one of five finalists in the NIST hash function competition, but in 2012 In the final the winner was chosen Keccak algorithm, the most productive and insensitive to the vulnerabilities of SHA-2. The name Skein refers to how the Skein function intertwines the input, similar to a skein of yarn., while leveraging an optional low-overhead argument-system for flexibility. Skein's algorithm as also reference implementation was given to public domain.

Threefish Block[edit]

Threefish is a configurable block cipher defined for 256, 512, and 1024 bit blocks and arbitrary output sizes. The authors claim 6.1 cycles per byte for any output size on an Intel Core 2 Duo in 64-bit mode.

The cipher is implemented as a permutation network. The core of Threefish is based on a MIX function that transforms 2 64-bit words using a single addition, rotation by a constant and XOR. The UBI chaining mode combines an input chaining value with an arbitrary length input string and produces a fixed size output.

It uses 72 rounds for 256-bit and 512-bit ciphers, and 80 rounds for 1024-bit ciphers. Between rounds there is a permutation of words, and every four rounds is added to the key, whereby there is a nonlinearity.

Threefish's nonlinearity comes entirely from the combination of addition operations and XORs; it does not use S-boxes. The function is optimized for 64-bit processors, and the Skein paper defines optional features such as randomized hashing, parallelizable tree hashing, a stream cipher, personalization, and a key derivation function.

UBI[edit]

Threefish in Skein is used in UBI (Unique Block Iteration) hashing mode. UBI mode is a kind of Matyas-Meyer-Oseas mode. Each UBI link combines input messages from the previous link of the chain with a sequence of arbitrary length and sets the output value to a fixed size. The message sent between links (tweak) contains information about how many bytes have been processed, the start and end flags of the chain, and a data type field that allows you to distinguish between UBI applications.

UBI guarantees that the result of hashing the same message cannot be reproduced and that it provides additional protection by allowing the same messages to enter the hash function and the cipher.

Cryptanalysis of Skein algorithm[edit]

In 2009, the authors investigated Threefish, as an important part Skein, to cryptologist. Together with the research creators, they came to the result specified in the table.

Number of rounds Time Memory Type of cryptanalysis
8 1 - 511-bit pseudomallei
16 26 - 459-bit pseudomallei
17 224 - 434-bit pseudomallei
17 28,6 - Related-key distinguisher
21 23.4 - Related-key distinguisher
21 - - Related-key impossible differential
25  ? - Related-key key recovery (conjectured)
25 2416.6 - Related-key key recovery
26 2507.8 - Related-key key recovery
32 2312 271 Related-key boomerang key recovery
34 2398 - Related-key boomerang distinguisher
35 2478 - Known-related-key boomerang distinguisher

In October 2010, an attack that combines rotational cryptanalysis with the rebound attack was published. The attack finds rotational collisions for 53 of 72 rounds in Threefish-256, and 57 of 72 rounds in Threefish-512. It also affects the Skein hash function.

The Skein team tweaked the key schedule constant for round 3 of the NIST hash function competition, to make this attack less effective, even though they believe the hash would still be secure without these tweaks.

Skein Versions[edit]

There are implementations of Skein for three variants of the internal state value: 256, 512, and 1024 bits. The main option is considered to be Skein-512, which can be safely used for all cryptographic applications in the foreseeable future. The 1024-bit version is even more secure and works twice as fast in existing hardware implementations. Skein-256 is the best option for use in low-memory devices (such as smart cards), as it requires only 100 bytes of RAM, unlike Skein-512, which requires 200 bytes. Due to the device Threefish, Skein is the fastest on 64-bit processors. The table below provides a comparison of the performance of Skein and SHA algorithms. The table shows the speed (in cycles per byte) of the C implementation on a 64-bit processor.

Algorithm/Message length (Byte) 1 10 100 1000 10000 100000
Skein-256 774 77 16,6 9,8 9,2 9,2
Skein-512 1086 110 15,6 7,3 6,6 6,5
Skein-1024 3295 330 33,2 14,2 12,3 12,3
SHA-1 677 74,2 14,0 10,4 10,0 10,0
SHA-224 1379 143,1 27,4 20,7 20,1 20,0
SHA-256 1405 145,7 77,6 20,7 20,1 20,0
SHA-384 1821 187,3 19,6 13,7 13,4 13,3
SHA-512 1899 192,5 20,6 13,8 13,4 13,3

As you can see from the table, Skein works twice as fast as SHA-512.

Examples of Skein hashes[edit]

Hash values of empty string.

Skein-256-256("")
0x c8877087da56e072870daa843f176e9453115929094c3a40c463a196c29bf7ba
Skein-512-256("")
0x 39ccc4554a8b31853b9de7a1fe638a24cce6b35a55f2431009e18780335d2621
Skein-512-512("")
0x bc5b4c50925519c290cc634277ae3d6257212395cba733bbad37a4af0fa06af41fca7903d06564fea7a2d3730dbdb80c1f85562dfcc070334ea4d1d9e72cba7a

Even a small change in the message will (with overwhelming probability) result in a mostly different hash, due to the avalanche effect. For example, adding a period to the end of the sentence:

Skein-512-256("The quick brown fox jumps over the lazy dog")
0x b3250457e05d3060b1a4bbc1428bc75a3f525ca389aeab96cfa34638d96e492a
Skein-512-256("The quick brown fox jumps over the lazy dog.")
0x 41e829d7fca71c7d7154ed8fc8a069f274dd664ae0ed29d365d919f4e575eebb
Skein-512-512("The quick brown fox jumps over the lazy dog")
0x 94c2ae036dba8783d0b3f7d6cc111ff810702f5c77707999be7e1c9486ff238a7044de734293147359b4ac7e1d09cd247c351d69826b78dcddd951f0ef912713
Skein-512-512("The quick brown fox jumps over the lazy dog.")
0x 658223cb3d69b5e76e3588ca63feffba0dc2ead38a95d0650564f2a39da8e83fbb42c9d6ad9e03fbfde8a25a880357d457dbd6f74cbcb5e728979577dbce5436

Skein in Python[edit]

PySkein is an extension module for Python, implementing the Skein hash algorithm, one of the five finalists of the NIST SHA-3 Competition. While ultimately not selected as the winner of that competition, Skein may still be useful as an alternative hash algorithm, offering flexible hashing modes with various parameters. PySkein provides all features of Skein through a Pythonic interface and is released as free software under the GNU General Public License. Its highlights are:

  • Simple interface following the hash algorithms in the Python standard library (like hashlib.sha1 or hashlib.sha256);
  • All features of the Skein specification (flexible digest sizes, MAC generation, tree hashing, and various others);
  • High performance through optimized C implementation (7.1 cycles/byte for sequential hashing and 4.2 cycles/byte for tree hashing on two cores, measured on an Athlon 64 X2);
  • Threefish, the tweakable block cipher used in Skein, available for encryption and decryption on its own.

See Also on BitcoinWiki[edit]

External links[edit]