Recent

Author Topic: One-way functions: (crypto-) hash, MACs and so on  (Read 2028 times)

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
One-way functions: (crypto-) hash, MACs and so on
« on: January 11, 2020, 04:06:29 pm »
Apologies for a general question, but I'm sure that this is an easy one for somebody who has studied this particular field.

When generating a hash from a small amount of input, what is the "best" size of output relative to the amount of input?

All of the published crypto hashes appear to be optimised for variable but large amounts of input text, and to assume that the longer the output the more difficult it is to compromise. However it seems to me that even if the output is long- 128 or 256 bits- if you're dealing with a small and in particular fixed-length amount of input you gain nothing since the greater the disparity in size the more it tends towards a chosen-plaintext attack (the extreme case of zero bits input risks revealing the initialisation vector, and if the input were known to be a single byte you're not much better off).

A recent article https://www.theregister.co.uk/2019/12/16/internet_of_crap_encryption/ suggested that IoT security was bad in part because devices lack the memory space to generate good random primes. If- in effect- a space-constrained program only has a 16-bit random number generator, is it worth putting in a full-blown crypto library to implement SHA-256 or would something simpler be more appropriate?

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

simone

  • Hero Member
  • *****
  • Posts: 573
Re: One-way functions: (crypto-) hash, MACs and so on
« Reply #1 on: January 11, 2020, 07:05:49 pm »
The answer to your question depends on the context in which hash functions must be used (i.e.: digital signatures, password based key derivation functions, digital forensics etc.), on the security requirements that must be met in such a context (in particular, the degree of resistance to collision and preimage attacks) and on the constraints related to available computational resources.

In the last years, the spread of small digital devices with limited capabilities, particularly in the IoT sector, has stimulated intense research in the so-called 'lightweight encryption'. These articles offer surveys on this topic:

https://www.tandfonline.com/doi/full/10.1080/23742917.2017.1384917

https://www.ijser.org/researchpaper/A-survey-of-Lightweight-Cryptographic-Hash-Function.pdf

About the length of the digest generated by a hash function, remember that the probability of collisions is ideally proportional to about 1/(2^n), where n is the length of digest.

I can't be more concrete. Hope this can help anyway.
« Last Edit: January 11, 2020, 07:08:16 pm by simone »
Microsoft Windows 10 64 bit - Lazarus 3.0 FPC 3.2.2 x86_64-win64-win32/win64

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: One-way functions: (crypto-) hash, MACs and so on
« Reply #2 on: January 12, 2020, 07:28:35 pm »
@simone, Thanks for those papers which are interesting (even if the quality of their editing left a bit to be desired :-)

However neither of them really addresses my concern, which is that I suspect (without being enough of a mathematician to be able to prove) that a situation where a small amount of input is mapped through a hash function with larger output size risks compromising the one-way nature of the function used.

> remember that the probability of collisions is ideally proportional to about 1/(2^n), where n is the length of digest.

Where the unspoken assumption there is that the amount of input is large. Where the amount of input is known to not be large it approaches a chosen-plaintext scenario.

Poking around with Google, I came across https://crypto.stackexchange.com/questions/16219/cryptographic-hash-function-for-32-bit-length-input-keys where somebody is asking a similar question. One suggestion was to use something like MD5 but to truncate the output (which is presumably better than XORing portions of the output together in case that shows up patterns), alternatively the person answering suggests and discusses a fairly simple function while emphasising that the important thing is to get the input bits diffusing thoroughly across the output.

I think that a fair example of this sort of thing I'm considering is where a short message (four to eight bytes) is being sent over a reliable data path, with an appended hash value which includes unknown "salt" as an IV. My feeling is that the size of the hash should not be substantially larger than that of the data.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

simone

  • Hero Member
  • *****
  • Posts: 573
Re: One-way functions: (crypto-) hash, MACs and so on
« Reply #3 on: January 12, 2020, 10:32:18 pm »
However neither of them really addresses my concern, which is that I suspect (without being enough of a mathematician to be able to prove) that a situation where a small amount of input is mapped through a hash function with larger output size risks compromising the one-way nature of the function used.

...

Where the unspoken assumption there is that the amount of input is large. Where the amount of input is known to not be large it approaches a chosen-plaintext scenario.

That's right.

Poking around with Google, I came across https://crypto.stackexchange.com/questions/16219/cryptographic-hash-function-for-32-bit-length-input-keys where somebody is asking a similar question. One suggestion was to use something like MD5 but to truncate the output (which is presumably better than XORing portions of the output together in case that shows up patterns), alternatively the person answering suggests and discusses a fairly simple function while emphasising that the important thing is to get the input bits diffusing thoroughly across the output.

I think that a fair example of this sort of thing I'm considering is where a short message (four to eight bytes) is being sent over a reliable data path, with an appended hash value which includes unknown "salt" as an IV. My feeling is that the size of the hash should not be substantially larger than that of the data.

MarkMLl

For which purpose should you use a hash function?

One of practical reasons for which we use cryptographic hashes is to verify a property (typically integrity) relating to a large amount of data by working on a small amount (the so-called digest) which depends sensibly on that data. In this case, if the amount of data is smaller than the digest, it makes no sense to use a hash function. For integrity check of chunks with 128/256 bits, I think it's better to use a cyclic redundancy check (CRC) algorithm, a checksum, even a parity bit.

Differently, if you need to generate a cryptographic key from a password / passphrase, you should use a password based key derivation function (PBKDF, see RFC 8018).

About MD5: it is very weak and therefore strongly deprecated. If you reduce your digest with a truncation, it becomes even weaker.
« Last Edit: January 12, 2020, 10:44:38 pm by simone »
Microsoft Windows 10 64 bit - Lazarus 3.0 FPC 3.2.2 x86_64-win64-win32/win64

ASBzone

  • Hero Member
  • *****
  • Posts: 678
  • Automation leads to relaxation...
    • Free Console Utilities for Windows (and a few for Linux) from BrainWaveCC
Re: One-way functions: (crypto-) hash, MACs and so on
« Reply #4 on: January 13, 2020, 12:58:10 am »
When generating a hash from a small amount of input, what is the "best" size of output relative to the amount of input?
MarkMLl


It really depends on what the data is all about.   If it is small, rather than hashing, you should consider a KDF (key derivation function), which is better optimized for that size of data.


(Which simone also recommended)
-ASB: https://www.BrainWaveCC.com/

Lazarus v2.2.7-ada7a90186 / FPC v3.2.3-706-gaadb53e72c
(Windows 64-bit install w/Win32 and Linux/Arm cross-compiles via FpcUpDeluxe on both instances)

My Systems: Windows 10/11 Pro x64 (Current)

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: One-way functions: (crypto-) hash, MACs and so on
« Reply #5 on: January 13, 2020, 09:27:43 am »
For which purpose should you use a hash function?

One of practical reasons for which we use cryptographic hashes is to verify a property (typically integrity) relating to a large amount of data by working on a small amount (the so-called digest) which depends sensibly on that data. In this case, if the amount of data is smaller than the digest, it makes no sense to use a hash function. For integrity check of chunks with 128/256 bits, I think it's better to use a cyclic redundancy check (CRC) algorithm, a checksum, even a parity bit.

Although my understanding is that CRCs are optimised for low-level communications where the relative likelihood of single- vs double-bit errors is known etc. A non-CRC digest such as a hash doesn't make that sort of assumption, and is marginally better for catching entirely random errors.

Differently, if you need to generate a cryptographic key from a password / passphrase, you should use a password based key derivation function (PBKDF, see RFC 8018).

About MD5: it is very weak and therefore strongly deprecated. If you reduce your digest with a truncation, it becomes even weaker.

Thanks (also @ASBzone) for the KDF suggestion, useful search term. The suggestion of MD5 wasn't mine, I was quoting the StackExchange item I cited.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

Thaddy

  • Hero Member
  • *****
  • Posts: 14197
  • Probably until I exterminate Putin.
Re: One-way functions: (crypto-) hash, MACs and so on
« Reply #6 on: January 13, 2020, 09:46:05 am »
A recent article https://www.theregister.co.uk/2019/12/16/internet_of_crap_encryption/ suggested that IoT security was bad in part because devices lack the memory space to generate good random primes. If- in effect- a space-constrained program only has a 16-bit random number generator, is it worth putting in a full-blown crypto library to implement SHA-256 or would something simpler be more appropriate?

MarkMLl
The Raspberry Pi family are popular IoT devices and has even hardware optimized entropy true 32/64 bit RNG, so that article is at least in part nonsense.
The libraries - e.g. the one by user Xor-El - simply work and just as good as on other systems.

On devices like the Arduino family you can use  a dedicated HAT for proper RNG's or you can use a server that generates the random numbers.
Then again, a Raspberry Pi  Zero has the properties I described: true random entropy for $10.-
Of course not as perfect as radioactive decay based superduper professional and expensive devices.
The RPi takes is entropy from hardware fluctuations. That is good enough.
« Last Edit: January 13, 2020, 09:52:16 am by Thaddy »
Specialize a type, not a var.

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
Re: One-way functions: (crypto-) hash, MACs and so on
« Reply #7 on: January 13, 2020, 10:34:24 am »
The Raspberry Pi family are popular IoT devices and has even hardware optimized entropy true 32/64 bit RNG, so that article is at least in part nonsense.

Something like the RPi is vastly overpriced for applications like putting "intelligence" into a lightbulb or switch. Have you seen the recent articles elsewhere regarding a Chinese microcontroller that sells for around 3 US cents in reasonable quantity?

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

Thaddy

  • Hero Member
  • *****
  • Posts: 14197
  • Probably until I exterminate Putin.
Re: One-way functions: (crypto-) hash, MACs and so on
« Reply #8 on: January 13, 2020, 12:04:08 pm »
The Raspberry Pi family are popular IoT devices and has even hardware optimized entropy true 32/64 bit RNG, so that article is at least in part nonsense.

Something like the RPi is vastly overpriced for applications like putting "intelligence" into a lightbulb or switch. Have you seen the recent articles elsewhere regarding a Chinese microcontroller that sells for around 3 US cents in reasonable quantity?

MarkMLl
No, because something like the Orange Pi has no hwrng (hardware random number generator) but an emulator with less entropy.
Specialize a type, not a var.

minesadorada

  • Sr. Member
  • ****
  • Posts: 452
  • Retired
Re: One-way functions: (crypto-) hash, MACs and so on
« Reply #9 on: January 13, 2020, 05:50:27 pm »
For a high entropy random number there is a server in Australia with an API.  It can serve a Hex string of arbitrary length.

https://qrng.anu.edu.au/
Here it is wrapped into a component: https://wiki.lazarus.freepascal.org/EverettRandom
GPL Apps: Health MonitorRetro Ski Run
OnlinePackageManager Components: LazAutoUpdate, LongTimer, PoweredBy, ScrollText, PlaySound, CryptINI

 

TinyPortal © 2005-2018