phc-discussions - Re: [PHC] Initial hashing function. Feedback welcome

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date: Wed, 1 Jan 2014 01:40:26 +0000
From: Peter Gutmann <pgut001@...auckland.ac.nz>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] Initial hashing function. Feedback welcome

Bill Cox <waywardgeek@...il.com> writes:

>I think it depends on whether or not I want to be able to do the KDF on
>devices that don't have SSE or multiple cores.  I think filling the available
>memory bandwidth should be goal #1, and to meet that goal on mobile devices,
>we should have as simple a hashing function as possible.

A general-purpose KDF will have to run on a lot more than that.  How will this
work on embedded devices like routers, firewalls, print controllers, and
similar, which will have something like a MIPS or several-generations-old ARM
core and maybe 2-8MB of RAM?  Multi-core memory-hard functions seem like an
interesting gedanken experiment, but it's creating something with such a
specialised field of application (newer PCs and recent smart phones and
tablets) that you're seriously limiting its applicability.

If you're going to do memory-hard, or more accurately ASIC-hard stuff, then
you don't need to go to multi-threaded implementations.  Do something with a
largeish dynamic memory structure like an AVL tree (just taking the first
thing that popped into my head), which randomly touches memory all over the
place and would be near-impossible to do in hardware because you need a
general-purpose CPU for the update operations.

(What I mean is something like run a hash PRF to get 1MB of output, stuff it
all into an AVL tree, do a tree-walk to get the input to the next lot of
hashing, and repeat.  The AVL step is the killer for both caches and custom
hardware).

The downside is that this rapidly gets very Rube Goldberg-y.

Peter.