0
$\begingroup$

I'm trying to calculate how many possible combinations of files there can be using a signed 64-bit file length, but can't seem to find a formula (or I'm using the wrong keywords). For example, the number of unique files that have a length of 256 bytes is $2^{256*8}$ = $2^{2048}$. I assume the total number of combinations across all file lengths will be some kind of geometric sequence?

The reason I want to calculate it is because I'm curious how it relates to the number of possible SHA-256 hashes ($2^{256}$). Also, if I calculate the SHA-256 hash of the SHA-256 hash of a file's contents, how much have I reduced the entropy (if that's the correct term)?

Improve this question
$\endgroup$
1
  • $\begingroup$ It looks like you did not work on that one hard enough. Some hints follow. You will find the restrictions on the input of SHA-256 in the standard. That does not match the question and title, any way I read length. Worse, there's a clash in the usual meaning of the term. You need to define what length is in your context. $\endgroup$
    – fgrieu ♦
    Dec 6, 2011 at 12:50

2 Answers 2

Reset to default
4
$\begingroup$

For a given file length L bytes the combinations for that length is 256^L. The total combination is the sum of combinations for all file lengths L from zero to (2^63)-1. Just substitute parameters in the formula for summing the n first terms of a geometric series. The rest is left as an exercise to the reader :-)

If all you need is a rough order-of-magnitude estimate it is really sufficient to just look at the highest order term, which provides a quick lower-bound estimate and which will already tells you the ratio is a very large number (very large for cryptographic purposes), which means the factor you have "reduced entropy" is a number very close to zero (once again, for cryptographic purposes).

Improve this answer
$\endgroup$
1
  • $\begingroup$ For example if the max file size was 8 bits, we get 2$^{8}$+2$^{7}$+...+2$^{0}$ = 2$^{9}$-1. In your example for a signed 64-bit integer the answer is 2$^{64}$-1 or 18,446,744,073,709,551,615, and for SHA-256 the answer is 2$^{65}$-1 or 36,893,488,147,419,103,231. For SHA-512 the answer is 2$^{129}$-1, which is around 680 trillion trillion trillion. $\endgroup$
    – Richie Frame
    Dec 22, 2013 at 0:31
2
$\begingroup$

Update:

The theory

If you have a file system like NTFS, this uses 64 bit for the file size, so you can have 2^64 Bytes = 16 EB in one file.

Imagine you have only one 16 EB large file. There are 256^18446744073709551616 different file contents possible. In total there are even more, because you need to sum up all file sizes.

From AES you get 2^256 different hashes. Compared to the possible combinations of file content, that's off by a huge factor and it seems that there must be many collisions.

The reality

The universe has approximately 10^82 = 2^272 atoms, Earth has about 10^50 = 2^166 atoms.

So even if you could store a whole file on every atom on Earth, there is still the possibility for a unique AES hash for every file.

Improve this answer
$\endgroup$
0

Your Answer

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

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