Add SHA-3 and SHAKE (Keccak) support

[tiran]

BPO	16113
Nosy	@tim-one, @loewis, @rhettinger, @gpshead, @jcea, @pitrou, @vstinner, @larryhastings, @tiran, @ezio-melotti, @asvetlov, @mgorny, @dstufft
Files	521e85a613bf.diff remove_sha3.patch SHA3-and-SHAKE-support-for-Python.patch SHA3-and-SHAKE-support-for-Python-2.patch SHA3-and-SHAKE-support-for-Python-3.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2016-09-08.09:51:00.910>
created_at = <Date 2012-10-03.03:10:04.668>
labels = ['extension-modules', 'type-feature']
title = 'Add SHA-3 and SHAKE (Keccak) support'
updated_at = <Date 2017-02-28.11:18:50.985>
user = 'https://github.com/tiran'

bugs.python.org fields:

activity = <Date 2017-02-28.11:18:50.985>
actor = 'mgorny'
assignee = 'none'
closed = True
closed_date = <Date 2016-09-08.09:51:00.910>
closer = 'christian.heimes'
components = ['Extension Modules']
creation = <Date 2012-10-03.03:10:04.668>
creator = 'christian.heimes'
dependencies = []
files = ['27441', '33298', '42764', '43107', '44176']
hgrepos = []
issue_num = 16113
keywords = ['patch']
message_count = 80.0
messages = ['171848', '171882', '171898', '171913', '171929', '171963', '171964', '171968', '171971', '171983', '171995', '172070', '172100', '172144', '172152', '172157', '172158', '172313', '172314', '172316', '172319', '172324', '183129', '190303', '191931', '191940', '191971', '201078', '201079', '201080', '201081', '201082', '201083', '201084', '201085', '201086', '201092', '201096', '201928', '207169', '207170', '207171', '207184', '207187', '207188', '207189', '207190', '207191', '207192', '207225', '207226', '207228', '207229', '231838', '253023', '253025', '253028', '253029', '253174', '264029', '265033', '265059', '265066', '265088', '265125', '266911', '266974', '273252', '273328', '273330', '273331', '273363', '274786', '274789', '274790', '274791', '274793', '274797', '275000', '288706']
nosy_count = 21.0
nosy_names = ['tim.peters', 'loewis', 'rhettinger', 'gregory.p.smith', 'jcea', 'pitrou', 'vstinner', 'larry', 'christian.heimes', 'habnabit', 'ezio.melotti', 'spatz', 'Arfrever', 'asvetlov', 'mgorny', 'python-dev', 'sbt', 'bjornedstrom', 'dstufft', 'markk', 'haakon']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue16113'
versions = ['Python 3.6']

[tiran]

Today the latest crypto hash function was announced by NIST [1]. I suggest that we include the new hash algorithm in 3.4 once it lands in OpenSSL.

The Keccak site also has a reference implementation in C and Assembler [2]. It may take some effort to integrate the reference implementation as it contains several optimized backends for X86, X86_64, SIMD and various ARM platforms.

[1] http://www.nist.gov/itl/csd/sha-100212.cfm
[2] http://keccak.noekeon.org/

[jcea]

We have MD5, SHA1, sha256, sha512 implemented, to use when openssl is not available. Can we do the same with sha-3?. I would suggest to adopt the reference implementation without extensive optimizations, since we will have them when openssl has them.

So we might implement SHA-3 now and integrate OpenSSL implementation later, when available. This is interesting, for instance, because many users of Python 3.4 will have a non "up to date" OpenSSL system library.

[tiran]

I've done some experiments with the reference implementation and adopted code of sha1module.c for sha3: https://bitbucket.org/tiran/pykeccak

So far the code just compiles (64bit only) but doesn't work properly yet. I may need to move away from the NIST interface and use the sponge interface directly.

[bjornedstrom]

For what it's worth, I've built a working C-based sha3-module that is available here: https://github.com/bjornedstrom/python-sha3

Note that I've only tested this on Python 2, for Python 3 YMMV.

Best regards
Björn

[tiran]

Hello Björn,

thanks for the information. Your package didn't turn up on Google when I started with my experiment. Perhaps it's too new?

Your code and mine have lots of similarities. I was amused when I saw that you had the same issue with the block size attribute. At first I set it to 200 (1600 / 8) but eventually I didn't implement it.

My code does everything in C with a separate constructor for each flavor of SHA-3. It's compatible to Python 2.6 to 3.4 and uses the optimized code for 32 and 64bit platforms.

Oh, and my code is now working properly. Feel free to review the module. I'll upload the test code later.

[tiran]

Release 0.1 of pysha3 [1] is out. I've tweaked the C module to make it compatible with Python 2.6 to 3.4. The module and its tests run successfully under Linux and Windows. So far I've tested Linux X84_64 (2.7, 3.2, 3.3, 3.4), Windows X86 (2.6, 2.7, 3.2, 3.3) and Windows X86_64 (2.6, 2.7, 3.2, 3.3).

Please review Modules/sha3module.c and ignore all version specific #if blocks. For Python 3.4 I'm going to remove all blocks for Python < 3.3.

[1] http://pypi.python.org/pypi/pysha3/0.1

[pitrou]

Please review Modules/sha3module.c

Can't you post a patch here?

[tiran]

How about a sandbox repos?

[pitrou]

Good, you can click the "create patch" button when it's ready :)

[tiran]

Antoine pointed out that the code contains C++ comments and exports a lot of functions. The latest patch has all // comments replaced, marks all functions and globals as static and #includes the C files directly.

[tiran]

Please review the latest patch.

I've included Gregory as he is the creator of hashlib.

[tiran]

The hightlights of the next patch are

• release the GIL
• more test vectors
• remove bgr_endian.h
• move typedef UINT64 to sha3module
• declare more globals as static