Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Re^2: [OT] The statistics of hashing.

by BrowserUk (Pope)
on Apr 01, 2012 at 16:23 UTC ( #962893=note: print w/replies, xml ) Need Help??


in reply to Re: [OT] The statistics of hashing.
in thread [OT] The statistics of hashing.

I only bring this up because I think you started out with the same assumption about MD5, ...

That is a very good point.

The distribution of any (perfect(*)) hashing algorithm will only be fully utilised if the inputs can take on all possible values for any given input length.

For example, ASCII or ISO text, certain parts of the input range -- many of the control characters <32; and characters >126 -- will not appear in the inputs, so for any given length, the range of inputs to the hashing algorithm is biased. It stand to reason that the outputs will similarly biased and the full range of the hash values will not be produced.

It is also the case that for any given input language, there are some character combinations that will never appear in normal text -- eg. ZXZXZXZXZXZXZXZXZXZ -- hence the inputs, and thus outputs will be further biased.

For this particular part of the exercise, I'm more concerned with the collision detection mechanism than the vagaries of the hashing.

But thank you for raising the issue. I may well contact you later for the details of your SimCRC64 algorithm.

(*)Note: I am aware that MD5 is probably far from perfect.


With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

The start of some sanity?

Replies are listed 'Best First'.
Re^3: [OT] The statistics of hashing.
by flexvault (Monsignor) on Apr 02, 2012 at 08:45 UTC

    BrowserUk,

      ...ASCII or ISO text, certain parts of the input range -- many of the control characters <32; and characters >126 -- will not appear...
    I hadn't thought about it but since the files were encrypted, more character sequences might appear.

    As far as the 'SimCRC64' algorithm, it was just a simple CRC routine. I don't have the actual code, but it was something like this.

    my $crc = crc64(\$output); ## Add crc check to output data sub crc64 ## Add crc check to output data { my $data = shift; my $crc = ""; my $len = length($$data); my $pos + = 0; while ( $pos < $len ) { $crc = $crc ^ ( substr($$data,$pos,8) ); $pos += 8; } return ( $crc ); }

    It was part of the test to see what the worst case would be. As I previously said, I didn't expect the results.

    Thank you

    "Well done is better than well said." - Benjamin Franklin

      I don't have the actual code, but it was something like this.

      Thanks for posting that.

      However, for my purposes -- deterministically generating a randomly distributed value -- it doesn't work well. With the MD5, every single bit change in the input generates an average of 64-bits change in the output -- which is near perfect.

      But this crc algorithm -- which was probably great for your purposes -- only generates a single bit change in the output for each single bit change in the input:

      #! perl -slw use strict; use Digest::MD5 qw[ md5 ]; sub crc64 { my $data = shift; my $crc = ""; my $len = length( $$data ); my $pos = 0; while ( $pos < $len ) { $crc = $crc ^ substr( $$data, $pos, 8 ); $pos += 8; } return ( $crc ); } our $C //= 16; my $text = join '', map chr( rand 256 ), 1 .. 16; my $md5text = md5( $text ); my $crctext = crc64( \$text ); my $copy = $text; my $md5changes = 0; my $crcchanges = 0; for my $bit ( 0 .. 16*8 -1 ) { vec( $copy, $bit, 1 ) ^= 1; ## toggle this bit my $md5copy = md5( $copy ); my $md5changed = unpack '%32B*', $md5text ^ $md5copy; $md5changes += $md5changed; my $crccopy = crc64( \$copy ); my $crcchanged = unpack '%32B*', $crctext ^ $crccopy; $crcchanges += $crcchanged; print "Toggling bit:$bit produced MD5[$md5changed] CRC[$crcchanged +] changes"; vec( $copy, $bit, 1 ) ^= 1; ## toggle it back } printf "Average MD5[changes: %.3f bits] CRC[changes: %.3f bits] per in +put bit changed\n", $md5changes / ( 16*8 ), $crcchanges / ( 16*8 ); __END__ C:\test>t-md5rand -C=4 Toggling bit:0 produced MD5[68] CRC[1] changes Toggling bit:1 produced MD5[52] CRC[1] changes Toggling bit:2 produced MD5[66] CRC[1] changes Toggling bit:3 produced MD5[75] CRC[1] changes Toggling bit:4 produced MD5[64] CRC[1] changes Toggling bit:5 produced MD5[61] CRC[1] changes Toggling bit:6 produced MD5[65] CRC[1] changes Toggling bit:7 produced MD5[64] CRC[1] changes Toggling bit:8 produced MD5[54] CRC[1] changes Toggling bit:9 produced MD5[58] CRC[1] changes Toggling bit:10 produced MD5[66] CRC[1] changes Toggling bit:11 produced MD5[74] CRC[1] changes Toggling bit:12 produced MD5[67] CRC[1] changes Toggling bit:13 produced MD5[76] CRC[1] changes Toggling bit:14 produced MD5[66] CRC[1] changes Toggling bit:15 produced MD5[57] CRC[1] changes Toggling bit:16 produced MD5[73] CRC[1] changes Toggling bit:17 produced MD5[56] CRC[1] changes Toggling bit:18 produced MD5[71] CRC[1] changes Toggling bit:19 produced MD5[61] CRC[1] changes Toggling bit:20 produced MD5[63] CRC[1] changes Toggling bit:21 produced MD5[64] CRC[1] changes Toggling bit:22 produced MD5[66] CRC[1] changes Toggling bit:23 produced MD5[60] CRC[1] changes Toggling bit:24 produced MD5[53] CRC[1] changes Toggling bit:25 produced MD5[64] CRC[1] changes Toggling bit:26 produced MD5[72] CRC[1] changes Toggling bit:27 produced MD5[72] CRC[1] changes Toggling bit:28 produced MD5[65] CRC[1] changes Toggling bit:29 produced MD5[68] CRC[1] changes Toggling bit:30 produced MD5[48] CRC[1] changes Toggling bit:31 produced MD5[61] CRC[1] changes Toggling bit:32 produced MD5[65] CRC[1] changes Toggling bit:33 produced MD5[57] CRC[1] changes Toggling bit:34 produced MD5[60] CRC[1] changes Toggling bit:35 produced MD5[65] CRC[1] changes Toggling bit:36 produced MD5[64] CRC[1] changes Toggling bit:37 produced MD5[58] CRC[1] changes Toggling bit:38 produced MD5[69] CRC[1] changes Toggling bit:39 produced MD5[64] CRC[1] changes Toggling bit:40 produced MD5[62] CRC[1] changes Toggling bit:41 produced MD5[64] CRC[1] changes Toggling bit:42 produced MD5[71] CRC[1] changes Toggling bit:43 produced MD5[61] CRC[1] changes Toggling bit:44 produced MD5[64] CRC[1] changes Toggling bit:45 produced MD5[61] CRC[1] changes Toggling bit:46 produced MD5[71] CRC[1] changes Toggling bit:47 produced MD5[73] CRC[1] changes Toggling bit:48 produced MD5[65] CRC[1] changes Toggling bit:49 produced MD5[56] CRC[1] changes Toggling bit:50 produced MD5[58] CRC[1] changes Toggling bit:51 produced MD5[61] CRC[1] changes Toggling bit:52 produced MD5[66] CRC[1] changes Toggling bit:53 produced MD5[60] CRC[1] changes Toggling bit:54 produced MD5[66] CRC[1] changes Toggling bit:55 produced MD5[63] CRC[1] changes Toggling bit:56 produced MD5[64] CRC[1] changes Toggling bit:57 produced MD5[63] CRC[1] changes Toggling bit:58 produced MD5[57] CRC[1] changes Toggling bit:59 produced MD5[66] CRC[1] changes Toggling bit:60 produced MD5[66] CRC[1] changes Toggling bit:61 produced MD5[59] CRC[1] changes Toggling bit:62 produced MD5[63] CRC[1] changes Toggling bit:63 produced MD5[72] CRC[1] changes Toggling bit:64 produced MD5[59] CRC[1] changes Toggling bit:65 produced MD5[64] CRC[1] changes Toggling bit:66 produced MD5[65] CRC[1] changes Toggling bit:67 produced MD5[64] CRC[1] changes Toggling bit:68 produced MD5[68] CRC[1] changes Toggling bit:69 produced MD5[68] CRC[1] changes Toggling bit:70 produced MD5[67] CRC[1] changes Toggling bit:71 produced MD5[61] CRC[1] changes Toggling bit:72 produced MD5[64] CRC[1] changes Toggling bit:73 produced MD5[69] CRC[1] changes Toggling bit:74 produced MD5[73] CRC[1] changes Toggling bit:75 produced MD5[68] CRC[1] changes Toggling bit:76 produced MD5[57] CRC[1] changes Toggling bit:77 produced MD5[53] CRC[1] changes Toggling bit:78 produced MD5[59] CRC[1] changes Toggling bit:79 produced MD5[63] CRC[1] changes Toggling bit:80 produced MD5[74] CRC[1] changes Toggling bit:81 produced MD5[65] CRC[1] changes Toggling bit:82 produced MD5[73] CRC[1] changes Toggling bit:83 produced MD5[66] CRC[1] changes Toggling bit:84 produced MD5[62] CRC[1] changes Toggling bit:85 produced MD5[53] CRC[1] changes Toggling bit:86 produced MD5[55] CRC[1] changes Toggling bit:87 produced MD5[60] CRC[1] changes Toggling bit:88 produced MD5[61] CRC[1] changes Toggling bit:89 produced MD5[68] CRC[1] changes Toggling bit:90 produced MD5[69] CRC[1] changes Toggling bit:91 produced MD5[64] CRC[1] changes Toggling bit:92 produced MD5[66] CRC[1] changes Toggling bit:93 produced MD5[65] CRC[1] changes Toggling bit:94 produced MD5[66] CRC[1] changes Toggling bit:95 produced MD5[64] CRC[1] changes Toggling bit:96 produced MD5[50] CRC[1] changes Toggling bit:97 produced MD5[68] CRC[1] changes Toggling bit:98 produced MD5[59] CRC[1] changes Toggling bit:99 produced MD5[60] CRC[1] changes Toggling bit:100 produced MD5[65] CRC[1] changes Toggling bit:101 produced MD5[64] CRC[1] changes Toggling bit:102 produced MD5[48] CRC[1] changes Toggling bit:103 produced MD5[62] CRC[1] changes Toggling bit:104 produced MD5[66] CRC[1] changes Toggling bit:105 produced MD5[61] CRC[1] changes Toggling bit:106 produced MD5[63] CRC[1] changes Toggling bit:107 produced MD5[68] CRC[1] changes Toggling bit:108 produced MD5[70] CRC[1] changes Toggling bit:109 produced MD5[62] CRC[1] changes Toggling bit:110 produced MD5[57] CRC[1] changes Toggling bit:111 produced MD5[60] CRC[1] changes Toggling bit:112 produced MD5[68] CRC[1] changes Toggling bit:113 produced MD5[68] CRC[1] changes Toggling bit:114 produced MD5[49] CRC[1] changes Toggling bit:115 produced MD5[64] CRC[1] changes Toggling bit:116 produced MD5[55] CRC[1] changes Toggling bit:117 produced MD5[57] CRC[1] changes Toggling bit:118 produced MD5[57] CRC[1] changes Toggling bit:119 produced MD5[71] CRC[1] changes Toggling bit:120 produced MD5[70] CRC[1] changes Toggling bit:121 produced MD5[62] CRC[1] changes Toggling bit:122 produced MD5[70] CRC[1] changes Toggling bit:123 produced MD5[67] CRC[1] changes Toggling bit:124 produced MD5[52] CRC[1] changes Toggling bit:125 produced MD5[70] CRC[1] changes Toggling bit:126 produced MD5[73] CRC[1] changes Toggling bit:127 produced MD5[59] CRC[1] changes Average MD5[changes: 63.531 bits] CRC[changes: 1.000 bits] per input b +it changed

      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.

      The start of some sanity?

        BrowserUK,

        I had to download your code to figure out what you were doing, but now I know your interest in uniqueness was different than mine(i.e. project).

        Each of the test encrypted files was unique and we wanted an algorithm that would produce the lowest number of duplicate hashes for the different unique files. The statistics I showed was the number of duplicate hashes produced from unique files. Each hash was generated and then:

        ... $Dupes{$hash}++; ...
        Then we just counted the total number of keys with values greater than one.

        Your code was very interesting and quite a mind tester.

        Thank you

        "Well done is better than well said." - Benjamin Franklin

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://962893]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (3)
As of 2020-09-20 05:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    If at first I donít succeed, I Ö










    Results (118 votes). Check out past polls.

    Notices?