rfc9923v4.txt   rfc9923.txt 
skipping to change at line 128 skipping to change at line 128
Collision: Finding two data inputs that yield the same hash output. Collision: Finding two data inputs that yield the same hash output.
First Pre-Image: Given a hash output, finding a data input that First Pre-Image: Given a hash output, finding a data input that
hashes to that output. hashes to that output.
Second Pre-Image: Given a first data input, finding a second input Second Pre-Image: Given a first data input, finding a second input
that produces the same hash output as the first. that produces the same hash output as the first.
For a hash function producing N bits, there necessarily will be For a hash function producing N bits, there necessarily will be
collisions among the hashes of more than 2**N distinct inputs. And collisions among the hashes of more than 2^N distinct inputs. And if
if the hash function can produce hashes covering all 2**N possible the hash function can produce hashes covering all 2^N possible
outputs, then there will exist first and second pre-images. FNV is outputs, then there will exist first and second pre-images. FNV is
NOT RECOMMENDED for any application that requires that it be NOT RECOMMENDED for any application that requires that it be
computationally infeasible for one of the above types of attacks to computationally infeasible for one of the above types of attacks to
succeed. succeed.
FNV hashes are generally not applicable for use when faced with an FNV hashes are generally not applicable for use when faced with an
active adversary in a security scheme where the modest effort active adversary in a security scheme where the modest effort
required to compute FNV hashes (see Appendix A) and their other non- required to compute FNV hashes (see Appendix A) and their other non-
cryptographic characteristics (see Section 1.4) would make the scheme cryptographic characteristics (see Section 1.4) would make the scheme
ineffective against the threat model being considered. It is ineffective against the threat model being considered. It is
skipping to change at line 299 skipping to change at line 299
and multiply operations is reversed. Operational experience and multiply operations is reversed. Operational experience
indicates better hash dispersion for small amounts of data with FNV- indicates better hash dispersion for small amounts of data with FNV-
1a. FNV-0 is the same as FNV-1 but with offset_basis set to zero. 1a. FNV-0 is the same as FNV-1 but with offset_basis set to zero.
FNV-1a is suggested for general use. FNV-1a is suggested for general use.
2.1. FNV Primes 2.1. FNV Primes
The theory behind FNV_Primes is beyond the scope of this document, The theory behind FNV_Primes is beyond the scope of this document,
but the basic property to look for is how an FNV_Prime would impact but the basic property to look for is how an FNV_Prime would impact
dispersion. Now, consider any n-bit FNV hash where n >= 32 and is dispersion. Now, consider any n-bit FNV hash where n >= 32 and is
also a power of 2 -- in particular, n = 2**s. For each such n-bit also a power of 2 -- in particular, n = 2^s. For each such n-bit FNV
FNV hash, an FNV_Prime p is defined as follows: hash, an FNV_Prime p is defined as follows:
* When s is an integer and 4 < s < 11, FNV_Prime is the smallest * When s is an integer and 4 < s < 11, FNV_Prime is the smallest
prime p of the form: prime p of the form:
256**int((5 + 2**s)/12) + 2**8 + b 256**int((5 + 2**s)/12) + 2**8 + b
* where b is an integer such that: * where b is an integer such that:
0 < b < 2**8 0 < b < 2**8
skipping to change at line 332 skipping to change at line 332
The case where s < 5 is not considered due to the resulting low hash The case where s < 5 is not considered due to the resulting low hash
quality. Such small hashes can, if desired, be derived from a 32-bit quality. Such small hashes can, if desired, be derived from a 32-bit
FNV hash by XOR folding (see Section 3). The case where s > 10 is FNV hash by XOR folding (see Section 3). The case where s > 10 is
not considered because of the doubtful utility of such large FNV not considered because of the doubtful utility of such large FNV
hashes and because the criteria for such large FNV_Primes would be hashes and because the criteria for such large FNV_Primes would be
more complex, due to the sparsity of such large primes, and would more complex, due to the sparsity of such large primes, and would
needlessly clutter the criteria given above. needlessly clutter the criteria given above.
Per the above constraints, an FNV_Prime should have only six or seven Per the above constraints, an FNV_Prime should have only six or seven
one bits in it: one relatively high-order one bit, the 2**9 bit, and one bits in it: one relatively high-order one bit, the 2^9 bit, and
four or five one bits in the low-order byte. Therefore, some four or five one bits in the low-order byte. Therefore, some
compilers may seek to improve the performance of a multiplication compilers may seek to improve the performance of a multiplication
with an FNV_Prime by replacing the multiplication with shifts and with an FNV_Prime by replacing the multiplication with shifts and
adds. However, the performance of this substitution is highly adds. However, the performance of this substitution is highly
hardware dependent and should be done with care. The selection of hardware dependent and should be done with care. The selection of
FNV_Primes prioritizes the quality of the resulting hash function, FNV_Primes prioritizes the quality of the resulting hash function,
not compiler optimization considerations. not compiler optimization considerations.
2.2. FNV offset_basis 2.2. FNV offset_basis
skipping to change at line 416 skipping to change at line 416
A somewhat stronger hash may be obtained for exact FNV sizes by A somewhat stronger hash may be obtained for exact FNV sizes by
calculating an FNV twice as long as the desired output ( S = 2*k ) calculating an FNV twice as long as the desired output ( S = 2*k )
and performing such XOR data folding using a k equal to the size of and performing such XOR data folding using a k equal to the size of
the desired output. However, if a much stronger hash is desired, the desired output. However, if a much stronger hash is desired,
cryptographic algorithms, such as those specified in [FIPS202] or cryptographic algorithms, such as those specified in [FIPS202] or
[RFC6234], should be used. [RFC6234], should be used.
If it is desired to obtain a hash result that is a value between 0 If it is desired to obtain a hash result that is a value between 0
and max, where max+1 is not a power of 2, simply choose an FNV hash and max, where max+1 is not a power of 2, simply choose an FNV hash
size S such that 2**S > max. Then, calculate the following: size S such that 2^S > max. Then, calculate the following:
FNV_S mod ( max+1 ) FNV_S mod ( max+1 )
The resulting remainder will be in the range desired but will suffer The resulting remainder will be in the range desired but will suffer
from a bias against large values, with the bias being larger if 2**S from a bias against large values, with the bias being larger if 2^S
is only slightly larger than max. If this bias is acceptable, no is only slightly larger than max. If this bias is acceptable, no
further processing is needed. If this bias is unacceptable, it can further processing is needed. If this bias is unacceptable, it can
be avoided by retrying for certain high values of hash, as follows, be avoided by retrying for certain high values of hash, as follows,
before applying the mod operation above: before applying the mod operation above:
X = ( int( ( 2**S - 1 ) / ( max+1 ) ) ) * ( max+1 ) X = ( int( ( 2**S - 1 ) / ( max+1 ) ) ) * ( max+1 )
while ( hash >= X ) while ( hash >= X )
hash = ( hash * FNV_Prime ) + offset_basis hash = ( hash * FNV_Prime ) + offset_basis
4. Hashing Multiple Values Together 4. Hashing Multiple Values Together
skipping to change at line 520 skipping to change at line 520
The FNV Primes are as follows: The FNV Primes are as follows:
+==========================================================+ +==========================================================+
| Size FNV Prime = Expression | | Size FNV Prime = Expression |
+==========================================================+ +==========================================================+
| = Decimal | | = Decimal |
+==========================================================+ +==========================================================+
| = Hexadecimal | | = Hexadecimal |
+==========================================================+ +==========================================================+
| 32-bit FNV_Prime = 2**24 + 2**8 + 0x93 | | 32-bit FNV_Prime = 2^24 + 2^8 + 0x93 |
+----------------------------------------------------------+ +----------------------------------------------------------+
| = 16,777,619 | | = 16,777,619 |
+----------------------------------------------------------+ +----------------------------------------------------------+
| = 0x01000193 | | = 0x01000193 |
+----------------------------------------------------------+ +----------------------------------------------------------+
| 64-bit FNV_Prime = 2**40 + 2**8 + 0xB3 | | 64-bit FNV_Prime = 2^40 + 2^8 + 0xB3 |
+----------------------------------------------------------+ +----------------------------------------------------------+
| = 1,099,511,628,211 | | = 1,099,511,628,211 |
+----------------------------------------------------------+ +----------------------------------------------------------+
| = 0x00000100 000001B3 | | = 0x00000100 000001B3 |
+----------------------------------------------------------+ +----------------------------------------------------------+
| 128-bit FNV_Prime = 2**88 + 2**8 + 0x3B | | 128-bit FNV_Prime = 2^88 + 2^8 + 0x3B |
+----------------------------------------------------------+ +----------------------------------------------------------+
| = 309,485,009,821,345,068,724,781,371 | | = 309,485,009,821,345,068,724,781,371 |
+----------------------------------------------------------+ +----------------------------------------------------------+
| = 0x00000000 01000000 00000000 0000013B | | = 0x00000000 01000000 00000000 0000013B |
+----------------------------------------------------------+ +----------------------------------------------------------+
| 256-bit FNV_Prime = 2**168 + 2**8 + 0x63 | | 256-bit FNV_Prime = 2^168 + 2^8 + 0x63 |
+----------------------------------------------------------+ +----------------------------------------------------------+
| = 374,144,419,156,711,147,060,143,317,175,368,453,031, | | = 374,144,419,156,711,147,060,143,317,175,368,453,031, |
| 918,731,002,211 | | 918,731,002,211 |
+----------------------------------------------------------+ +----------------------------------------------------------+
| = 0x0000000000000000 0000010000000000 0000000000000000 | | = 0x0000000000000000 0000010000000000 0000000000000000 |
| 0000000000000163 | | 0000000000000163 |
+----------------------------------------------------------+ +----------------------------------------------------------+
| 512-bit FNV_Prime = 2**344 + 2**8 + 0x57 | | 512-bit FNV_Prime = 2^344 + 2^8 + 0x57 |
+----------------------------------------------------------+ +----------------------------------------------------------+
| = 35,835,915,874,844,867,368,919,076,489,095,108,449, | | = 35,835,915,874,844,867,368,919,076,489,095,108,449, |
| 946,327,955,754,392,558,399,825,615,420,669,938,882,575, | | 946,327,955,754,392,558,399,825,615,420,669,938,882,575, |
| 126,094,039,892,345,713,852,759 | | 126,094,039,892,345,713,852,759 |
+----------------------------------------------------------+ +----------------------------------------------------------+
| = 0x0000000000000000 0000000000000000 0000000001000000 | | = 0x0000000000000000 0000000000000000 0000000001000000 |
| 0000000000000000 0000000000000000 0000000000000000 | | 0000000000000000 0000000000000000 0000000000000000 |
| 0000000000000000 0000000000000157 | | 0000000000000000 0000000000000157 |
+----------------------------------------------------------+ +----------------------------------------------------------+
| 1024-bit FNV_Prime = 2**680 + 2**8 + 0x8D | | 1024-bit FNV_Prime = 2^680 + 2^8 + 0x8D |
+----------------------------------------------------------+ +----------------------------------------------------------+
| = 5,016,456,510,113,118,655,434,598,811,035,278,955,030, | | = 5,016,456,510,113,118,655,434,598,811,035,278,955,030, |
| 765,345,404,790,744,303,017,523,831,112,055,108,147,451, | | 765,345,404,790,744,303,017,523,831,112,055,108,147,451, |
| 509,157,692,220,295,382,716,162,651,878,526,895,249,385, | | 509,157,692,220,295,382,716,162,651,878,526,895,249,385, |
| 292,291,816,524,375,083,746,691,371,804,094,271,873,160, | | 292,291,816,524,375,083,746,691,371,804,094,271,873,160, |
| 484,737,966,720,260,389,217,684,476,157,468,082,573 | | 484,737,966,720,260,389,217,684,476,157,468,082,573 |
+----------------------------------------------------------+ +----------------------------------------------------------+
| = 0x0000000000000000 0000000000000000 0000000000000000 | | = 0x0000000000000000 0000000000000000 0000000000000000 |
| 0000000000000000 0000000000000000 0000010000000000 | | 0000000000000000 0000000000000000 0000010000000000 |
| 0000000000000000 0000000000000000 0000000000000000 | | 0000000000000000 0000000000000000 0000000000000000 |
skipping to change at line 6237 skipping to change at line 6237
BigInteger fnvOffsetBasis = new BigInteger BigInteger fnvOffsetBasis = new BigInteger
("14695981039346656037"); ("14695981039346656037");
BigInteger digest = fnvOffsetBasis; BigInteger digest = fnvOffsetBasis;
for (int i = 0; i < inpString.length(); i++) { for (int i = 0; i < inpString.length(); i++) {
digest = digest.xor(BigInteger.valueOf( digest = digest.xor(BigInteger.valueOf(
(int) inpString.charAt(i))); (int) inpString.charAt(i)));
digest = digest.multiply(fnvPrime).mod(m); digest = digest.multiply(fnvPrime).mod(m);
} }
return digest; return (digest);
} }
} }
<CODE ENDS> <CODE ENDS>
Acknowledgements Acknowledgements
The contributions of the following, listed in alphabetical order, are The contributions of the following, listed in alphabetical order, are
gratefully acknowledged: gratefully acknowledged:
 End of changes. 12 change blocks. 
14 lines changed or deleted 14 lines changed or added

This html diff was produced by rfcdiff 1.48.