Skip to content

Instantly share code, notes, and snippets.

@DrI-T

DrI-T/README.md

Last active July 11, 2021 16:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save DrI-T/8748be59087e244f916618ac2d66ae3b to your computer and use it in GitHub Desktop.
Save DrI-T/8748be59087e244f916618ac2d66ae3b to your computer and use it in GitHub Desktop.
Download ZIP
hashcash (original)
Raw
README.md

README for hashcash

gpg --verify hashcash.tgz.sig 
gpg --search-keys=3E7BCAA828B24551
curl -s https://keyserver.ubuntu.com/pks/lookup?search=3E7BCAA828B24551&fingerprint=on&op=index
curl -s https://pgp.uni-mainz.de/pks/lookup?op=index&search=3E7BCAA828B24551
curl -S http://pgpkeys.eu:11371/pks/lookup?search=3E7BCAA828B24551&fingerprint=on&op=index
# not found !
Raw
readme.txt
------------------------------------------------------------------------
The implementation is available here:
http://www.dcs.ex.ac.uk/~aba/hashcash/
------------------------------------------------------------------------
Hash Cash
A partial hash collision based postage scheme
Hash cash is payment in burnt CPU cycles by calculating n-bit partial hash
collisions on chosen texts.
The idea of using partial hashes is that they can be made arbitrarily
expensive to compute (by choosing the desired number of bits of collision),
and yet can be verified instantly. This can be used as the basis for an
ecash system measured in burnt CPU cycles. Such cash systems can be used to
throttle systematic abuses of un-metered internet resources.
Take as an example spam, where a user abuses the un-metered nature of email
to send out millions of emails. The most common form of spam is commercial
spam, where the user is hoping to make a profit. As the incremental costs of
sending more emails to the spammer are almost zero, he can still make a
profit even with a success rate of 0.0001 %. The unfortunate side-effect of
this is that many people are annoyed by advertisements they are
uninterested, and unlikely to be, interested in. Also on a global scale use
of bandwidth and CPU resources is wasted. The spam recipients time is wasted
as well, and in the case of people using commercial service providers, some
recipients have metered phone calls, and some service providers charge
hourly rates for connection time.
Hash cash coins
Hash cash is denominated in the bit length of the partial hash collisions.
One bit longer is twice as expensive to compute (on average). By choosing an
appropriate denomination of hash collision we can create a system of
metering which does not pose a problem to the normal sender, but which
becomes expensive for large mass mailings.
For example, my workstation is able to test 27,000 hashes per second. A 19
bit hash collision takes on average 20 seconds to produce at this rate. If I
am charged by recipients a 19 bit hash for each email I send, I can only
usefully send 4320 mails per day.
This should be more than adequate for the normal user, but could easily ruin
a spammers chances of breaking even with his low rate of success. This
should cause spammers to either give up sending spam, or to work hard on
increasing the accuracy of their direct marketing database, either option
being is a net positive result.
Integration of hash cash net software
The recipient's service provider's SMTP server could be modified to discard,
or bounce messages with insufficient hash cash. Notification of the amount
of hashcash required could be part of the bounce message. Alternatively the
user could use the hashcash client as a filter from his .forward file. If
the system administrator, or the user decides that they are still getting
spam with the current postage charge, they increase the hashcash charge for
receipt.
Hashcash suffers from a high rate of inflation: machines get faster every
year. In the longer term it may be necessary to increase the hash collision
postage rate by a couple of bits or so a year.
For mailing lists which have a need to send many emails (50 messages/ day x
1000 subscribers = 50000 emails / day) the requirement to include hash cash
tokens may become expensive. To solve this problem subscribers should put
the mailing list address in a postage-free recipients list.
Anonymity issues
Other uses of hash cash include charging for use of anonymous remailer
resources. For non-replyable remailer services a hash cash postage payment
must be included for each hop of the remailer network. The remailers may
wish to charge higher postage if they are the exit (last) remailer in the
chain. This reflects the fact that the exit remailer may incur subsequent
overheads on the senders behalf, such as receiving attempted replies by
people not realizing that it was an anonymous post. Another overhead might
be the remailer operators time in dealing with queries about the remailers
services from users unfamiliar with remailers, and surprised to find no
working reply address.
For longer term services such as two way nym-server accounts a larger
denomination hash collision could be used as a subscription for a given
period to reflect the resources consumed by the remailer.
Traditional payment systems which are traceable are not appropriate where
privacy must be maintained at the same time as enabling providing protection
from systematic abuse of un-metered resources. David Chaum's digicash
payment system which is an example of a privacy preserving ecash system. I
am very keen on seeing digicash succeed as the main net payment system
because of it's privacy preserving features.
Migration path to digicash
Digicash support can be combined with the hashcash client, thus providing a
smooth migration path to postage denominated in digicash. The client could
be set up so that either form of payment form would be accepted. Advantages
of this dual currency approach are:
* Hashcash may provide a stop gap measure until digicash becomes more
widely accepted and used
* Hashcash is free, all you've got to do is burn some cycles on your PC.
It is in keeping with net culture of free discourse, where the
financially challenged can duke it out with millionaires, retired
government officials, etc. on equal terms. For this reason it would be
desirable to retain hashcash as an alternative even if digicash becomes
pervasive.
* Hashcash may provide us with a fall back method for controlling access
to un-metered resources while preserving anonymity if digicash turns
sour (gets outlawed or required to escrow user identities).
The advantages of digicash, is that it actually compensates the recipient
for resources used. For example the operator of a popular remailer can use
the revenue generated to upgrade equipment to cope with the overhead.
Popular individuals (media-celebrities), or individuals whose time is
valuable to themselves can set the postage higher to discourage emails of a
trivial nature, or in the extreme case (media celebrities) hire a secretary
with the revenues generated to deal with the email, and filter by given
criteria.
Other related ecash systems
Another payment systems based on partial hash collisions is Ron Rivest and
Adi Shamir's MicroMint payment system. Their paper discusses using k-way
hash collisions to offer a redeemable micro payment system for accessing web
pages. A key feature of the MicroMint system is that it involves a
centralized mint which must purchase special purpose hardware, to overcome a
threshold in the generation of k-way hash functions. The choice of a high
threshold makes it uneconomical to produce a competing mint to steal the
redemption values.
Implementation
A first cut implementation of these ideas can be fetched from here:
* hashcash.tgz
* PGP signature of hashcash.tgz
I will describe what the implementation allows by example, using the program
so you can follow along if you wish.
There is an integrated partial hash collision generator (hashcash mint) and
remailer plug-in. The remailer plug-in should be easy to hook into type I
remailers. type-II or nym-server would require modifying the mixmaster
client / remailer, the code has been designed to make this relatively easy
to do, and link directly into mixmaster, or alpha or new-nym.
Compiling
% gcc -O6 -c *.c
% gcc -o hashcash hashcash.o sha1.o timer.o
% gcc -o sha1 sha1file.o sha1.o
% gcc -o sha1test sha1test.o sha1.o timer.o
%
The functions provided by the program are
Run with no arguments and it prints a list of flags and terse usage
instructions.
Speed test:
% hashcash -t
speed: 7218 hashes per sec
%
This tells you the number of hashes it can search per second. Version 0.3
added a fast SHA1, and other speed enhancements, so the client is now 4 x
faster. The speed is not actually important as such, but it is good to have
a fast implementation, because spammers will have incentives to heavily
optimize the code. By starting with a well optimized client there is little
room for additional speedups to be found by spammers.
Estimate time required to find 17-bit partial hash collision:
% hashcash -t -17
speed: 7274 hashes per sec
find: 17 bit partial sha1 collision
estimate: 9 seconds
%
(varies quite widely from estimated time)
Calculate a 17 bit collision on string "flame"
(flame is a now dead remailer):
% hashcash -17 flame
speed: 7274 hashes per sec
find: 17 bit partial sha1 collision
collision: 09948flame356018443
tries: 57450
%
The collision is actually found on the hash of the date since Jan 1 1970 in
days (5 digit, leading zero filled) and string given.
So the collision is found on:
% echo -n 09948flame | sha1
fbbea210abafe3e72afe7849eaea2052e309e017
%
The collision that was found can be seen manually as the collision is
constrained to be the MSbits of the digest:
% echo -n 09948flame356018443 | sha1
fbbead76da651cf856f7466fed9624d3ada061d9
%
You can manually see that the first 20 bits match. (Note we asked for a 17
bit hash, but it generates a 17 bit or larger hash. We just got lucky and
got an extra 3 bits, which would happen about 1 time in 8).
The hashcash client can also report on a collision:
% hashcash flame 09948flame356018443
collision: 20 bits
%
You can check on the validity period as compared to today's date:
% hashcash flame 09948flame356018443 28
validity: 28 days remaining
collision: 20 bits
%
You can check that a hash has a requested number of bits:
% hashcash -25 flame 09948flame356018443
collision: 20 bits
required: 25 bits
rejected: too few bits
%
The exit status is set to failure if any of the tests fail: i.e. if there
are too few bits, or if you do a validity check and the hash has expired, or
isn't yet in it's validity period.
Double spending protection
You can also ask the hashcash client to remember collisions within a
selected validity period.
% hashcash -d -25 flame 09948flame356018443 28
validity: 28 days remaining
collision: 20 bits
required: 20 bits
database: not double spent
adding: 28 09948flame356018443
%
The collision will only be added if all the tests pass (in validity period,
or required number of bits). The exit status also tells you if the hash was
ok.
The database would grow indefinitely as the mailer accepted new payments, so
the validity period is stored in the database, and at the next use of the
database after the validity period expires, the collision will be discarded.
There is no need to keep expired collisions around because we wouldn't
accept it anyway because it's out of date, so who cares if we've previously
accepted it. A validity period of 0 means valid forever, and will never be
discarded from the database.
An example of double spending
A new test now that we have a value in the double spend database is whether
a hash has been presented before, so we reissue the above command and expect
the hash collision to be rejected as already spent, because it is in the
database:
% hashcash -d -25 flame 09948flame356018443 28
validity: 28 days remaining
collision: 20 bits
required: 25 bits
rejected: too few bits
database: double spent
%
(exit status is set to failure, due to double spent cash)
That's it
It's very lightly tested, so if anything breaks let me know.
The hash search is reasonably fast (bar assembly language speedups).
It's got some inefficiencies in the double spending protection database
implementation, but working code comes first, efficiency later.
Adam
------------------------------------------------------------------------
Comments, html bugs to me (Adam Back) at <aba@dcs.ex.ac.uk>
Raw
announce.txt
To: cypherpunks@toad.com
Subject: [ANNOUNCE] hash cash postage implementation
From: Adam Back <aba@dcs.ex.ac.uk>
Date: Fri, 28 Mar 1997 16:52:26 GMT
Sender: owner-cypherpunks@toad.com
A partial hash collision based postage scheme
I've been talking about a partial hash collision based postage scheme
on the crypto lists for the last few days. The idea of using partial
hashes is that they can be made arbitrarily expensive to compute (by
choosing the desired number of bits of collision), and yet can be
verified instantly.
A first cut implementation of these ideas can be fetched from here:
* hashcash.tgz
* PGP signature of hashcash.tgz
I will describe what the implementation allows by example, using the program
so you can follow along if you wish.
There is an integrated partial hash collision generator (hashcash mint) and
remailer plug-in. The remailer plug-in should be easy to hook into typeI
remailers. typeII or nymserver would require modifying the mixmaster
client/remailer, the code has been designed to make this relatively easy to
do, and link directly into mixmaster, or alpha or newnym.
Compiling
% gcc -O6 -c *.c
% gcc -o hashcash hashcash.o sha1.o
% gcc -o sha1 sha1file.o sha1.o
% gcc -o sha1test sha1test.o sha1.o
%
The functions provided by the program are
Run with no arguments and it prints a list of flags and terse usage
instructions.
Speed test:
% hashcash -t
speed: 7218 hashes per sec
%
This tells you the number of hashes it can search per second. (Note, the
implementation of sha1 it is using is not optimised, it is my reference
implementation. I have another speed freak sha1 implementation which needs
1/2 hrs work, and has the same interface, so I'll plug it in later. It's
commented in sha1.c).
Estimate time required to find 17-bit partial hash collision:
% hashcash -t -17
speed: 7274 hashes per sec
find: 17 bit partial sha1 collision
estimate: 9 seconds
%
(varies quite widely from estimated time)
Calculate a 17 bit collision on string "flame"
(flame is a now dead remailer):
% hashcash -17 flame
speed: 7274 hashes per sec
find: 17 bit partial sha1 collision
collision: 09948flame356018443
tries: 57450
%
The collision is actually found on the hash of the date since Jan 1 1970 in
days (5 digit leading zero filled) and string given.
So the collision is found on:
% echo -n 09948flame | sha1
fbbea210abafe3e72afe7849eaea2052e309e017
%
The collision that was found can be seen manually as the collision is
constrained to be the MSbits of the digest:
% echo -n 09948flame356018443 | sha1
fbbead76da651cf856f7466fed9624d3ada061d9
%
You can manually see that the first 20 bits match. (Note we asked for a 17
bit hash, but it generates a 17 bit or larger hash. We just got lucky and
got an extra 3 bits, which would happen about 1 time in 8).
The hashcash client can also report on a collision:
% hashcash flame 09948flame356018443
collision: 20 bits
%
You can check on the validity period as compared to todays date:
% hashcash flame 09948flame356018443 28
validity: 28 days remaining
collision: 20 bits
%
You can check that a hash has a requested number of bits:
% hashcash -25 flame 09948flame356018443
collision: 20 bits
required: 25 bits
rejected: too few bits
%
The exit status is set to failure if any of the tests fail: ie if there are
too few bits, or if you do a validity check and the hash has expired, or
isn't yet in it's validity period.
Double spending protection
You can also ask the hashcash client to remember collisions within a
selected validity period.
% hashcash -d -25 flame 09948flame356018443 28
validity: 28 days remaining
collision: 20 bits
required: 20 bits
database: not double spent
adding: 28 09948flame356018443
%
The collision will only be added if all the tests pass (in validity period,
required number of bits). The exit status also tells you if the hash was ok.
The database would grow indefinately as the mailer accepted new payments, so
the validity period is stored in the database, and at the next use of the
database after the validity period expires, the collision will be discarded.
There is no need to keep expired collisions around because we wouldn't
accetp it anyway because it's out of date, so who cares if we've previously
accepted it. A validity period of 0 means valid forever, and it will never
be discarded from the database.
An example of double spending
A new test now is whether a hash has been presented before, so we the above
command and expect it to be rejected as already spent, because it is in the
database:
% hashcash -d -25 flame 09948flame356018443 28
validity: 28 days remaining
collision: 20 bits
required: 25 bits
rejected: too few bits
database: double spent
%
(exit status is set to failure, due to double spent cash)
That's it
It's very lightly tested, so if anything breaks let me know.
It's got some inefficiencies in places, but working code comes first,
efficiency later.
(Also I have not tested my SHA1 implementation on a big endian machine, it
auto-detects byte endian-ness, theoretically).
Remailer applications discussed so far
* exit remailer postage per post
* spam filter on mail you receive, if it hasn't got a 20 bit hash, or 1c
digicash you have a program which bounces it with a notice explaining
the required postage, and where to obtain software from. This would put
spammers out of business overnight, as 1,000,000 x 20 = 100 MIP years
which is going to be more compute than they've got, and 1,000,000 x 1c
= $10,000 is going to be more than they are likely to make through
sales interest from the spam.
* good behaviour bond for nymserver users. The nymserver user pays the
nymserver (in a largish hash collision, or $25 digicash) for a
replyable nymserver account. They agree an contract with the penalty
clause that breaking the contract means the nymserver keeps the
digicash/collision, and disables the account. They user's identity
isn't known, but to join in again they have to pay up another large
hash collision or more digicash.
* there are lots of other ideas to play with.
How does this fit in with digicash
Digicash postage on remailers, and mail would be useful, however there are a
number of problems with digicash:
* It is more onerous to set up an account (form filling etc)
* Not many people have accounts
* It's only anonymous for the payer anonymous (and not anonymous for the
seller)
So my suggestion is that we have remailers which accept either hash
collision postage, or digicash postage. The advantages of this approach are:
* Hashcash may provide a stop gap measure until digicash becomes more
widely used
* Hashcash is free, all you've got to do is burn some cycles on your PC.
It is in keeping with net culture of free discourse, where the
financially challenged can duke it out with millionaires, retired
government officials, etc on equal terms.
* Hashcash may provide us with a fall back method for controling spam if
digicash goes sour (gets outlawed or required to escrow user
identities).
Any comments, code, etc gratefully received. A couple of remailers
alpha testing it would be nice also.
Adam
Raw
compiling
gcc -O6 -c *.c
gcc -o hashcash hashcash.o sha1.o endian.o timer.o
gcc -o sha1 sha1file.o sha1.o endian.o
gcc -o sha1test sha1test.o sha1.o endian.o timer.o
Raw
endian.c
#include "endian.h"
#include "types.h"
void swap_endian16( void* data, int len )
{
word16 tmp16;
byte* tmp16_as_bytes = (byte*) &tmp16;
word16* data_as_word16s = (word16*) data;
byte* data_as_bytes;
int i;
for ( i = 0; i < len; i++ )
{
tmp16 = data_as_word16s[ i ];
data_as_bytes = (byte*) &( data_as_word16s[ i ] );
data_as_bytes[ 0 ] = tmp16_as_bytes[ 1 ];
data_as_bytes[ 1 ] = tmp16_as_bytes[ 0 ];
}
}
void swap_endian32( void* data, int len )
{
word32 tmp32;
byte* tmp32_as_bytes = (byte*) &tmp32;
word32* data_as_word32s = (word32*) data;
byte* data_as_bytes;
int i;
for ( i = 0; i < len; i++ )
{
tmp32 = data_as_word32s[ i ];
data_as_bytes = (byte*) &( data_as_word32s[ i ] );
data_as_bytes[ 0 ] = tmp32_as_bytes[ 3 ];
data_as_bytes[ 1 ] = tmp32_as_bytes[ 2 ];
data_as_bytes[ 2 ] = tmp32_as_bytes[ 1 ];
data_as_bytes[ 3 ] = tmp32_as_bytes[ 0 ];
}
}
Raw
endian.h
#if !defined( _endian_h )
#define _endian_h
#if defined( __cplusplus )
extern "C" {
#endif
/* This defaults to a run time endian test. You can define BIG_ENDIAN
or LITTLE_ENDIAN appropriately to speed things up.
LITTLE_ENDIAN is the broken one: 80x86s, VAXs
BIG_ENDIAN is: most unix machines, RISC chips, 68000, etc
The endianess is stored in macros:
little_endian
and big_endian
These boolean values can be checked in your code in C expressions.
They should NOT be tested with conditional macro statements (#ifdef
etc). use BIG_ENDIAN and LITTLE_ENDIAN for this, if they are defined.
Careful use should ensure the compiler compiles out code where
possible
*/
#if defined( BIG_ENDIAN )
#define little_endian 0
#elif defined( LITTLE_ENDIAN )
#define little_endian 1
#else
#define little_endian ( (* (long*) "\1\0\0\0" ) == 1 )
#endif
#define big_endian ( ! little_endian )
void swap_endian16( void*, int );
void swap_endian32( void*, int );
#define make_big_endian32( data, len ) \
( little_endian ? swap_endian32( data, len ) : 0 )
#define make_big_endian16( data, len ) \
( little_endian ? swap_endian16( data, len ) : 0 )
#define BURN( x, n ) memset( x, '\0', n )
#if defined( __cplusplus )
}
#endif
#endif
Raw
fip180-1.txt
FIPS PUB 180-1
FEDERAL INFORMATION PROCESSING STANDARDS PUBLICATION
(Supersedes FIPS PUB 180 - 1993 May 11)
1995 April 17
U.S. DEPARTMENT OF COMMERCE/National Institute of Standards and Technology
SECURE HASH STANDARD
/*** NOTE: NOT OFFICIAL. HARD COPY IS THE OFFICIAL VERSION.
^ is used for exponentiation or superscript. ***/
CATEGORY: COMPUTER SECURITY
U.S. DEPARTMENT OF COMMERCE, Ronald H. Brown, Secretary
NATIONAL INSTITUTE OF STANDARDS AND TECHNOLOGY
Foreword
The Federal Information Processing Standards Publication Series
of the National Institute of Standards and Technology (NIST) is the
official series of publications relating to standards and guidelines
adopted and promulgated under the provisions of Section 111(d) of the
Federal Property and Administrative Services Act of 1949 as amended by
the Computer Security Act of 1987, Public Law 100-235. These mandates
have given the Secretary of Commerce and NIST important responsibilities
for improving the utilization and management of computer and related
telecommunications systems in the Federal Government. The NIST, through
the Computer Systems Laboratory, provides leadership, technical guidance,
and coordination of Government efforts in the development of standards
and guidelines in these areas.
Comments concerning Federal Information Processing Standards
Publications are welcomed and should be addressed to the Director,
Computer Systems Laboratory, National Institute of Standards and
Technology, Gaithersburg, MD 20899.
James H. Burrows, Director
Computer Systems Laboratory
Abstract
This standard specifies a Secure Hash Algorithm (SHA-1) which can
be used to generate a condensed representation of a message called a
message digest. The SHA-1 is required for use with the Digital Signature
Algorithm (DSA) as specified in the Digital Signature Standard (DSS) and
whenever a secure hash algorithm is required for Federal applications.
The SHA-1 is used by both the transmitter and intended receiver of a
message in computing and verifying a digital signature.
Key words: computer security; digital signatures; Federal Information
Processing Standard (FIPS); hash algorithm.
FIPS PUB 180-1
Federal Information
Processing Standards Publication 180-1
1995 APRIL 17
ANNOUNCING THE
SECURE HASH STANDARD
Federal Information Processing Standards Publications (FIPS PUBS) are
issued by the National Institute of Standards and Technology (NIST) after
approval by the Secretary of Commerce pursuant to Section 111(d) of the
Federal Property and Administrative Services Act of 1949 as amended by the
Computer Security Act of 1987, Public Law 100-235.
Name of Standard: Secure Hash Standard.
Category of Standard: Computer Security.
Explanation: This Standard specifies a Secure Hash Algorithm, SHA-1,
for computing a condensed representation of a message or a data file. When
a message of any length < 2^64 bits is input, the SHA-1 produces a 160-bit
output called a message digest. The message digest can then be input to
the Digital Signature Algorithm (DSA) which generates or verifies the
signature for the message. Signing the message digest rather than the
message often improves the efficiency of the process because the message
digest is usually much smaller in size than the message. The same hash
algorithm must be used by the verifier of a digital signature as was used
by the creator of the digital signature.
The SHA-1 is called secure because it is computationally infeasible to find
a message which corresponds to a given message digest, or to find two
different messages which produce the same message digest. Any change to a
message in transit will, with very high probability, result in a different
message digest, and the signature will fail to verify. SHA-1 is a technical
revision of SHA (FIPS 180). A circular left shift operation has been added
to the specifications in section 7, line b, page 9 of FIPS 180 and its
equivalent in section 8, line c, page 10 of FIPS 180. This revision improves
the security provided by this standard. The SHA-1 is based on principles
similar to those used by Professor Ronald L. Rivest of MIT when designing
the MD4 message digest algorithm ("The MD4 Message Digest Algorithm,"
Advances in Cryptology - CRYPTO '90 Proceedings, Springer-Verlag, 1991,
pp. 303-311), and is closely modelled after that algorithm.
Approving Authority: Secretary of Commerce.
Maintenance Agency: U.S. Department of Commerce, National Institute of
Standards and Technology, Computer Systems Laboratory.
Applicability: This standard is applicable to all Federal departments and
agencies for the protection of unclassified information that is not subject
to section 2315 of Title 10, United States Code, or section 3502(2) of Title
44, United States Code. This standard is required for use with the Digital
Signature Algorithm (DSA) as specified in the Digital Signature Standard
(DSS) and whenever a secure hash algorithm is required for Federal applica-
tions. Private and commercial organizations are encouraged to adopt and use
this standard.
Applications: The SHA-1 may be used with the DSA in electronic mail,
electronic funds transfer, software distribution, data storage, and other
applications which require data integrity assurance and data origin
authentication. The SHA-1 may also be used whenever it is necessary to
generate a condensed version of a message.
Implementations: The SHA-1 may be implemented in software, firmware,
hardware, or any combination thereof. Only implementations of the SHA-1
that are validated by NIST will be considered as complying with this
standard. Information about the requirements for validating implementations
of this standard can be obtained from the National Institute of Standards
and Technology, Computer Systems Laboratory, Attn: SHS Validation,
Gaithersburg, MD 20899.
Export Control: Implementations of this standard are subject to Federal
Government export controls as specified in Title 15, Code of Federal
Regulations, Parts 768 through 799. Exporters are advised to contact the
Department of Commerce, Bureau of Export Administration for more information.
Patents: Implementations of the SHA-1 in this standard may be covered
by U.S. and foreign patents.
Implementation Schedule: This standard becomes effective October 2, 1995.
Specifications: Federal Information Processing Standard (FIPS 180-1)
Secure Hash Standard (affixed).
Cross Index:
a. FIPS PUB 46-2, Data Encryption Standard.
b. FIPS PUB 73, Guidelines for Security of Computer Applications.
c. FIPS PUB 140-1, Security Requirements for Cryptographic Modules.
d. FIPS PUB 186, Digital Signature Standard.
e. Federal Informations Resources Management Regulations (FIRMR) subpart
201.20.303, Standards, and subpart 201.39.1002, Federal Standards.
Objectives: The objectives of this standard are to:
a. Specify the secure hash algorithm required for use with the Digital
Signature Standard (FIPS 186) in the generation and verification of
digital signatures;
b. Specify the secure hash algorithm to be used whenever a secure hash
algorithm is required for Federal applications; and
c. Encourage the adoption and use of the specified secure hash algorithm
by private and commercial organizations.
Qualifications: While it is the intent of this standard to specify a secure
hash algorithm, conformance to this standard does not assure that a particular
implementation is secure. The responsible authority in each agency or
department shall assure that an overall implementation provides an acceptable
level of security. This standard will be reviewed every five years in order
to assess its adequacy.
Waiver Procedure: Under certain exceptional circumstances, the heads of
Federal departments and agencies may approve waivers to Federal Information
Processing Standards (FIPS). The head of such agency may redelegate such
authority only to a senior official designated pursuant to section 3506(b)
of Title 44, United States Code. Waiver shall be granted only when:
a. Compliance with a standard would adversely affect the accomplishment of
the mission of an operator of a Federal computer system; or
b. Compliance with a standard would cause a major adverse financial impact
on the operator which is not offset by Government-wide savings.
Agency heads may act upon a written waiver request containing the information
detailed above. Agency heads may also act without a written waiver request
when they determine that conditions for meeting the standard cannot be met.
Agency heads may approve waivers only by a written decision which explains
the basis on which the agency head made the required finding(s). A copy of
each decision, with procurement sensitive or classified portions clearly
identified, shall be sent to: National Institute of Standards and Technology;
ATTN: FIPS Waiver Decisions, Technology Building, Room B-154, Gaithersburg,
MD 20899.
In addition, notice of each waiver granted and each delegation of authority
to approve waivers shall be sent promptly to the Committee on Government
Operations of the House of Representatives and the Committee on Government
Affairs of the Senate and shall be published promptly in the Federal Register.
When the determination on a waiver applies to the procurement of equipment
and/or services, a notice of the waiver determination must be published in
the Commerce Business Daily as a part of the notice of solicitation for
offers of an acquisition or, if the waiver determination is made after that
notice is published, by amendment to such notice.
A copy of the waiver, any supporting documents, the document approving the
waiver and any accompanying documents, with such deletions as the agency is
authorized and decides to make under 5 United States Code Section 552(b),
shall be part of the procurement documentation and retained by the agency.
Where to Obtain Copies of the Standard: Copies of this publication are for
sale by the National Technical Information Service, U.S. Department of
Commerce, Springfield, VA 22161. When ordering, refer to Federal Information
Processing Standards Publication 180-1 (FIPSPUB180-1), and identify the title.
When microfiche is desired, this should be specified. Prices are published by
NTIS in current catalogs and other issuances. Payment may be made by check,
money order, deposit account or charged to a credit card accepted by NTIS.
---------------------
Federal Information
Processing Standards Publication 180-1
1995 April 17
Specifications for the
SECURE HASH STANDARD
1. INTRODUCTION
The Secure Hash Algorithm (SHA-1) is required for use with the Digital
Signature Algorithm (DSA) as specified in the Digital Signature Standard
(DSS) and whenever a secure hash algorithm is required for federal applica-
tions. For a message of length < 2^64 bits, the SHA-1 produces a 160-bit
condensed representation of the message called a message digest. The message
digest is used during generation of a signature for the message. The SHA-1
is also used to compute a message digest for the received version of the
message during the process of verifying the signature. Any change to the
message in transit will, with very high probability, result in a different
message digest, and the signature will fail to verify.
The SHA-1 is designed to have the following properties: it is computationally
infeasible to find a message which corresponds to a given message digest, or
to find two different messages which produce the same message digest.
2. BIT STRINGS AND INTEGERS
The following terminology related to bit strings and integers will be used:
a. A hex digit is an element of the set {0, 1, ... , 9, A, ... , F}. A
hex digit is the representation of a 4-bit string. Examples: 7 = 0111,
A = 1010.
b. A word equals a 32-bit string which may be represented as a sequence of
8 hex digits. To convert a word to 8 hex digits each 4-bit string is
converted to its hex equivalent as described in (a) above. Example:
1010 0001 0000 0011 1111 1110 0010 0011 = A103FE23.
c. An integer between 0 and 2^32 - 1 inclusive may be represented as a word.
The least significant four bits of the integer are represented by the
right-most hex digit of the word representation. Example: the integer
291 = 2^8+2^5+2^1+2^0 = 256+32+2+1 is represented by the hex word,
00000123.
If z is an integer, 0 <= z < 2^64, then z = (2^32)x + y where
0 <= x < 2^32 and 0 <= y < 2^32. Since x and y can be represented as
words X and Y, respectively, z can be represented as the pair of words
(X,Y).
d. block = 512-bit string. A block (e.g., B) may be represented as a
sequence of 16 words.
3. OPERATIONS ON WORDS
The following logical operators will be applied to words:
a. Bitwise logical word operations
X AND Y = bitwise logical "and" of X and Y.
X OR Y = bitwise logical "inclusive-or" of X and Y.
X XOR Y = bitwise logical "exclusive-or" of X and Y.
NOT X = bitwise logical "complement" of X.
Example:
01101100101110011101001001111011
XOR 01100101110000010110100110110111
--------------------------------
= 00001001011110001011101111001100
b. The operation X + Y is defined as follows: words X and Y represent
integers x and y, where 0 <= x < 2^32 and 0 <= y < 2^32. For positive
integers n and m, let n mod m be the remainder upon dividing n by m.
Compute
z = (x + y) mod 2^32.
Then 0 <= z < 2^32. Convert z to a word, Z, and define Z = X + Y.
c. The circular left shift operation S^n(X), where X is a word and n is an
integer with 0 <= n < 32, is defined by
S^n(X) = (X << n) OR (X >> 32-n).
In the above, X << n is obtained as follows: discard the left-most n
bits of X and then pad the result with n zeroes on the right (the result
will still be 32 bits). X >> n is obtained by discarding the right-most
n bits of X and then padding the result with n zeroes on the left. Thus
S^n(X) is equivalent to a circular shift of X by n positions to the left.
4. MESSAGE PADDING
The SHA-1 is used to compute a message digest for a message or data file that
is provided as input. The message or data file should be considered to be a
bit string. The length of the message is the number of bits in the message
(the empty message has length 0). If the number of bits in a message is a
multiple of 8, for compactness we can represent the message in hex. The
purpose of message padding is to make the total length of a padded message a
multiple of 512. The SHA-1 sequentially processes blocks of 512 bits when
computing the message digest. The following specifies how this padding shall
be performed. As a summary, a "1" followed by m "0"s followed by a 64-bit
integer are appended to the end of the message to produce a padded message of
length 512 * n. The 64-bit integer is l, the length of the original message.
The padded message is then processed by the SHA-1 as n 512-bit blocks.
Suppose a message has length l < 2^64. Before it is input to the SHA-1, the
message is padded on the right as follows:
a. "1" is appended. Example: if the original message is "01010000", this
is padded to "010100001".
b. "0"s are appended. The number of "0"s will depend on the original length
of the message. The last 64 bits of the last 512-bit block are reserved
for the length l of the original message.
Example: Suppose the original message is the bit string
01100001 01100010 01100011 01100100 01100101.
After step (a) this gives
01100001 01100010 01100011 01100100 01100101 1.
Since l = 40, the number of bits in the above is 41 and 407 "0"s are
appended, making the total now 448. This gives (in hex)
61626364 65800000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000.
c. Obtain the 2-word representation of l, the number of bits in the original
message. If l < 2^32 then the first word is all zeroes. Append these
two words to the padded message.
Example: Suppose the original message is as in (b). Then l = 40 (note
that l is computed before any padding). The two-word representation of
40 is hex 00000000 00000028. Hence the final padded message is hex
61626364 65800000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000028.
The padded message will contain 16 * n words for some n > 0. The padded
message is regarded as a sequence of n blocks M(1) , M(2), ... , M(n), where
each M(i) contains 16 words and M(1) contains the first characters (or bits)
of the message.
5. FUNCTIONS USED
A sequence of logical functions f(0), f(1),..., f(79) is used in the SHA-1.
Each f(t), 0 <= t <= 79, operates on three 32-bit words B, C, D and produces
a 32-bit word as output. f(t;B,C,D) is defined as follows:
for words B, C, D,
f(t;B,C,D) = (B AND C) OR ((NOT B) AND D) ( 0 <= t <= 19)
f(t;B,C,D) = B XOR C XOR D (20 <= t <= 39)
f(t;B,C,D) = (B AND C) OR (B AND D) OR (C AND D) (40 <= t <= 59)
f(t;B,C,D) = B XOR C XOR D (60 <= t <= 79).
6. CONSTANTS USED
A sequence of constant words K(0), K(1), ... , K(79) is used in the SHA-1.
In hex these are given by
K(t) = 5A827999 ( 0 <= t <= 19)
K(t) = 6ED9EBA1 (20 <= t <= 39)
K(t) = 8F1BBCDC (40 <= t <= 59)
K(t) = CA62C1D6 (60 <= t <= 79).
7. COMPUTING THE MESSAGE DIGEST
The message digest is computed using the final padded message. The
computation uses two buffers, each consisting of five 32-bit words, and a
sequence of eighty 32-bit words. The words of the first 5-word buffer are
labeled A,B,C,D,E. The words of the second 5-word buffer are labeled H0, H1,
H2, H3, H4. The words of the 80-word sequence are labeled W(0), W(1),...,
W(79). A single word buffer TEMP is also employed.
To generate the message digest, the 16-word blocks M(1), M(2),..., M(n)
defined in Section 4 are processed in order. The processing of each M(i)
involves 80 steps.
Before processing any blocks, the H's are initialized as follows:
in hex,
H0 = 67452301
H1 = EFCDAB89
H2 = 98BADCFE
H3 = 10325476
H4 = C3D2E1F0.
Now M(1), M(2), ... , M(n) are processed. To process M(i), we proceed as
follows:
a. Divide M(i) into 16 words W(0), W(1), ... , W(15), where W(0) is the
left-most word.
b. For t = 16 to 79 let
W(t) = S^1(W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16)).
c. Let A = H0, B = H1, C = H2, D = H3, E = H4.
d. For t = 0 to 79 do
TEMP = S^5(A) + f(t;B,C,D) + E + W(t) + K(t);
E = D; D = C; C = S^30(B); B = A; A = TEMP;
e. Let H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D,
H4 = H4 + E.
After processing M(n), the message digest is the 160-bit string
represented by the 5 words
H0 H1 H2 H3 H4.
8. ALTERNATE METHOD OF COMPUTATION
The above assumes that the sequence W(0), ... , W(79) is implemented
as an array of eighty 32-bit words. This is efficient from the standpoint
of minimization of execution time, since the addresses of W(t-3), ... ,W(t-16)
in step (b) are easily computed. If space is at a premium, an alternative is
to regard { W(t) } as a circular queue, which may be implemented using an
array of sixteen 32-bit words W[0], ... W[15]. In this case, in hex let
MASK = 0000000F. Then processing of M(i) is as follows:
a. Divide M(i) into 16 words W[0], ... , W[15], where W[0] is the
left-most word.
b. Let A = H0, B = H1, C = H2, D = H3, E = H4.
c. For t = 0 to 79 do
s = t AND MASK;
if (t >= 16) W[s] = S^1(W[(s + 13) AND MASK] XOR W[(s + 8) AND MASK]
XOR W[(s + 2) AND MASK] XOR W[s]);
TEMP = S^5(A) + f(t;B,C,D) + E + W[s] + K(t);
E = D; D = C; C = S^30(B); B = A; A = TEMP;
d. Let H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D,
H4 = H4 + E.
9. COMPARISON OF METHODS
The methods of Sections 7 and 8 yield the same message digest. Although
using the method of Section 8 saves sixty-four 32-bit words of storage, it
is likely to lengthen execution time due to the increased complexity of the
address computations for the { W[t] } in step (c). Other computation methods
which give identical results may be implemented in conformance with the
standard.
APPENDIX A. A SAMPLE MESSAGE AND ITS MESSAGE DIGEST
This appendix is for informational purposes only and is not required to meet
the standard.
Let the message be the ASCII binary-coded form of "abc", i.e.,
01100001 01100010 01100011.
This message has length l = 24. In step (a) of Section 4, we append "1". In
step (b) we append 423 "0"s. In step (c) we append hex 00000000 00000018,
the 2-word representation of 24. Thus the final padded message consists of
one block, so that n = 1 in the notation of Section 4.
The initial hex values of {Hi} are
H0 = 67452301
H1 = EFCDAB89
H2 = 98BADCFE
H3 = 10325476
H4 = C3D2E1F0.
Start processing block 1. The words of block 1 are
W[0] = 61626380
W[1] = 00000000
W[2] = 00000000
W[3] = 00000000
W[4] = 00000000
W[5] = 00000000
W[6] = 00000000
W[7] = 00000000
W[8] = 00000000
W[9] = 00000000
W[10] = 00000000
W[11] = 00000000
W[12] = 00000000
W[13] = 00000000
W[14] = 00000000
W[15] = 00000018.
The hex values of A,B,C,D,E after pass t of the "for t = 0 to 79" loop
(step (d) of Section 7 or step (c) of Section 8) are
A B C D E
t = 0: 0116FC33 67452301 7BF36AE2 98BADCFE 10325476
t = 1: 8990536D 0116FC33 59D148C0 7BF36AE2 98BADCFE
t = 2: A1390F08 8990536D C045BF0C 59D148C0 7BF36AE2
t = 3: CDD8E11B A1390F08 626414DB C045BF0C 59D148C0
t = 4: CFD499DE CDD8E11B 284E43C2 626414DB C045BF0C
t = 5: 3FC7CA40 CFD499DE F3763846 284E43C2 626414DB
t = 6: 993E30C1 3FC7CA40 B3F52677 F3763846 284E43C2
t = 7: 9E8C07D4 993E30C1 0FF1F290 B3F52677 F3763846
t = 8: 4B6AE328 9E8C07D4 664F8C30 0FF1F290 B3F52677
t = 9: 8351F929 4B6AE328 27A301F5 664F8C30 0FF1F290
t = 10: FBDA9E89 8351F929 12DAB8CA 27A301F5 664F8C30
t = 11: 63188FE4 FBDA9E89 60D47E4A 12DAB8CA 27A301F5
t = 12: 4607B664 63188FE4 7EF6A7A2 60D47E4A 12DAB8CA
t = 13: 9128F695 4607B664 18C623F9 7EF6A7A2 60D47E4A
t = 14: 196BEE77 9128F695 1181ED99 18C623F9 7EF6A7A2
t = 15: 20BDD62F 196BEE77 644A3DA5 1181ED99 18C623F9
t = 16: 4E925823 20BDD62F C65AFB9D 644A3DA5 1181ED99
t = 17: 82AA6728 4E925823 C82F758B C65AFB9D 644A3DA5
t = 18: DC64901D 82AA6728 D3A49608 C82F758B C65AFB9D
t = 19: FD9E1D7D DC64901D 20AA99CA D3A49608 C82F758B
t = 20: 1A37B0CA FD9E1D7D 77192407 20AA99CA D3A49608
t = 21: 33A23BFC 1A37B0CA 7F67875F 77192407 20AA99CA
t = 22: 21283486 33A23BFC 868DEC32 7F67875F 77192407
t = 23: D541F12D 21283486 0CE88EFF 868DEC32 7F67875F
t = 24: C7567DC6 D541F12D 884A0D21 0CE88EFF 868DEC32
t = 25: 48413BA4 C7567DC6 75507C4B 884A0D21 0CE88EFF
t = 26: BE35FBD5 48413BA4 B1D59F71 75507C4B 884A0D21
t = 27: 4AA84D97 BE35FBD5 12104EE9 B1D59F71 75507C4B
t = 28: 8370B52E 4AA84D97 6F8D7EF5 12104EE9 B1D59F71
t = 29: C5FBAF5D 8370B52E D2AA1365 6F8D7EF5 12104EE9
t = 30: 1267B407 C5FBAF5D A0DC2D4B D2AA1365 6F8D7EF5
t = 31: 3B845D33 1267B407 717EEBD7 A0DC2D4B D2AA1365
t = 32: 046FAA0A 3B845D33 C499ED01 717EEBD7 A0DC2D4B
t = 33: 2C0EBC11 046FAA0A CEE1174C C499ED01 717EEBD7
t = 34: 21796AD4 2C0EBC11 811BEA82 CEE1174C C499ED01
t = 35: DCBBB0CB 21796AD4 4B03AF04 811BEA82 CEE1174C
t = 36: 0F511FD8 DCBBB0CB 085E5AB5 4B03AF04 811BEA82
t = 37: DC63973F 0F511FD8 F72EEC32 085E5AB5 4B03AF04
t = 38: 4C986405 DC63973F 03D447F6 F72EEC32 085E5AB5
t = 39: 32DE1CBA 4C986405 F718E5CF 03D447F6 F72EEC32
t = 40: FC87DEDF 32DE1CBA 53261901 F718E5CF 03D447F6
t = 41: 970A0D5C FC87DEDF 8CB7872E 53261901 F718E5CF
t = 42: 7F193DC5 970A0D5C FF21F7B7 8CB7872E 53261901
t = 43: EE1B1AAF 7F193DC5 25C28357 FF21F7B7 8CB7872E
t = 44: 40F28E09 EE1B1AAF 5FC64F71 25C28357 FF21F7B7
t = 45: 1C51E1F2 40F28E09 FB86C6AB 5FC64F71 25C28357
t = 46: A01B846C 1C51E1F2 503CA382 FB86C6AB 5FC64F71
t = 47: BEAD02CA A01B846C 8714787C 503CA382 FB86C6AB
t = 48: BAF39337 BEAD02CA 2806E11B 8714787C 503CA382
t = 49: 120731C5 BAF39337 AFAB40B2 2806E11B 8714787C
t = 50: 641DB2CE 120731C5 EEBCE4CD AFAB40B2 2806E11B
t = 51: 3847AD66 641DB2CE 4481CC71 EEBCE4CD AFAB40B2
t = 52: E490436D 3847AD66 99076CB3 4481CC71 EEBCE4CD
t = 53: 27E9F1D8 E490436D 8E11EB59 99076CB3 4481CC71
t = 54: 7B71F76D 27E9F1D8 792410DB 8E11EB59 99076CB3
t = 55: 5E6456AF 7B71F76D 09FA7C76 792410DB 8E11EB59
t = 56: C846093F 5E6456AF 5EDC7DDB 09FA7C76 792410DB
t = 57: D262FF50 C846093F D79915AB 5EDC7DDB 09FA7C76
t = 58: 09D785FD D262FF50 F211824F D79915AB 5EDC7DDB
t = 59: 3F52DE5A 09D785FD 3498BFD4 F211824F D79915AB
t = 60: D756C147 3F52DE5A 4275E17F 3498BFD4 F211824F
t = 61: 548C9CB2 D756C147 8FD4B796 4275E17F 3498BFD4
t = 62: B66C020B 548C9CB2 F5D5B051 8FD4B796 4275E17F
t = 63: 6B61C9E1 B66C020B 9523272C F5D5B051 8FD4B796
t = 64: 19DFA7AC 6B61C9E1 ED9B0082 9523272C F5D5B051
t = 65: 101655F9 19DFA7AC 5AD87278 ED9B0082 9523272C
t = 66: 0C3DF2B4 101655F9 0677E9EB 5AD87278 ED9B0082
t = 67: 78DD4D2B 0C3DF2B4 4405957E 0677E9EB 5AD87278
t = 68: 497093C0 78DD4D2B 030F7CAD 4405957E 0677E9EB
t = 69: 3F2588C2 497093C0 DE37534A 030F7CAD 4405957E
t = 70: C199F8C7 3F2588C2 125C24F0 DE37534A 030F7CAD
t = 71: 39859DE7 C199F8C7 8FC96230 125C24F0 DE37534A
t = 72: EDB42DE4 39859DE7 F0667E31 8FC96230 125C24F0
t = 73: 11793F6F EDB42DE4 CE616779 F0667E31 8FC96230
t = 74: 5EE76897 11793F6F 3B6D0B79 CE616779 F0667E31
t = 75: 63F7DAB7 5EE76897 C45E4FDB 3B6D0B79 CE616779
t = 76: A079B7D9 63F7DAB7 D7B9DA25 C45E4FDB 3B6D0B79
t = 77: 860D21CC A079B7D9 D8FDF6AD D7B9DA25 C45E4FDB
t = 78: 5738D5E1 860D21CC 681E6DF6 D8FDF6AD D7B9DA25
t = 79: 42541B35 5738D5E1 21834873 681E6DF6 D8FDF6AD.
Block 1 has been processed. The values of {Hi} are
H0 = 67452301 + 42541B35 = A9993E36
H1 = EFCDAB89 + 5738D5E1 = 4706816A
H2 = 98BADCFE + 21834873 = BA3E2571
H3 = 10325476 + 681E6DF6 = 7850C26C
H4 = C3D2E1F0 + D8FDF6AD = 9CD0D89D.
Message digest = A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D
APPENDIX B. A SECOND SAMPLE MESSAGE AND ITS MESSAGE DIGEST
This appendix is for informational purposes only and is not required to
meet the standard.
Let the message be the binary-coded form (cf. Appendix A) of the ASCII string
"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq".
Since each of the 56 characters is converted to 8 bits, the length of the
message is l = 448. In step (a) of Section 4, we append "1". In step (b)
we append 511 "0"s. In step (c) we append the 2-word representation of 448,
i.e., hex 00000000 000001C0. This gives n = 2.
The initial hex values of {Hi} are
H0 = 67452301
H1 = EFCDAB89
H2 = 98BADCFE
H3 = 10325476
H4 = C3D2E1F0.
Start processing block 1. The words of block 1 are
W[0] = 61626364
W[1] = 62636465
W[2] = 63646566
W[3] = 64656667
W[4] = 65666768
W[5] = 66676869
W[6] = 6768696A
W[7] = 68696A6B
W[8] = 696A6B6C
W[9] = 6A6B6C6D
W[10] = 6B6C6D6E
W[11] = 6C6D6E6F
W[12] = 6D6E6F70
W[13] = 6E6F7071
W[14] = 80000000
W[15] = 00000000.
The hex values of A,B,C,D,E after pass t of the "for t = 0 to 79" loop (step
(d) of Section 7 or step (c) of Section 8) are
A B C D E
t = 0: 0116FC17 67452301 7BF36AE2 98BADCFE 10325476
t = 1: EBF3B452 0116FC17 59D148C0 7BF36AE2 98BADCFE
t = 2: 5109913A EBF3B452 C045BF05 59D148C0 7BF36AE2
t = 3: 2C4F6EAC 5109913A BAFCED14 C045BF05 59D148C0
t = 4: 33F4AE5B 2C4F6EAC 9442644E BAFCED14 C045BF05
t = 5: 96B85189 33F4AE5B 0B13DBAB 9442644E BAFCED14
t = 6: DB04CB58 96B85189 CCFD2B96 0B13DBAB 9442644E
t = 7: 45833F0F DB04CB58 65AE1462 CCFD2B96 0B13DBAB
t = 8: C565C35E 45833F0F 36C132D6 65AE1462 CCFD2B96
t = 9: 6350AFDA C565C35E D160CFC3 36C132D6 65AE1462
t = 10: 8993EA77 6350AFDA B15970D7 D160CFC3 36C132D6
t = 11: E19ECAA2 8993EA77 98D42BF6 B15970D7 D160CFC3
t = 12: 8603481E E19ECAA2 E264FA9D 98D42BF6 B15970D7
t = 13: 32F94A85 8603481E B867B2A8 E264FA9D 98D42BF6
t = 14: B2E7A8BE 32F94A85 A180D207 B867B2A8 E264FA9D
t = 15: 42637E39 B2E7A8BE 4CBE52A1 A180D207 B867B2A8
t = 16: 6B068048 42637E39 ACB9EA2F 4CBE52A1 A180D207
t = 17: 426B9C35 6B068048 5098DF8E ACB9EA2F 4CBE52A1
t = 18: 944B1BD1 426B9C35 1AC1A012 5098DF8E ACB9EA2F
t = 19: 6C445652 944B1BD1 509AE70D 1AC1A012 5098DF8E
t = 20: 95836DA5 6C445652 6512C6F4 509AE70D 1AC1A012
t = 21: 09511177 95836DA5 9B111594 6512C6F4 509AE70D
t = 22: E2B92DC4 09511177 6560DB69 9B111594 6512C6F4
t = 23: FD224575 E2B92DC4 C254445D 6560DB69 9B111594
t = 24: EEB82D9A FD224575 38AE4B71 C254445D 6560DB69
t = 25: 5A142C1A EEB82D9A 7F48915D 38AE4B71 C254445D
t = 26: 2972F7C7 5A142C1A BBAE0B66 7F48915D 38AE4B71
t = 27: D526A644 2972F7C7 96850B06 BBAE0B66 7F48915D
t = 28: E1122421 D526A644 CA5CBDF1 96850B06 BBAE0B66
t = 29: 05B457B2 E1122421 3549A991 CA5CBDF1 96850B06
t = 30: A9C84BEC 05B457B2 78448908 3549A991 CA5CBDF1
t = 31: 52E31F60 A9C84BEC 816D15EC 78448908 3549A991
t = 32: 5AF3242C 52E31F60 2A7212FB 816D15EC 78448908
t = 33: 31C756A9 5AF3242C 14B8C7D8 2A7212FB 816D15EC
t = 34: E9AC987C 31C756A9 16BCC90B 14B8C7D8 2A7212FB
t = 35: AB7C32EE E9AC987C 4C71D5AA 16BCC90B 14B8C7D8
t = 36: 5933FC99 AB7C32EE 3A6B261F 4C71D5AA 16BCC90B
t = 37: 43F87AE9 5933FC99 AADF0CBB 3A6B261F 4C71D5AA
t = 38: 24957F22 43F87AE9 564CFF26 AADF0CBB 3A6B261F
t = 39: ADEB7478 24957F22 50FE1EBA 564CFF26 AADF0CBB
t = 40: D70E5010 ADEB7478 89255FC8 50FE1EBA 564CFF26
t = 41: 79BCFB08 D70E5010 2B7ADD1E 89255FC8 50FE1EBA
t = 42: F9BCB8DE 79BCFB08 35C39404 2B7ADD1E 89255FC8
t = 43: 633E9561 F9BCB8DE 1E6F3EC2 35C39404 2B7ADD1E
t = 44: 98C1EA64 633E9561 BE6F2E37 1E6F3EC2 35C39404
t = 45: C6EA241E 98C1EA64 58CFA558 BE6F2E37 1E6F3EC2
t = 46: A2AD4F02 C6EA241E 26307A99 58CFA558 BE6F2E37
t = 47: C8A69090 A2AD4F02 B1BA8907 26307A99 58CFA558
t = 48: 88341600 C8A69090 A8AB53C0 B1BA8907 26307A99
t = 49: 7E846F58 88341600 3229A424 A8AB53C0 B1BA8907
t = 50: 86E358BA 7E846F58 220D0580 3229A424 A8AB53C0
t = 51: 8D2E76C8 86E358BA 1FA11BD6 220D0580 3229A424
t = 52: CE892E10 8D2E76C8 A1B8D62E 1FA11BD6 220D0580
t = 53: EDEA95B1 CE892E10 234B9DB2 A1B8D62E 1FA11BD6
t = 54: 36D1230A EDEA95B1 33A24B84 234B9DB2 A1B8D62E
t = 55: 776C3910 36D1230A 7B7AA56C 33A24B84 234B9DB2
t = 56: A681B723 776C3910 8DB448C2 7B7AA56C 33A24B84
t = 57: AC0A794F A681B723 1DDB0E44 8DB448C2 7B7AA56C
t = 58: F03D3782 AC0A794F E9A06DC8 1DDB0E44 8DB448C2
t = 59: 9EF775C3 F03D3782 EB029E53 E9A06DC8 1DDB0E44
t = 60: 36254B13 9EF775C3 BC0F4DE0 EB029E53 E9A06DC8
t = 61: 4080D4DC 36254B13 E7BDDD70 BC0F4DE0 EB029E53
t = 62: 2BFAF7A8 4080D4DC CD8952C4 E7BDDD70 BC0F4DE0
t = 63: 513F9CA0 2BFAF7A8 10203537 CD8952C4 E7BDDD70
t = 64: E5895C81 513F9CA0 0AFEBDEA 10203537 CD8952C4
t = 65: 1037D2D5 E5895C81 144FE728 0AFEBDEA 10203537
t = 66: 14A82DA9 1037D2D5 79625720 144FE728 0AFEBDEA
t = 67: 6D17C9FD 14A82DA9 440DF4B5 79625720 144FE728
t = 68: 2C7B07BD 6D17C9FD 452A0B6A 440DF4B5 79625720
t = 69: FDF6EFFF 2C7B07BD 5B45F27F 452A0B6A 440DF4B5
t = 70: 112B96E3 FDF6EFFF 4B1EC1EF 5B45F27F 452A0B6A
t = 71: 84065712 112B96E3 FF7DBBFF 4B1EC1EF 5B45F27F
t = 72: AB89FB71 84065712 C44AE5B8 FF7DBBFF 4B1EC1EF
t = 73: C5210E35 AB89FB71 A10195C4 C44AE5B8 FF7DBBFF
t = 74: 352D9F4B C5210E35 6AE27EDC A10195C4 C44AE5B8
t = 75: 1A0E0E0A 352D9F4B 7148438D 6AE27EDC A10195C4
t = 76: D0D47349 1A0E0E0A CD4B67D2 7148438D 6AE27EDC
t = 77: AD38620D D0D47349 86838382 CD4B67D2 7148438D
t = 78: D3AD7C25 AD38620D 74351CD2 86838382 CD4B67D2
t = 79: 8CE34517 D3AD7C25 6B4E1883 74351CD2 86838382.
Block 1 has been processed. The values of {Hi} are
H0 = 67452301 + 8CE34517 = F4286818
H1 = EFCDAB89 + D3AD7C25 = C37B27AE
H2 = 98BADCFE + 6B4E1883 = 0408F581
H3 = 10325476 + 74351CD2 = 84677148
H4 = C3D2E1F0 + 86838382 = 4A566572.
Start processing block 2. The words of block 2 are
W[0] = 00000000
W[1] = 00000000
W[2] = 00000000
W[3] = 00000000
W[4] = 00000000
W[5] = 00000000
W[6] = 00000000
W[7] = 00000000
W[8] = 00000000
W[9] = 00000000
W[10] = 00000000
W[11] = 00000000
W[12] = 00000000
W[13] = 00000000
W[14] = 00000000
W[15] = 000001C0.
The hex values of A,B,C,D,E after pass t of the for "t = 0 to 79" loop
(step (d) of Section 7 or step (c) of Section 8) are
A B C D E
t = 0: 2DF257E9 F4286818 B0DEC9EB 0408F581 84677148
t = 1: 4D3DC58F 2DF257E9 3D0A1A06 B0DEC9EB 0408F581
t = 2: C352BB05 4D3DC58F 4B7C95FA 3D0A1A06 B0DEC9EB
t = 3: EEF743C6 C352BB05 D34F7163 4B7C95FA 3D0A1A06
t = 4: 41E34277 EEF743C6 70D4AEC1 D34F7163 4B7C95FA
t = 5: 5443915C 41E34277 BBBDD0F1 70D4AEC1 D34F7163
t = 6: E7FA0377 5443915C D078D09D BBBDD0F1 70D4AEC1
t = 7: C6946813 E7FA0377 1510E457 D078D09D BBBDD0F1
t = 8: FDDE1DE1 C6946813 F9FE80DD 1510E457 D078D09D
t = 9: B8538ACA FDDE1DE1 F1A51A04 F9FE80DD 1510E457
t = 10: 6BA94F63 B8538ACA 7F778778 F1A51A04 F9FE80DD
t = 11: 43A2792F 6BA94F63 AE14E2B2 7F778778 F1A51A04
t = 12: FECD7BBF 43A2792F DAEA53D8 AE14E2B2 7F778778
t = 13: A2604CA8 FECD7BBF D0E89E4B DAEA53D8 AE14E2B2
t = 14: 258B0BAA A2604CA8 FFB35EEF D0E89E4B DAEA53D8
t = 15: D9772360 258B0BAA 2898132A FFB35EEF D0E89E4B
t = 16: 5507DB6E D9772360 8962C2EA 2898132A FFB35EEF
t = 17: A51B58BC 5507DB6E 365DC8D8 8962C2EA 2898132A
t = 18: C2EB709F A51B58BC 9541F6DB 365DC8D8 8962C2EA
t = 19: D8992153 C2EB709F 2946D62F 9541F6DB 365DC8D8
t = 20: 37482F5F D8992153 F0BADC27 2946D62F 9541F6DB
t = 21: EE8700BD 37482F5F F6264854 F0BADC27 2946D62F
t = 22: 9AD594B9 EE8700BD CDD20BD7 F6264854 F0BADC27
t = 23: 8FBAA5B9 9AD594B9 7BA1C02F CDD20BD7 F6264854
t = 24: 88FB5867 8FBAA5B9 66B5652E 7BA1C02F CDD20BD7
t = 25: EEC50521 88FB5867 63EEA96E 66B5652E 7BA1C02F
t = 26: 50BCE434 EEC50521 E23ED619 63EEA96E 66B5652E
t = 27: 5C416DAF 50BCE434 7BB14148 E23ED619 63EEA96E
t = 28: 2429BE5F 5C416DAF 142F390D 7BB14148 E23ED619
t = 29: 0A2FB108 2429BE5F D7105B6B 142F390D 7BB14148
t = 30: 17986223 0A2FB108 C90A6F97 D7105B6B 142F390D
t = 31: 8A4AF384 17986223 028BEC42 C90A6F97 D7105B6B
t = 32: 6B629993 8A4AF384 C5E61888 028BEC42 C90A6F97
t = 33: F15F04F3 6B629993 2292BCE1 C5E61888 028BEC42
t = 34: 295CC25B F15F04F3 DAD8A664 2292BCE1 C5E61888
t = 35: 696DA404 295CC25B FC57C13C DAD8A664 2292BCE1
t = 36: CEF5AE12 696DA404 CA573096 FC57C13C DAD8A664
t = 37: 87D5B80C CEF5AE12 1A5B6901 CA573096 FC57C13C
t = 38: 84E2A5F2 87D5B80C B3BD6B84 1A5B6901 CA573096
t = 39: 03BB6310 84E2A5F2 21F56E03 B3BD6B84 1A5B6901
t = 40: C2D8F75F 03BB6310 A138A97C 21F56E03 B3BD6B84
t = 41: BFB25768 C2D8F75F 00EED8C4 A138A97C 21F56E03
t = 42: 28589152 BFB25768 F0B63DD7 00EED8C4 A138A97C
t = 43: EC1D3D61 28589152 2FEC95DA F0B63DD7 00EED8C4
t = 44: 3CAED7AF EC1D3D61 8A162454 2FEC95DA F0B63DD7
t = 45: C3D033EA 3CAED7AF 7B074F58 8A162454 2FEC95DA
t = 46: 7316056A C3D033EA CF2BB5EB 7B074F58 8A162454
t = 47: 46F93B68 7316056A B0F40CFA CF2BB5EB 7B074F58
t = 48: DC8E7F26 46F93B68 9CC5815A B0F40CFA CF2BB5EB
t = 49: 850D411C DC8E7F26 11BE4EDA 9CC5815A B0F40CFA
t = 50: 7E4672C0 850D411C B7239FC9 11BE4EDA 9CC5815A
t = 51: 89FBD41D 7E4672C0 21435047 B7239FC9 11BE4EDA
t = 52: 1797E228 89FBD41D 1F919CB0 21435047 B7239FC9
t = 53: 431D65BC 1797E228 627EF507 1F919CB0 21435047
t = 54: 2BDBB8CB 431D65BC 05E5F88A 627EF507 1F919CB0
t = 55: 6DA72E7F 2BDBB8CB 10C7596F 05E5F88A 627EF507
t = 56: A8495A9B 6DA72E7F CAF6EE32 10C7596F 05E5F88A
t = 57: E785655A A8495A9B DB69CB9F CAF6EE32 10C7596F
t = 58: 5B086C42 E785655A EA1256A6 DB69CB9F CAF6EE32
t = 59: A65818F7 5B086C42 B9E15956 EA1256A6 DB69CB9F
t = 60: 7AAB101B A65818F7 96C21B10 B9E15956 EA1256A6
t = 61: 93614C9C 7AAB101B E996063D 96C21B10 B9E15956
t = 62: F66D9BF4 93614C9C DEAAC406 E996063D 96C21B10
t = 63: D504902B F66D9BF4 24D85327 DEAAC406 E996063D
t = 64: 60A9DA62 D504902B 3D9B66FD 24D85327 DEAAC406
t = 65: 8B687819 60A9DA62 F541240A 3D9B66FD 24D85327
t = 66: 083E90C3 8B687819 982A7698 F541240A 3D9B66FD
t = 67: F6226BBF 083E90C3 62DA1E06 982A7698 F541240A
t = 68: 76C0563B F6226BBF C20FA430 62DA1E06 982A7698
t = 69: 989DD165 76C0563B FD889AEF C20FA430 62DA1E06
t = 70: 8B2C7573 989DD165 DDB0158E FD889AEF C20FA430
t = 71: AE1B8E7B 8B2C7573 66277459 DDB0158E FD889AEF
t = 72: CA1840DE AE1B8E7B E2CB1D5C 66277459 DDB0158E
t = 73: 16F3BABB CA1840DE EB86E39E E2CB1D5C 66277459
t = 74: D28D83AD 16F3BABB B2861037 EB86E39E E2CB1D5C
t = 75: 6BC02DFE D28D83AD C5BCEEAE B2861037 EB86E39E
t = 76: D3A6E275 6BC02DFE 74A360EB C5BCEEAE B2861037
t = 77: DA955482 D3A6E275 9AF00B7F 74A360EB C5BCEEAE
t = 78: 58C0AAC0 DA955482 74E9B89D 9AF00B7F 74A360EB
t = 79: 906FD62C 58C0AAC0 B6A55520 74E9B89D 9AF00B7F.
Block 2 has been processed. The values of {Hi} are
H0 = F4286818 + 906FD62C = 84983E44
H1 = C37B27AE + 58C0AAC0 = 1C3BD26E
H2 = 0408F581 + B6A55520 = BAAE4AA1
H3 = 84677148 + 74E9B89D = F95129E5
H4 = 4A566572 + 9AF00B7F = E54670F1.
Message digest = 84983E44 1C3BD26E BAAE4AA1 F95129E5 E54670F1
APPENDIX C. A THIRD SAMPLE MESSAGE AND ITS MESSAGE DIGEST
This appendix is for informational purposes only and is not required to meet
the standard.
Let the message be the binary-coded form of the ASCII string which consists
of 1,000,000 repetitions of "a".
Message digest = 34AA973C D4C4DAA4 F61EEB2B DBAD2731 6534016F
Raw
hashcash.c
/* "hash cash" mint and remailer plug in for purposes of
* remailer postage (or any other use you can think of)
*
* hash cash is payment in burnt CPU cycles by calculating n-bit
* partial hash collisions
*
* see: http://www.dcs.ex.ac.uk/~aba/hashcash/
*
* for updates.
*
* version 0.1: 27 Mar 97
* Adam Back <aba@dcs.ex.ac.uk>
* http://www.dcs.ex.ac.uk/~aba/hashcash/
*
* version 0.2: 28 Mar 97
* Chris Kuethe <ckuethe@gpu.srv.ualberta.ca>
* http://www.ualberta.ca/~ckuethe/
* added minimal macintosh support (Think C)
*
* version 0.3: 30 Mar 97
* Adam Back <aba@dcs.ex.ac.uk>
* put in fast SHA1, and other mods giving a 4x speedup
* plus a few bug fixes
*
* version 0.4 31 Mar 97
* Adam Back <aba@dcs.ex.ac.uk>
* More portable timer and types macros
*
* version 0.5 07 Apr 97
* Adam Back <aba@dcs.ex.ac.uk>
* made mods as suggested by
* Andy Dustman <andy@CCMSD.chem.uga.edu>
* to avoid collision collisions on larger collision lengths
* previous method was bugged
*
* version 0.6 07 May 97
* Andy Dustman <andy@CCMSD.chem.uga.edu>
* bug fix + SPARSE compile option for library use
*
* version 0.7: 08 Dec 97
* Adam Back <aba@dcs.ex.ac.uk>
* bug fix in SHA1 code
*
*/
#if defined( THINK_C )
#include <console.h>
#include <unix.h>
#else
#include <unistd.h>
#endif
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include "sha1.h"
#include "timer.h"
void random_start( word32*, word32*, word32*, word32* );
void usage( void );
word32 find_collision( char day[ 5 ], char*, int, char*, word32, char* );
double estimate_time( int );
double expected_tries( int );
double usecs_for_n_hashes( word32 );
void set_db_filename( char* );
void add_to_database( char*, int );
void purge_database( void );
int still_valid( char*, int );
#define GROUP_SIZE ULONG_MAX
#define GROUP_DIGITS 8
#define GFORMAT "%08x"
#if 0
/* smaller base for debugging */
#define GROUP_SIZE 255
#define GROUP_DIGITS 2
#define GFORMAT "%02x"
#endif
/* a 120Mhz 486 does 28000 per second
do a special case for tick = 1 second, say 5 seconds
so 131071 tries
*/
#define DEFAULT_TRY ( ( tick_us() == 1000000 ) ? 131071 : 16383 )
word32 hashes_per_sec( void );
char* db_filename = "hashcash.db";
int validity_period = 28;
int bits = 20;
char today[ 6 ];
word32 today_num;
#ifndef SPARSE
int main( int argc, char* argv[] )
{
int tries;
int i;
word32 i0, i1, i2;
word32 ran0, ran1, ran2, ran3;
int done0 = 0, done1 = 0, done2 = 0;
int collision_bits;
int arguments = 0;
int time_flag = 0;
int bits_flag = 0;
int validity_flag = 0;
int database_flag = 0;
int name_flag = 0;
int check_flag = 0;
int valid;
int in_db;
int gig;
int expired;
int seconds;
int found;
char collision[ 100 ];
char name[ 100 ];
char check[ 100 ];
char counter[ 50 ];
char* counter_ptr;
double tries_expected;
double tries_taken;
double time_estimated;
double taken;
double count;
#ifdef THINK_C
argc=ccommand(&argv);
#endif
for ( i = 1; i < argc; i++ )
{
if ( argv[ i ][ 0 ] == '-' )
{
switch ( argv[ i ][ 1 ] )
{
case 't':
time_flag = 1;
break;
case 'd':
database_flag = 1;
break;
case 'f':
set_db_filename( argv[ i ] + 2 );
break;
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
bits = atoi( argv[ i ] + 1 );
bits_flag = 1;
if ( bits < 0 ) { usage(); }
break;
default:
usage();
}
}
else
{
switch ( arguments )
{
case 0:
strncpy( name, argv[ i ], 100 );
name_flag = 1;
break;
case 1:
strncpy( check, argv[ i ], 100 );
check_flag = 1;
break;
case 2:
validity_period = atoi( argv[ i ] );
validity_flag = 1;
if ( validity_period < 0 ) { usage(); }
break;
default:
usage();
break;
}
arguments++;
}
}
if ( ! time_flag && ! name_flag )
{
usage();
}
today_num = ( time( 0 ) / 3600 ) / 24;
sprintf( today, "%05d", today_num );
if ( check_flag )
{
/* database_flag only meaningful if check_flag set */
valid = still_valid( check, validity_period );
if ( validity_flag )
{
printf( "validity: " );
if ( valid == 0 )
{
printf( "expired\n" );
}
else if ( valid > 0 )
{
printf( "%d days remaining\n", valid );
}
else
{
printf( "forever\n" );
}
}
collision_bits = count_collision_bits( name, check );
printf( "collision: %d bits\n", collision_bits );
if ( bits_flag )
{
printf( "required: %d bits\n", bits );
if ( collision_bits < bits )
{
printf( "rejected: too few bits\n" );
}
}
if ( database_flag ) /* if we're checking the database */
{
in_db = in_database( check ); /* if it's in there, it's a failure */
printf( "database: " );
if ( in_db )
{
printf( "double spent\n" );
exit( 1 );
}
else
{
printf( "not double spent\n" );
if ( validity_flag ) /* validity check */
{
if ( valid )
{
if ( bits_flag ) /* check num of bits */
{
if ( collision_bits >= bits )
{
add_to_database( check, validity_period );
exit( 0 );
}
}
else /* no bit check */
{
add_to_database( check, validity_period );
exit( 0 );
}
}
exit( 1 ); /* else fail */
}
else /* no validity check */
{
if ( bits_flag ) /* check num of bits */
{
if ( collision_bits >= bits )
{
add_to_database( check, validity_period );
exit( 0 );
}
}
else /* no bit check */
{
add_to_database( check, validity_period );
exit( 0 );
}
exit ( 1 );
}
}
}
if ( !bits_flag )
{
if ( !validity_flag || (validity_flag && valid) )
{
exit ( 0 ); /* if target not given */
}
}
else
{
if ( collision_bits >= bits )
{
if ( !validity_flag || (validity_flag && valid) )
{
exit( 0 ); /* if target given and met */
}
}
}
exit( 1 ); /* target given and failed */
}
printf( "speed: %lu hashes per sec\n", hashes_per_sec() );
if ( bits_flag )
{
printf( "find: %d bit partial sha1 collision\n", bits );
time_estimated = estimate_time( bits );
printf( "estimate: %.0lf seconds\n", time_estimated );
tries_expected = expected_tries( bits );
printf( "expected: %.0lf tries = 2 ^ %d tries\n", tries_expected, bits );
}
fflush( stdout );
if ( time_flag )
{
exit( 0 ); /* don't actually calculate it */
}
if ( ! name_flag )
{
usage();
}
memset( counter, '\0', 37 );
random_start( &ran0, &ran1, &ran2, &ran3 );
timer_start();
counter_ptr = counter;
found = 0;
for ( i0 = 0; !found; )
{
sprintf( counter_ptr, GFORMAT GFORMAT, ( i0 + ran0 ) & GROUP_SIZE,
ran1 & GROUP_SIZE );
found = find_collision( today, name, bits, collision,
GROUP_SIZE, counter_ptr );
if ( !found )
{
i0 = ( i0 + 1 ) & GROUP_SIZE;
if ( i0 == 0 ) /* ie if wrapped */
{
fprintf( stderr, "failed to find collision in 2^64 tries!\n" );
exit( 1 );
/* shouldn't get here without trying */
/* for a very long time */
}
}
}
count = 0;
printf( "collision: %s\n", collision );
printf( "tries: " );
counter_ptr = counter;
tries_taken = ( (double) i0 ) * ULONG_MAX + ( (double) found );
printf( "%.0lf", tries_taken );
printf( " %.2lf x expected\n", tries_taken / tries_expected );
timer_stop();
taken = timer_time() / 1000000.0;
printf( "time: %.0lf seconds", taken );
#if 0
/* This is commented out because it is confusing to see discrepency
between x expected time and x expected tries.
(And yes, you would expect to see a discrepency because the length
of the counter (the amount of data to hash) affects the time taken
to check a hash. And the number of bits of collision requested
affects the proportion of times that the counter will get longer.)
*/
printf( " %.2lf x expected", taken / time_estimated );
#endif
putchar( '\n' );
return 0;
}
word32 hashes_per_s = 0;
word32 hashes_per_sec( void )
{
double usecs;
if ( hashes_per_s == 0 )
{
usecs = usecs_for_n_hashes( DEFAULT_TRY );
hashes_per_s = (word32) ( ( ( (double)DEFAULT_TRY ) / usecs )
* 1000000.0 );
}
return hashes_per_s;
}
double expected_tries( int b )
{
double expected_hashes = 1.0;
while ( b > 31 )
{
expected_hashes *= 1UL << 31;
b -= 31;
}
expected_hashes *= 1UL << b;
return expected_hashes;
}
double estimate_time( int b )
{
return expected_tries( b ) / hashes_per_sec();
}
double usecs_for_n_hashes( word32 try )
{
timer start;
timer end;
byte collision[ 20 ];
char counter[ 50 ];
double elapsed;
timer_read( &start );
sprintf( counter, GFORMAT GFORMAT, 0, 0 );
find_collision( "09856", "flame", 25, collision, try, counter );
timer_read( &end );
elapsed = timer_interval( &start, &end );
return elapsed;
}
#endif SPARSE
int still_valid( char* check, int validity_period )
{
char day[ 6 ];
word32 day_num;
word32 today_num = ( time( 0 ) / 3600 ) / 24;
if ( validity_period == 0 ) /* for ever */
{
return -1; /* infinity */
}
strncpy( day, check, 5 );
day[ 5 ] = '\0';
day_num = atoi( day );
if ( day_num > today_num ) return 0;
if ( day_num + validity_period > today_num )
{ /* valid return days left */
return day_num + validity_period - today_num;
}
else return 0;
}
int count_collision_bits( char* name, char* check )
{
char target[ 100 ];
char try[ 100 ];
SHA1_ctx ctx;
byte target_digest[ 20 ];
byte check_digest[ 20 ];
int i;
int last;
int collision_bits;
strncpy( target, check, 5 );
target[ 5 ] = '\0';
strncat( target, name, 95 );
SHA1_init( &ctx );
SHA1_update( &ctx, target, strlen( target ) );
SHA1_final( &ctx );
memcpy( target_digest, SHA1_digest( &ctx ), SHA1_DIGEST_BYTES );
SHA1_init( &ctx );
SHA1_update( &ctx, check, strlen( check ) );
SHA1_final( &ctx );
memcpy( check_digest, SHA1_digest( &ctx ), SHA1_DIGEST_BYTES );
for ( i = 0; i < 20 && check_digest[ i ] == target_digest[ i ]; i++ )
{
}
last = i;
collision_bits = 8 * i;
#define bit( n, c ) (((c) >> (7 - (n))) & 1)
for ( i = 0; i < 8; i++ )
{
if ( bit( i, check_digest[ last ] ) == bit( i, target_digest[ last ] ) )
{
collision_bits++;
}
else
{
break;
}
}
return collision_bits;
}
void random_start( word32* w1, word32* w2, word32* w3, word32* w4)
{
/* kludge, might want to improve this, if collision collisions happen */
timer t;
word32 start;
byte digest[ 20 ];
SHA1_ctx ctx;
SHA1_init( &ctx );
timer_read( &t );
SHA1_update( &ctx, &t, sizeof( timer ) );
SHA1_final( &ctx );
*w1 = ctx.H[ 0 ];
*w2 = ctx.H[ 1 ];
*w3 = ctx.H[ 2 ];
*w4 = ctx.H[ 3 ];
}
word32 find_collision( char day[ 5 ], char* name, int bits,
char* collision, word32 tries, char* counter )
{
char* hex = "0123456789abcdef";
char target[ 100 ];
char try[ 100 ];
char* changing_part_of_try;
SHA1_ctx ctx;
SHA1_ctx precomputed_ctx;
word32 i;
int j;
word32 trial;
word32 tries2;
int len;
int counter_len;
int try_len;
int try_strlen;
byte target_digest[ 20 ];
byte try_digest[ 20 ];
int partial_byte = bits & 7;
int check_bytes;
int partial_byte_index;
int partial_byte_mask;
char last_char;
int last_digit;
memcpy( target, day, 5 );
target[ 5 ] = 0;
strncat( target, name, 95 );
counter_len = strlen( counter ) - GROUP_DIGITS;
sscanf( counter + counter_len, "%08x", &trial );
trial -= trial % 16; /* lop off last digit */
if ( partial_byte )
{
partial_byte_index = bits / 8;
partial_byte_mask = ~ (( 1 << (8 - (bits & 7))) -1 );
check_bytes = partial_byte_index + 1;
}
else
{
check_bytes = bits / 8;
}
SHA1_init( &ctx );
SHA1_update( &ctx, target, strlen( target ) );
SHA1_final( &ctx );
memcpy( target_digest, SHA1_digest( &ctx ), SHA1_DIGEST_BYTES );
if ( partial_byte )
{
target_digest[ partial_byte_index ] &= partial_byte_mask;
}
strncpy( try, target, 100 );
strncat( try, counter, counter_len );
try_len = strlen( try );
/* length of try is fixed, GFORMAT is %08x, so move strlen outside loop */
changing_part_of_try = try + try_len;
sprintf( changing_part_of_try, GFORMAT, 0 );
try_strlen = strlen( try );
/* part of the ctx context can be precomputed as not all of the
message is changing
*/
tries2 = (int) ( (double) tries / 16.0 + 0.5 );
for ( i = 0; i < tries2; i++, trial = (trial + 16) & GROUP_SIZE )
{
/* move precompute closer to the inner loop to precompute more */
SHA1_init( &precomputed_ctx );
sprintf( changing_part_of_try, GFORMAT, trial );
SHA1_update( &precomputed_ctx, try, try_strlen - 1 );
for ( j = 0; j < 16; j++ )
{
#if defined( DEBUG )
printf( "try: %s\n", try );
#endif
memcpy( &ctx, &precomputed_ctx, sizeof( SHA1_ctx ) );
last_char = hex[ j ];
SHA1_update( &ctx, &last_char, 1 );
SHA1_final( &ctx );
memcpy( try_digest, SHA1_digest( &ctx ), SHA1_DIGEST_BYTES );
if ( bits > 7 )
{
if ( try_digest[ 0 ] != target_digest[ 0 ] )
{
continue;
}
}
if ( partial_byte )
{
try_digest[ partial_byte_index ] &= partial_byte_mask;
}
if ( memcmp( target_digest, try_digest, check_bytes ) == 0 )
{
changing_part_of_try[ GROUP_DIGITS - 1 ] = hex[ j ];
strcpy( collision, try );
return i * 16 + j + 1;
}
}
}
return 0;
}
#ifndef SPARSE
void create_if_nec( void )
{
FILE* db = fopen( db_filename, "r" );
if ( db == 0 )
{
if ( errno == ENOENT )
{
db = fopen( db_filename, "w" );
if ( db == 0 )
{
perror( db_filename );
exit( 1 );
}
fprintf( db, "%s\n", today );
fclose( db );
}
}
}
void purge_if_nec( void )
{
FILE* db;
char day[ 6 ];
db = fopen( db_filename, "r" );
fgets( day, 6, db );
day[ 5 ] ='\0';
fclose( db );
if ( strncmp( day, today, 5 ) != 0 )
{
purge_database();
}
}
/* dumb, DUMB, implementations of a database function - linear lookup */
void add_to_database( char* collision, int expiry )
{
FILE* db;
create_if_nec();
purge_if_nec();
db = fopen( db_filename, "a" );
if ( db == 0 )
{
perror( db_filename );
exit( 1 );
}
printf( "adding: %d %s\n", expiry, collision );
fseek( db, 0, SEEK_END );
fprintf( db, "%d ", expiry );
fputs( collision, db );
fputc( '\n', db );
fclose( db );
}
int in_database( char* find, int days )
{
char entry[ 100 ];
char* collision;
char* expiry;
int expiry_num;
char day[ 6 ];
word32 day_num;
int len;
FILE* db;
create_if_nec();
purge_if_nec();
len = strlen( find );
db = fopen( db_filename, "r" );
if ( db == 0 )
{
perror( db_filename );
exit( 1 );
}
fgets( entry, 100, db ); /* junk date line */
while ( !feof( db ) )
{
fgets( entry, 100, db );
if ( !feof( db ) )
{
expiry = strtok( entry, " " );
if ( expiry == 0 )
{
fclose( db );
return 0;
}
collision = strtok( 0, " " );
if ( strncmp( find, collision, len ) == 0 )
{
fclose( db );
return 1;
}
}
}
fclose( db );
return 0;
}
void purge_database( void )
{
FILE* db = fopen( db_filename, "r" );
char purged_filename[ 256 ];
FILE* purged;
int status;
char entry[ 100 ];
char day[ 6 ];
word32 day_num;
char* expiry;
char* collision;
word32 expiry_num;
printf( "purging database...\n" );
if ( db == 0 )
{
perror( db_filename );
exit( 1 );
}
strncpy( purged_filename, db_filename, 256 );
strcat( purged_filename, "1" );
purged = fopen( purged_filename, "w" );
if ( purged == 0 )
{
perror( purged_filename );
exit( 1 );
}
printf( "tmpfile: %s\n", purged_filename );
fputs( today, purged );
fputc( '\n', purged );
fgets( entry, 100, db ); /* junk date line */
while ( ! feof( db ) )
{
fgets( entry, 100, db );
expiry = strtok( entry, " " );
if ( expiry == 0 )
{
continue;
}
collision = strtok( 0, " " );
if ( collision == 0 )
{
continue;
}
expiry_num = atoi( expiry );
strncpy( day, collision, 5 );
day[ 5 ] ='\0';
day_num = atoi( day );
if ( expiry_num == 0 || expiry_num && day_num + expiry_num >= today_num )
{
fputs( expiry, purged );
fputc( ' ', purged );
fputs( collision, purged );
}
else
{
printf( "discarded: %d %s", expiry_num, collision );
}
}
fflush( purged );
fclose( purged );
fclose( db );
unlink( db_filename );
status = rename( purged_filename, db_filename );
if ( status < 0 )
{
perror( "rename" );
exit( 1 );
}
printf( "done\n" );
}
void set_db_filename( char* filename )
{
db_filename = filename;
}
void usage( void )
{
fprintf( stderr, "usage: hashcash [-t] [-d] [-fdbfile] [-bits] string [check [days]]\n\n" );
fprintf( stderr, "\t-t\ttime only (don't find collision)\n" );
fprintf( stderr, "\t-d\tuse database (for double spending detection)\n" );
fprintf( stderr, "\t-f\tuse filename dbfile for database\n" );
fprintf( stderr, "\t-bits\tfind partial hash collision of length bits\n" );
fprintf( stderr, "\tstring\tis the string to find a partial hash collision on\n" );
fprintf( stderr, "\tcheck\treport on collision check (with respect to string)\n" );
fprintf( stderr, "\tdays\treport on cash with days validity period from minting\n" );
fprintf( stderr, "\n" );
fprintf( stderr, "examples:\n" );
fprintf( stderr, "\thashcash -20 flame # mint 20 bit collision\n" );
fprintf( stderr, "\thashcash flame 09948flame3543 # examine collision\n" );
fprintf( stderr, "# examine, also keep double spend database, validity 28 days\n" );
fprintf( stderr, "\thashcash -d flame 09948flame3543 28\n" );
fprintf( stderr, "\n" );
fprintf( stderr, "see http://www.dcs.ex.ac.uk/~aba/hashcash/ for more detail\n");
exit( 1 );
}
#endif
Raw
hashcash.tgz.sig
hashcash.tgz signature from
Adam Back <aba@dcs.ex.ac.uk>
-----BEGIN PGP MESSAGE-----
Version: 2.6.3i
iQEVAwUANItI8T57yqgoskVRAQGWhwf7BhLbswYptMHQ5AC4jXOqZIM5dVZI86m0
XtsPC0hhmy5wCI3KK/NYqFxjJylocpUK4p3jpvIjBGBm6wlLRL8bK751F3jxqc+3
qdpZ8vYVrgAYMZ+GBflXnZ+f17vAMvSBpCsykJ1ihTFJXHBnrD3NbxQtJpx5pmuM
FrdvDNkwe94aaI1ZBPnjSnsmkGfBHyPA2skbnXaKFzaq7KnWpxyM3ECAdQ3QsESA
MlgHGQtvGLHRjDSMnz5fkhCCNLKWz5MPLW3OcOSbiE75XerMeTNKfxHwQLsDQ1ZK
89lEk3RLGG1jaQRgAznN7K5Za4EC1i1o/crdsVRjqsZKTYZOPrwk1A==
=866O
-----END PGP MESSAGE-----
Raw
sha1.c
/*
* Implementation of Federal Information Processing Standards Publication
* FIPS 180-1 (17 Apr 1995) which supersedes FIPS 180 (11 May 1993)
*
* Speed hack version optimised for speed (see also reference version)
* uses macros so you need to recompile, not just relink
*
* Adam Back <aba@dcs.ex.ac.uk>
*
*/
/* define VERBOSE to get output as in fip180-1.txt */
#if defined( VERBOSE )
#include <stdio.h>
#endif
#include "sha1.h"
#include "endian.h"
#define min( x, y ) ( ( x ) < ( y ) ? ( x ) : ( y ) )
/********************* function used for rounds 0..19 ***********/
/* #define F1( B, C, D ) ( ( (B) & (C) ) | ( ~(B) & (D) ) ) */
/* equivalent, one less operation: */
#define F1( B, C, D ) ( (D) ^ ( (B) & ( (C) ^ (D) ) ) )
/********************* function used for rounds 20..39 ***********/
#define F2( B, C, D ) ( (B) ^ (C) ^ (D) )
/********************* function used for rounds 40..59 ***********/
/* #define F3( B, C, D ) ( (B) & (C) ) | ( (C) & (D) ) | ( (C) & (D) ) */
/* equivalent, one less operation */
#define F3( B, C, D ) ( ( (B) & ( (C) | (D) )) | ( (C) & (D) ) )
/********************* function used for rounds 60..79 ***********/
#define F4( B, C, D ) ( (B) ^ (C) ^ (D) )
#define K1 0x5A827999 /* constant used for rounds 0..19 */
#define K2 0x6ED9EBA1 /* constant used for rounds 20..39 */
#define K3 0x8F1BBCDC /* constant used for rounds 40..59 */
#define K4 0xCA62C1D6 /* constant used for rounds 60..79 */
/* magic constants */
#define H0 0x67452301
#define H1 0xEFCDAB89
#define H2 0x98BADCFE
#define H3 0x10325476
#define H4 0xC3D2E1F0
word32 SHA1_IV[ 5 ] = { H0, H1, H2, H3, H4 };
/* rotate X n bits left ( X <<< n ) */
#define S(n, X) ( ( (X) << (n) ) | ( (X) >> ( 32 - (n) ) ) )
/* this is only used if you want to modify the IV */
/* ignore this function for purposes of the standard */
void SHA1_init_with_IV( SHA1_ctx* ctx,
const byte user_IV[ SHA1_DIGEST_BYTES ] )
{
word32 IV[ SHA1_DIGEST_WORDS ];
SHA1_zero_bitcount( ctx );
memcpy( IV, user_IV, SHA1_DIGEST_BYTES );
make_big_endian32( IV, SHA1_DIGEST_WORDS );
SHA1_set_IV( ctx, IV );
}
void SHA1_transform( word32 H[ SHA1_DIGEST_WORDS ],
const byte M[ SHA1_INPUT_BYTES ] )
{
int t;
word32 A = H[ 0 ];
word32 B = H[ 1 ];
word32 C = H[ 2 ];
word32 D = H[ 3 ];
word32 E = H[ 4 ];
word32 W[ 16 ];
memcpy( W, M, SHA1_INPUT_BYTES );
/* Use method B from FIPS-180 (see fip-180.txt) where the use of
temporary array W of 80 word32s is avoided by working in a circular
buffer of size 16 word32s.
*/
/********************* define some macros *********************/
/* Wc = access W as 16 word circular buffer */
#define Wc( t ) ( W[ (t) & 15 ] )
/* Calculate access to W array on the fly for entries 16 .. 79 */
#define Wf( t ) \
( Wc( t ) = S( 1, Wc( t ) ^ Wc( t - 14 ) ^ Wc( t - 8 ) ^ Wc( t - 3 ) ) )
/* Calculate access to W virtual array calculating access to W on the fly */
#define Wfly( t ) ( (t) < 16 ? W[ (t) ] : Wf( (t) ) )
#if defined( VERBOSE )
#define REPORT( t ) \
fprintf( stderr, "t = %2d: %08x %08x %08x %08x %08x\n",\
t, A, B, C, D, E );
#else
#define REPORT( t )
#endif
#define ROUND( t, A, B, C, D, E, Func, K ) \
E += S( 5, A ) + Func( B, C, D ) + Wfly( t ) + K;\
B = S( 30, B ); REPORT( t )
/* Remove rotatation E' = D; D' = C; C' = B; B' = A; A' = E; by
completely unrolling and rotating the arguments to the macro ROUND
manually so the rotation is compiled in.
*/
#define ROUND5( t, Func, K ) \
ROUND( t + 0, A, B, C, D, E, Func, K );\
ROUND( t + 1, E, A, B, C, D, Func, K );\
ROUND( t + 2, D, E, A, B, C, Func, K );\
ROUND( t + 3, C, D, E, A, B, Func, K );\
ROUND( t + 4, B, C, D, E, A, Func, K )
#define ROUND20( t, Func, K )\
ROUND5( t + 0, Func, K );\
ROUND5( t + 5, Func, K );\
ROUND5( t + 10, Func, K );\
ROUND5( t + 15, Func, K )
/********************* use the macros *********************/
#if defined( VERBOSE )
for ( t = 0; t < 16; t++ )
{
fprintf( stderr, "W[%2d] = %08x\n", t, W[ t ] );
}
fprintf( stderr,
" A B C D E\n\n" );
#endif
/* rounds 0..19 */
ROUND20( 0, F1, K1 );
/* rounds 21..39 */
ROUND20( 20, F2, K2 );
/* rounds 40..59 */
ROUND20( 40, F3, K3 );
/* rounds 60..79 */
ROUND20( 60, F4, K4 );
H[ 0 ] += A;
H[ 1 ] += B;
H[ 2 ] += C;
H[ 3 ] += D;
H[ 4 ] += E;
}
void SHA1_update( SHA1_ctx* ctx, const void* pdata, word32 data_len )
{
const byte* data = pdata;
word32 use;
word32 low_bits;
int mlen;
/* convert data_len to bits and add to the 64-bit bit count */
#if defined( word64 )
mlen = ( ctx->bits >> 3 ) % SHA1_INPUT_BYTES;
ctx->bits += ( (word64) data_len ) << 3;
#else
mlen = ( ctx->lbits >> 3 ) % SHA1_INPUT_BYTES;
ctx->hbits += data_len >> 29; /* simulate 64 bit addition */
low_bits = data_len << 3;
ctx->lbits += low_bits;
if ( ctx->lbits < low_bits ) { ctx->hbits++; }
#endif
/* deal with first block */
use = min( SHA1_INPUT_BYTES - mlen, data_len );
memcpy( ctx->M + mlen, data, use );
mlen += use;
data_len -= use;
data += use;
while ( mlen == SHA1_INPUT_BYTES )
{
make_big_endian32( (word32*)ctx->M, SHA1_INPUT_WORDS );
SHA1_transform( ctx->H, ctx->M );
use = min( SHA1_INPUT_BYTES, data_len );
memcpy( ctx->M, data, use );
mlen = use;
data_len -= use;
data += use;
}
}
void SHA1_final( SHA1_ctx* ctx )
{
int mlen;
int padding;
#if defined( word64 )
word64 temp;
#endif
#if defined( word64 )
mlen = ( ctx->bits >> 3 ) % SHA1_INPUT_BYTES;
#else
mlen = ( ctx->lbits >> 3 ) % SHA1_INPUT_BYTES;
#endif
ctx->M[ mlen ] = 0x80; mlen++; /* append a 1 bit */
padding = SHA1_INPUT_BYTES - mlen;
#define BIT_COUNT_WORDS 2
#define BIT_COUNT_BYTES ( BIT_COUNT_WORDS * sizeof( word32 ) )
if ( padding >= BIT_COUNT_BYTES )
{
memset( ctx->M + mlen, 0x00, padding - BIT_COUNT_BYTES );
make_big_endian32( ctx->M, SHA1_INPUT_WORDS - BIT_COUNT_WORDS );
}
else
{
memset( ctx->M + mlen, 0x00, SHA1_INPUT_BYTES - mlen );
make_big_endian32( ctx->M, SHA1_INPUT_WORDS );
SHA1_transform( ctx->H, ctx->M );
memset( ctx->M, 0x00, SHA1_INPUT_BYTES - BIT_COUNT_BYTES );
}
#if defined( word64 )
if ( little_endian )
{
temp = ( ctx->bits << 32 | ctx->bits >> 32 );
}
else
{
temp = ctx->bits;
}
memcpy( ctx->M + SHA1_INPUT_BYTES - BIT_COUNT_BYTES, &temp,
BIT_COUNT_BYTES );
#else
memcpy( ctx->M + SHA1_INPUT_BYTES - BIT_COUNT_BYTES, &(ctx->hbits),
BIT_COUNT_BYTES );
#endif
SHA1_transform( ctx->H, ctx->M );
}
const byte* SHA1_get_digest( const SHA1_ctx* ctx )
{
static byte digest[ SHA1_DIGEST_BYTES ];
if ( little_endian )
{
memcpy( digest, ctx->H, SHA1_DIGEST_BYTES );
make_big_endian32( digest, SHA1_DIGEST_WORDS );
return digest;
}
else
{
return (const byte*) ( ctx->H );
}
}
Raw
sha1.h
#if !defined( _sha1_h )
#define _sha1_h
#include "types.h"
#include "endian.h"
#if defined( __cplusplus )
extern "C" {
#endif
#define SHA1_INPUT_BYTES 64 /* 512 bits */
#define SHA1_INPUT_WORDS ( SHA1_INPUT_BYTES >> 2 )
#define SHA1_DIGEST_WORDS 5 /* 160 bits */
#define SHA1_DIGEST_BYTES ( SHA1_DIGEST_WORDS * 4 )
typedef struct {
word32 H[ SHA1_DIGEST_WORDS ];
#if defined( word64 )
word64 bits; /* we want a 64 bit word */
#else
word32 hbits, lbits; /* if we don't have one we simulate it */
#endif
byte M[ SHA1_INPUT_BYTES ];
} SHA1_ctx;
#define SHA1_set_IV( ctx, IV ) \
memcpy( (ctx)->H, IV, SHA1_DIGEST_BYTES )
#if defined( word64 )
#define SHA1_zero_bitcount( ctx )\
(ctx)->bits = 0
#else\
#define SHA1_zero_bitcount( ctx )\
(ctx)->lbits = 0;\
(ctx)->hbits = 0
#endif
extern word32 SHA1_IV[ 5 ];
#define SHA1_init( ctx ) \
SHA1_zero_bitcount( ctx ); \
SHA1_set_IV( ctx, SHA1_IV )
void SHA1_update( SHA1_ctx*, const void*, word32 );
void SHA1_final ( SHA1_ctx* );
/* called by macro */
const byte* SHA1_get_digest( const SHA1_ctx* );
/* result is in reused memory, copy it if you want to keep it */
#define SHA1_digest( ctx ) \
( little_endian ? SHA1_get_digest( ctx ) : (const byte*) (ctx)->H )
/* these provide extra access to internals of SHA1 for MDC and MACs */
void SHA1_init_with_IV( SHA1_ctx*, const byte[ SHA1_DIGEST_BYTES ] );
void SHA1_transform( word32[ SHA1_DIGEST_WORDS ],
const byte[ SHA1_INPUT_BYTES ] );
#if defined( __cplusplus )
}
#endif
#endif
Raw
sha1file.c
#include <stdio.h>
#include "sha1.h"
#define BUFFER_SIZE 1024
int SHA1_file( char* filename, byte md[ SHA1_DIGEST_BYTES ] )
{
FILE* file;
byte buffer[ BUFFER_SIZE ];
int bytes_read;
int opened = 0;
SHA1_ctx ctx;
if ( strcmp( filename, "-" ) == 0 )
{
file = stdin;
}
else
{
file = fopen( filename, "rb" );
if ( file == 0 )
{
return -1;
}
opened = 1;
}
SHA1_init( &ctx );
while ( !feof( file ) )
{
bytes_read = fread( buffer, 1, BUFFER_SIZE, file );
if ( bytes_read < BUFFER_SIZE && ferror( file ) )
{
return -1;
}
SHA1_update( &ctx, buffer, bytes_read );
}
SHA1_final( &ctx );
memcpy( md, SHA1_digest( &ctx ), SHA1_DIGEST_BYTES );
if ( opened )
{
fclose( file );
}
return 0;
}
const char* hex_digest( byte md[ SHA1_DIGEST_BYTES ] )
{
int i;
static char hex[ SHA1_DIGEST_BYTES * 2 + 1 ];
for ( i = 0; i < SHA1_DIGEST_BYTES; i++ )
{
sprintf( hex + 2 * i, "%02x", md[ i ] );
}
hex[ sizeof( hex ) - 1 ] = '\0';
return hex;
}
int main( int argc, char* argv[] )
{
int i;
byte digest[ SHA1_DIGEST_BYTES ];
int status;
if ( argc == 1 )
{
status = SHA1_file( "-", digest );
if ( status < 0 )
{
perror( "(stdin)" );
}
else
{
printf( "%s\n", hex_digest( digest ) );
}
}
else
{
for ( i = 1; i < argc; i++ )
{
status = SHA1_file( argv[ i ], digest );
if ( status < 0 )
{
perror( argv[ i ] );
return 1;
}
else
{
printf( "%s %s\n", hex_digest( digest ), argv[ i ] );
}
}
}
return 0;
}
Raw
sha1test.c
#include <stdio.h>
#include <time.h>
#include "sha1.h"
#include "timer.h"
byte b;
#define BUF_SIZE 1024
int main( int argc, char* argv[] )
{
SHA1_ctx ctx;
byte buf[ BUF_SIZE ];
int len;
int i;
long secondCount;
const byte* digest;
/* test 1 data */
const byte* test1 = "abc";
word32 result1[ 5 ] = {
0xA9993E36, 0x4706816A, 0xBA3E2571, 0x7850C26C, 0x9CD0D89D };
/* test 2 date */
const byte* test2 =
"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq";
word32 result2[ 5 ] = {
0x84983E44, 0x1C3BD26E, 0xBAAE4AA1, 0xF95129E5, 0xE54670F1 };
/* test 3 data */
/* test 3 is 1,000,000 letter "a"s. */
/* fill test 3 with "a"s and hash this 5000 times */
byte test3[ 200 ];
word32 result3[ 5 ] = {
0x34AA973C, 0xD4C4DAA4, 0xF61EEB2B, 0xDBAD2731, 0x6534016F };
/* test 1 */
printf( "test 1\n\n" );
SHA1_init( &ctx );
SHA1_update( &ctx, test1, strlen( test1 ) );
SHA1_final( &ctx );
printf( "SHA1(\"%s\") = \n\t", test1 );
/* illustrating printing using output of SHA1_digest function */
digest = SHA1_digest( &ctx );
for ( i = 0; i < 20 ; i++ )
{
printf( "%02x", digest[ i ] );
}
if ( memcmp( ctx.H, result1, 20 ) == 0 )
{
printf( " test ok\n" );
}
else
{
printf( " test failed\n" );
}
printf( "\n" );
/* test 2 */
printf( "test 2\n\n" );
SHA1_init( &ctx );
SHA1_update( &ctx, test2, strlen( test2 ) );
SHA1_final( &ctx );
/* illustrating printing using ctx.H values directly */
printf( "SHA1(\"%s\") = \n\t", test2 );
for ( i = 0; i < 5; i++ )
{
printf( "%08x", ctx.H[ i ] );
}
if ( memcmp( ctx.H, result2, 20 ) == 0 )
{
printf( " test ok\n" );
}
else
{
printf( " test failed\n" );
}
printf( "\n" );
/* test 3 */
printf( "test 3\n\n" );
/* we'll time test3 to see how many Mb/s we can do */
timer_start();
SHA1_init( &ctx );
memset( test3 , 'a', 200 ); /* fill test3 with "a"s */
for( i = 0; i < 5000; i++ ) /* digest 5000 times */
{
SHA1_update( &ctx, test3, 200 );
}
SHA1_final( &ctx );
timer_stop();
printf( "SHA1(\"a\" x 1,000,000) = \n\t" );
for ( i = 0; i < 5; i++ )
{
printf( "%08x", ctx.H[ i ] );
}
if ( memcmp( ctx.H, result3, 20 ) == 0 )
{
printf( " test ok\n" );
}
else
{
printf( " test failed\n" );
}
printf( "\n" );
/* report timing information */
printf( "speed: %.2lf Mb/s\n", 1 / ( timer_time() / 1000000.0 ) );
return 0;
}
Raw
timer.c
#include <time.h>
#include "timer.h"
#if defined( THINK_C )
#elif defined( DOS )
#include <conio.h>
#include <dos.h>
#elif defined( unix )
#include <sys/time.h>
#endif
#include <time.h>
word32 tick;
timer timer_at_start;
timer timer_at_end;
word32 find_tick_us( void )
{
#define delta 0.00000001
timer t1, t2;
double elapsed;
timer_read( &t1 );
/* tight loop until a tick happens */
/* if it is very high resolution, this may be inaccurate */
/* but if it is very high resolution, we haven't got a problem anyway */
do
{
timer_read( &t2 );
}
while ( timer_usecs( &t1 ) == timer_usecs( &t2 ) &&
timer_secs( &t1 ) == timer_secs( &t2 ) );
elapsed = timer_interval( &t1, &t2 );
/* see how many us the tick took */
return (word32) ( elapsed + 0.5 - delta );
}
void timer_read( timer* su )
{
#if defined( THINK_C )
struct tm t;
time( &t );
su->secs = t.tm_sec;
su->usecs = 0;
/* 780000 ticks/sec resolution timer goes here */
/* #elif DOS */
/* anyone care to write the code for DOS? */
#elif defined( unix )
struct timeval tv;
gettimeofday( &tv, 0 );
su->secs = tv.tv_sec;
su->usecs = tv.tv_usec;
#else
/* fall back */
time_t t;
t = time( 0 );
su->secs = t;
su->usecs = 0;
#endif
}
/* return difference in usecs */
void timer_diff( timer* s, timer* e, timer* diff )
{
timer* t;
double interval;
if ( timer_gt( s, e ) ) /* s > e */
{
t = s; s = e; e = t; /* swap( s, e ) */
}
interval = ( ( (double) e->secs ) - ( (double) s->secs ) )
* 1000000.0 + ( (double) e->usecs ) - ( (double) s->usecs );
/* if diff is not NULL, store the difference between end and start in it */
if ( diff )
{
diff->secs = interval / 1000000.0;
diff->usecs = interval - diff->secs;
}
}
double timer_interval( timer* s, timer* e )
{
timer* t;
double interval;
if ( timer_gt( s, e ) ) /* s > e */
{
t = s; s = e; e = t; /* swap( s, e ) */
}
interval = ( ( (double) e->secs ) - ( (double) s->secs ) )
* 1000000.0 + ( (double) e->usecs ) - ( (double) s->usecs );
/* return interval in usecs */
return interval;
}
Raw
timer.h
#if !defined( _timer_h )
#define _timer_h
#include "types.h"
#if defined( __cplusplus )
extern "C" {
#endif
typedef struct timer
{
word32 secs;
word32 usecs;
} timer;
#if defined( THINK_C )
#define tick_us() 1000000
/* 780000 ticks/sec resolution timer goes here */
/* tick_us() ( 1000000.0 / 780000.0 ) */
#else
extern word32 tick;
#define tick_us() ( tick ? tick : tick = find_tick_us())
#endif
void timer_read( timer* );
void timer_diff( timer*, timer*, timer* );
double timer_interval( timer*, timer* );
#define timer_secs( t ) ( (t)->secs )
#define timer_usecs( t ) ( (t)->usecs )
word32 find_ticks_sec( void );
/*************************** useful macros ***************************/
extern timer timer_at_start;
extern timer timer_at_end;
#define timer_start( ) ( timer_read( &timer_at_start ) )
#define timer_stop( ) ( timer_read( &timer_at_end ) )
#define timer_time( ) ( timer_interval( &timer_at_end, &timer_at_start ) )
#define timer_lt( t, u ) ((t)->secs < (u)->secs || \
(t)->secs == (u)->secs && (t)->usecs < (u)->usecs )
#define timer_gt( t, u ) timer_lt( u, t )
#if defined( __cplusplus )
}
#endif
#endif
Raw
types.h
#if !defined( _types_h )
#define _types_h
#include <limits.h>
#define word unsigned
#define byte unsigned char
#define bool byte
#define true 1
#define false 0
#define word8 unsigned char
#define int8 signed char
#define int16 signed short
#define word16 unsigned short
#if ( ULONG_MAX > 0xFFFFFFFFUL )
#define int32 signed int
#define word32 unsigned int
#define int64 signed long
#define word64 unsigned long
#else
#define word32 unsigned long
#define int32 signed long
#if defined( __GNUC__ )
#define int64 signed long long
#define word64 unsigned long long
#endif
#endif
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment