4
$\begingroup$

OK, so we've had questions about hashes build from stream ciphers (not a good idea) and about stream ciphers made out of hashes (yes, of course, use counter mode). What I want to ask is related but doesn't seem to have been asked before.

Is it possible to make a streaming hash? With a "streaming hash" I mean a hash function whose state is updated for each separate byte, instead of the byte itself having to be cached until a full message block is known.

Or, to turn the question around, is it required to always split the message into blocks instead of processing bytes? Or is this just an artifact of the functions used internally by the hash?

Improve this question
$\endgroup$
7
  • $\begingroup$ And no, padding each byte is not considered efficient enough :P $\endgroup$
    – Maarten Bodewes ♦
    Commented Feb 6, 2017 at 16:41
  • 2
    $\begingroup$ You could just reduce the block size to one byte, which comes natural for a sponge, but Davies-Meyer with a small key isn't that ugly either. $\endgroup$
    – CodesInChaos
    Commented Feb 6, 2017 at 16:45
  • $\begingroup$ When you say hash do you mean collision resistant hash? Or are keyed constructions acceptable? I think some polynomial MACs support absorbing smaller inputs. $\endgroup$
    – CodesInChaos
    Commented Feb 6, 2017 at 16:47
  • $\begingroup$ @CodesInChaos Yeah, a collision resistant hash. A keyed hash would be a separate question. Interesting comment about the sponge, hadn't thought of that. It would of course require a full run of function F I suppose (this is the inherent weakness of the question, how much processing would I expect for each byte)? $\endgroup$
    – Maarten Bodewes ♦
    Commented Feb 6, 2017 at 16:50
  • 1
    $\begingroup$ As CodesInChaos stated: sponge construction would be the way to go. Looking beyond SHA-3, you'll notice "how much processing" can actually be adapted to individual scenarios - that is, if that makes sense and assuming you really know what you're doing. (Somewhat related to that: Can we exchange the permutation of a sponge construction?) $\endgroup$
    – e-sushi
    Commented Feb 6, 2017 at 16:58

1 Answer 1

Reset to default
3
$\begingroup$

As CodesInChaos mentioned in the comments, you could simply set the size of the digested block to one byte (or bit, if that is your preference). Also as mentioned in the comments, this will not necessarily work nicely with any given hashing construction.

Is it required to always split the message into blocks instead of processing bytes?

I am not sure how you would process any input without breaking it into some kind of blocks. Considering that a block can be an arbitrary size that is usually defined by the algorithm in question, a block could range from 1 bit to however many bits constitute a complete input message. One bit is a valid blocksize, one byte is a valid blocksize, and X-Y bit words for any X and Y is a valid blocksize.

So I would say yes, it is unavoidable to split the message up into blocks for processing. Input of any length that you feed into the compression function constitutes a block. This seems unavoidable, unless you simply don't compress any input. Even if you compress the entire message at once, you are still working on one block.

Is this just an artifact of the functions used internally by the hash

The blocksize influences the performance of the compression function. If you digest 512 bits at a time using X instructions, clearly this will digest data much more quickly then digesting 1 bit at a time using the same X instructions. This assumes the CPU has appropriately sized registers and instructions for operating on the desired word size - which may not necessarily be the case.

Improve this answer
$\endgroup$
2
  • $\begingroup$ "One bit is a valid blocksize, one byte is a valid blocksize". If you use that kind of reasoning stream ciphers do not exist. I was hoping for something that doesn't have the full performance penalty of the underlying function (which doesn't have to be a block function). That all said, thanks for the answer; upvoted! $\endgroup$
    – Maarten Bodewes ♦
    Commented Feb 6, 2017 at 18:53
  • 1
    $\begingroup$ @MaartenBodewes "a block can be an arbitrary size that is usually defined by the algorithm in question" is closer to the core of my reasoning, I feel. Of course you can create a hash function that digests one byte at a time, there is nothing stopping you from structuring an algorithm this way. I have personally explored this idea in practice using an 8x256 S-box. $\endgroup$
    – Ella Rose
    Commented Feb 6, 2017 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.