[hashcash] Re: updating Digest::Hashcash? (Re: Re: Digest::Hashcash)

  • From: Adam Back <adam@xxxxxxxxxxxxxxx>
  • To: Justin <justin-hashcash@xxxxxxxx>
  • Date: Mon, 6 Jun 2005 17:56:57 -0400

Here's a bigger patch that also creates version 1 stamps (and is able
to create either version 0 or version 1 as well as verify both).

One remaining thing concerning me is the random number generator.
rand(3) is not a good choice.  I'm not seeing anything convenient in
cpan...  TrulyRandom I don't like (not that convinced about clock
jitter randomness myself); theres another one by Vipul but its just an
interface to /dev/urandom -- which is fine, but if /dev/urandom is not
there won't help.  And there is another one based on openSSL.

My thought is just include the hashcash random.c file and use it.  It
works on linux (/dev/urandom) and on windows (CAPI random API) and in
other places using something moderately safe, certainly safer than
rand(3), especially if one uses the high res timer that
Digest::Hashcash already depends upon.

Thoughts?

(Also need to add some tests for v1 stamps and added methods in the
test script).

Adam

On Fri, Jun 03, 2005 at 02:23:23PM +0000, Justin wrote:
> This seems to accurately verify version 0 and version 1 stamps, and
> return proper timestamps and resource values (so long as the resource
> doesn't contain escaped colons - I don't remember whether that's allowed
> or not).
> 
> It perhaps ought to return 0 for bits, and null strings for
> timestamp/resource values, for those that don't exist or are invalid.

diff -c Digest-Hashcash-0.04/Changes Digest-Hashcash-0.03/Changes
*** Digest-Hashcash-0.04/Changes        2005-06-06 22:07:39.384994728 +0100
--- Digest-Hashcash-0.03/Changes        2005-03-03 17:23:59.000000000 +0000
***************
*** 1,12 ****
  Revision history for Perl extension Digest::Hashcash
  
- 0.04  Sat Jun  4 22:00:00 BST 2005
-       - changes from Jason to verify version 1 stamps
-       - more changes from Adam Back: code to create version 1 stamps;
-         associated methods for v1 stamps: extension(), version()
-       - create v1 stamps by default
-       - fix some bugs (hash method was ignoring arguments)
- 
  0.03  Thu Mar  3 18:00:52 CET 2005
        - generate more efficient code with gcc-3.4 and later.
          - change of contact address.
--- 1,5 ----
Only in Digest-Hashcash-0.04: Hashcash.1
diff -c Digest-Hashcash-0.04/Hashcash.pm Digest-Hashcash-0.03/Hashcash.pm
*** Digest-Hashcash-0.04/Hashcash.pm    2005-06-06 22:15:48.051706096 +0100
--- Digest-Hashcash-0.03/Hashcash.pm    2005-03-03 17:24:10.000000000 +0000
***************
*** 29,35 ****
  
  no warnings;
  
! $VERSION = 0.04;
  
  XSLoader::load Digest::Hashcash, $VERSION;
  
--- 29,35 ----
  
  no warnings;
  
! $VERSION = 0.03;
  
  XSLoader::load Digest::Hashcash, $VERSION;
  
***************
*** 76,98 ****
  
  =over 4
  
! =item size => 20
  
  The number of collisions, in bits. Every bit increases the time to create
  the token (and thus the cash) by two.
  
- =item vers => 1
- 
- Default version 1.  Can produce version 0 if required for backwards
- compatibility.
- 
  =item uid => ""
  
  A string used to make the token more unique (e.g. the senders address)
  and reduce token collisions. The string must only contain characters
  valid for the trial part of the token, e.g. uuencoded, base64 or
! e-mail-address-parts are useful here.  Deprecated: use extension field
! if required.
  
  =item extrarand => 0
  
--- 76,92 ----
  
  =over 4
  
! =item size => 18
  
  The number of collisions, in bits. Every bit increases the time to create
  the token (and thus the cash) by two.
  
  =item uid => ""
  
  A string used to make the token more unique (e.g. the senders address)
  and reduce token collisions. The string must only contain characters
  valid for the trial part of the token, e.g. uuencoded, base64 or
! e-mail-address-parts are useful here.
  
  =item extrarand => 0
  
***************
*** 116,150 ****
  Any additional parameters are interpreted the same way as arguments to
  C<new>.
  
! =item $prefix = $cipher->verify ($token)
  
! Version 0: Checks the given token and returns the number of collision
! bits.
! 
! Version 1: Returns 0 if stated value is more than the computed
! collision value, otherwise returns the stated stamp value.
  
  Any additional parameters are interpreted the same way as arguments to
  C<new>.
  
- =item $version = $cipher->version ($token)
- 
- Returns the version of the stamp (currently 0 or 1).
- 
  =item $resource = $cipher->resource ($token)
  
  Returns the resource part, or C<undef>.
  
! =item $tstamp = $cipher->timestamp ($token)
  
! Returns the timestamp part (in the same format as perls C<time>), or
  C<undef>.
  
- =item $extension = $cipher->extension ($token)
- 
- For Version 1 stamps Returns the extension part; for Version 0 stamps
- returns undef.
- 
  =back
  
  =cut
--- 110,134 ----
  Any additional parameters are interpreted the same way as arguments to
  C<new>.
  
! =item $prefix = $cipher->verify ($token [, param => value...]))
  
! Checks the given token and returns true if the token has the minimum
! number of prefix bits, or false otherwise.  The value returned is actually
! the number of collisions, so to find the number of collisions bits specify
! C<< collisions => 0 >>.
  
  Any additional parameters are interpreted the same way as arguments to
  C<new>.
  
  =item $resource = $cipher->resource ($token)
  
  Returns the resource part, or C<undef>.
  
! =item $tstamp = $ciper->timestamp ($token)
  
! Returns the timestamp part (in the same format as perl's C<time>), or
  C<undef>.
  
  =back
  
  =cut
***************
*** 157,208 ****
  
  sub hash {
     my $self = shift;
!    my $resource = shift;
!    my %arg = ( vers => 1, %$self, resource => $resource, @_ );
  
!    &_gentoken(@arg{qw(size vers timestamp resource extension uid extrarand)});
  }
  
  sub verify {
     my ($self, $token) = (shift, shift);
  
     my $prefix = &_prefixlen($token);
  
!    if ($token =~ /^0:/) {
!       return $prefix >= 0 ? $prefix : 0;
!    } elsif ($token =~ /^1:/) {
!       ($ver, $bits, $ts, $res, $ext, $junk, $count) = split(':', $token, 7);
!       return $prefix >= $bits ? $bits : 0;
!    }
!    else { return undef; }
  }
  
  sub resource {
     my ($self, $token) = @_;
  
!    if ($token =~ /^0:/) {
!       ($ver, $ts, $res, $rand) = split(':', $token, 4);
!    }
!    elsif ($token =~ /^1:/) {
!       ($ver, $bits, $ts, $res, $ext, $junk, $count) = split(':', $token, 7);
!    }
!    else { return undef; }
!    return $res;
  }
  
  sub timestamp {
     my ($self, $token) = @_;
  
!    if ($token =~ /^0:/) {
!       ($ver, $ts, $res, $rand) = split(':', $token, 4);
!    }
!    elsif ($token =~ /^1:/) {
!       ($ver, $bits, $ts, $res, $ext, $junk, $count) = split(':', $token, 7);
!    }
!    else { return undef; }
  
     my ($y, $m, $d, $H, $M, $S);
!    local $_ = $ts;
     $y = /\G(\d\d)/gc ? $1 : return undef;
     $m = /\G(\d\d)/gc ? $1 : 1;
     $d = /\G(\d\d)/gc ? $1 : 1;
--- 141,179 ----
  
  sub hash {
     my $self = shift;
!    my %arg = (%$self, resource => @_);
  
!    &_gentoken(@arg{qw(size timestamp resource uid extrarand)});
  }
  
  sub verify {
     my ($self, $token) = (shift, shift);
+    my %arg = (%$self, @_);
  
     my $prefix = &_prefixlen($token);
  
!    $prefix < $arg{size}
!       ? undef
!       : $prefix;
  }
  
  sub resource {
     my ($self, $token) = @_;
  
!    $token =~ /^\d+:\d*:(.*):/
!       or return undef;
! 
!    return $1;
  }
  
  sub timestamp {
     my ($self, $token) = @_;
  
!    $token =~ /^\d+:(\d*):.*:/
!       or return undef;
  
     my ($y, $m, $d, $H, $M, $S);
!    local $_ = $1;
     $y = /\G(\d\d)/gc ? $1 : return undef;
     $m = /\G(\d\d)/gc ? $1 : 1;
     $d = /\G(\d\d)/gc ? $1 : 1;
***************
*** 213,241 ****
     return timegm $S, $M, $H, $d, $m - 1, $y;
  }
  
- sub extension { 
-    my ($self, $token) = @_;
- 
-    if ($token =~ /^0:/) {
-       return undef;
-    }
-    elsif ($token =~ /^1:/) {
-       ($ver, $bits, $ts, $res, $ext, $junk, $count) = split(':', $token, 7);
-    }
-    else { return undef; }
-    return $ext;
- }
- 
- sub version {
-    my ($self, $token) = @_;
- 
-    if ($token =~ /^0:/) {
-       return 0;
-    } elsif ($token =~ /^1:/) {
-       return 1;
-    }
-    else { return undef; }
- }
  =head1 SEE ALSO
  
  L<http://www.hashcash.org>.
--- 184,189 ----
***************
*** 254,256 ****
--- 202,205 ----
  =cut
  
  1;
+ 
diff -c Digest-Hashcash-0.04/Hashcash.xs Digest-Hashcash-0.03/Hashcash.xs
*** Digest-Hashcash-0.04/Hashcash.xs    2005-06-06 21:30:00.664372456 +0100
--- Digest-Hashcash-0.03/Hashcash.xs    2005-03-03 16:56:51.000000000 +0000
***************
*** 302,317 ****
             : zprefix (sha_info->digest[1]) + 32;
  }
  
! #define TRIALCHAR 
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789+/"
! 
! /* sizeof includes \0 */
! #define TRIALLEN ( sizeof (TRIALCHAR) -1 ) 
  
  static char       nextenc[256];
  
  static char rand_char ()
  {
!   return TRIALCHAR[rand () % TRIALLEN];
  }
  
  typedef double (*NVTime)(void);
--- 302,314 ----
             : zprefix (sha_info->digest[1]) + 32;
  }
  
! #define TRIALCHAR 
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!#$%&()*+,-./;<=>?@[]{}^_|"
  
  static char       nextenc[256];
  
  static char rand_char ()
  {
!   return TRIALCHAR[rand () % sizeof (TRIALCHAR)];
  }
  
  typedef double (*NVTime)(void);
***************
*** 338,345 ****
  {
     int i;
  
!    for (i = 0; i < TRIALLEN; i++)
!      nextenc[TRIALCHAR[i]] = TRIALCHAR[(i + 1) % TRIALLEN];
  }
  
  PROTOTYPES: ENABLE
--- 335,342 ----
  {
     int i;
  
!    for (i = 0; i < sizeof (TRIALCHAR); i++)
!      nextenc[TRIALCHAR[i]] = TRIALCHAR[(i + 1) % sizeof (TRIALCHAR)];
  }
  
  PROTOTYPES: ENABLE
***************
*** 378,414 ****
          RETVAL
  
  SV *
! _gentoken (int size, int vers, IV timestamp, char *resource, char* extension 
= "", char *trial = "", int extrarand = 0)
        CODE:
  {
          SHA_INFO ctx1, ctx;
          char *token, *seq, *s;
!         int toklen, i, j;
          time_t tstamp = timestamp ? timestamp : time (0);
          struct tm *tm = gmtime (&tstamp);
  
!       if ( vers == 0 ) {
!           New (0, token,
!                1 + 1                    // version
!                + 12 + 1                 // time field sans century
!                + strlen (resource) + 1  // ressource
!                + strlen (trial) + extrarand + 8 + 1 // trial
!                + 1,
!                char);
!       } else if ( vers == 1 ) {
!           New (0, token,
!                1 + 1                    // version
!              + ((size > 9) ? 2 : 1) + 1 // bits
!                + 12 + 1                 // time field sans century
!                + strlen (resource) + 1  // resource
!              + strlen (extension) + 1 // extension
!                + strlen (trial) + extrarand + 12 + 1 // trial
!              + 16 + 1                 // count
!                + 1,
!                char);
!       } else {
!         croak ("unsupported version");
!       }
  
          if (!token)
            croak ("out of memory");
--- 375,396 ----
          RETVAL
  
  SV *
! _gentoken (int size, IV timestamp, char *resource, char *trial = "", int 
extrarand = 0)
        CODE:
  {
          SHA_INFO ctx1, ctx;
          char *token, *seq, *s;
!         int toklen, i;
          time_t tstamp = timestamp ? timestamp : time (0);
          struct tm *tm = gmtime (&tstamp);
  
!         New (0, token,
!              1 + 1                    // version
!              + 12 + 1                 // time field sans century
!              + strlen (resource) + 1  // ressource
!              + strlen (trial) + extrarand + 8 + 1 // trial
!              + 1,
!              char);
  
          if (!token)
            croak ("out of memory");
***************
*** 416,433 ****
          if (size > 64)
            croak ("size must be <= 64 in this implementation\n");
  
!       again:  /* try again */
!       if ( vers == 0 ) { 
!           toklen = sprintf (token, "%d:%02d%02d%02d%02d%02d%02d:%s:%s",
                            0, tm->tm_year % 100, tm->tm_mon + 1, tm->tm_mday,
                            tm->tm_hour, tm->tm_min, tm->tm_sec,
                            resource, trial);
-       } else {
-           toklen = sprintf (token,"%d:%d:%02d%02d%02d%02d%02d%02d:%s:%s:%s",
-                           1, size, tm->tm_year % 100, tm->tm_mon + 1, 
-                         tm->tm_mday,tm->tm_hour, tm->tm_min, tm->tm_sec,
-                           resource, extension, trial);
-         }
  
          if (toklen > 8000)
            croak ("token length must be <= 8000 in this implementation\n");
--- 398,407 ----
          if (size > 64)
            croak ("size must be <= 64 in this implementation\n");
  
!         toklen = sprintf (token, "%d:%02d%02d%02d%02d%02d%02d:%s:%s",
                            0, tm->tm_year % 100, tm->tm_mon + 1, tm->tm_mday,
                            tm->tm_hour, tm->tm_min, tm->tm_sec,
                            resource, trial);
  
          if (toklen > 8000)
            croak ("token length must be <= 8000 in this implementation\n");
***************
*** 436,496 ****
          while (toklen < i)
            token[toklen++] = rand_char ();
  
-       if ( vers == 1 ) {
-         i +=  16;
-           while (toklen < i)
-             token[toklen++] = rand_char ();
-         token[toklen++] = ':';
-       }
- 
          sha_init (&ctx1);
          sha_update (&ctx1, token, toklen);
  
          seq = token + toklen;
!         if ( vers == 0 ) {
!           i += 16;
!           while (toklen < i)
!             token[toklen++] = rand_char ();
! 
!           for (;;)
!             {  // this "optimization" can help a lot for longer resource 
strings
!               ctx = ctx1; 
!               sha_update (&ctx, seq, 16);
!               i = sha_final (&ctx);
! 
!               if (i >= size)
!               goto done;
! 
!               s = seq;
!               do {
!                 *s = nextenc [*s];
!               } while (*s++ == 'a');
!             }
!         } else {
!         for ( j = 1; j <= 12; j++ ) 
!             {
!             memset (seq, 'a', j);
!             seq[j] = '\0';
!             s = seq+j-1;
!             for ( ; s-seq >= 0; ) {
!               s = seq+j-1;
!               ctx = ctx1;
!               sha_update (&ctx, seq, j);
!               i = sha_final (&ctx);
!               
!               if (i >= size) { 
!                 toklen += j;
!                 goto done; 
!               }
! 
!               do {
!                 *s = nextenc [*s];
!               } while ( *s == 'a' && s-- && s-seq >=0 );
!             }
!             }
!         goto again;
!         }
!       done:
          RETVAL = newSVpvn (token, toklen);
  }
        OUTPUT:
--- 410,438 ----
          while (toklen < i)
            token[toklen++] = rand_char ();
  
          sha_init (&ctx1);
          sha_update (&ctx1, token, toklen);
  
          seq = token + toklen;
!         i +=  8;
!         while (toklen < i)
!           token[toklen++] = rand_char ();
! 
!         for (;;)
!           {
!             ctx = ctx1; // this "optimization" can help a lot for longer 
resource strings
!             sha_update (&ctx, seq, 8);
!             i = sha_final (&ctx);
! 
!             if (i >= size)
!               break;
! 
!             s = seq;
!             do {
!               *s = nextenc [*s];
!             } while (*s++ == 'a');
!           }
! 
          RETVAL = newSVpvn (token, toklen);
  }
        OUTPUT:
***************
*** 510,512 ****
--- 452,456 ----
  }
        OUTPUT:
        RETVAL
+ 
+ 
Common subdirectories: Digest-Hashcash-0.04/t and Digest-Hashcash-0.03/t

Other related posts: