SIPPING C. Jennings
Internet-Draft Cisco Systems
Expires: August 19, 2005 February 18, 2005
SIP Computational Puzzles
draft-jennings-sip-hashcash-01
Status of this Memo
This document is an Internet-Draft and is subject to all provisions
of section 3 of RFC 3667. By submitting this Internet-Draft, each
author represents that any applicable patent or other IPR claims of
which he or she is aware have been or will be disclosed, and any of
which he or she become aware will be disclosed, in accordance with
RFC 3668.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as
Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on August 19, 2005.
Copyright Notice
Copyright (C) The Internet Society (2005).
Abstract
One of the techniques used in SPAM prevention and various solutions
for denial of service attacks is to force the SIP client requesting a
service to perform a calculation that limits the rate and increases
the cost of the request. This draft defines a way to allow a UAS to
ask the UAC to compute a computationally expensive hash based
function and present the result to the UAS. Although the computation
is expensive for the UAC to compute, it is cheap for the UAS to
verify. The solution also allows for proxies to compute and check
Jennings Expires August 19, 2005 [Page 1]
Internet-Draft SIP Puzzles February 2005
the puzzle on behalf of the UAC or UAS.
1. Overview
This specification extends RFC 3261 [3] and defines a mechanism for a
proxy or UAS to request that a UAC compute the solution to a puzzle.
The puzzle is based on finding a value called the pre-image that,
when hashed with SHA1 [4], results in a specific value referred to as
the image. The goal is for the UAC to find a pre-image that will
SHA1 hash to the correct image. The UAS provides a partial pre-image
with some of the low order bits set to zero, together with the number
of bits in the pre-image that have been set to zero.
The UAS provides the puzzle information using a 419 response, and the
UAC resubmits the request along with the solution to the puzzle. The
high level flow of information is shown below.
UAC UAS
| Request |
|------------------------->|
| |
| 419 with Puzzle |
|<-------------------------|
| |
| Request with Solution |
|------------------------->|
| |
This specification defines the 419 response code along with a new
header, called Puzzle, to carry the puzzle and solution.
2. Definitions
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [2].
3. Puzzles
The normative definition of a puzzle is as follows. A puzzle is four
values: an integer number referred to as work, a pre-image string, an
image string, and a integer number referred to as value. There MUST
exist a value X such that all but the "work" number of low order bits
of X match the pre-image string, and the SHA1 hash of the string
formed by the concatenation of "z9hG4bK" and X results in a value Y,
where the "value" number of low order bits of Y are the same as those
bits in the image string. The SHA1 hash is computed as described in
Jennings Expires August 19, 2005 [Page 2]
Internet-Draft SIP Puzzles February 2005
RFC 3174 [4]. The value X is the solution to the puzzle. The 'work'
number of low order bits of the pre-image MUST be zero.
This can all be described in a more mathematical way. The notation
low(v,x) returns the low v low order bits of x, and zero(v,x) returns
x with the low v bits set to zero. The | operator signifies string
concatenation. The solution to the puzzle can be considered finding
an X such that both the following are true:
low( value, image ) = low( value, sha1( "z9hG4bK" | X )
zero( work, X ) = zero( work, pre-image )
The pre-image forms a constraint on X. The value of X is the same
pre-image other than the low 'work' bits that are set to zero in the
pre-image. The 'value' is the number of bits that match in the
solution and is typically set to 160, which is the full size of the
SHA1 hash result.
The following is a non-normative way for a UAS or proxy to construct
a puzzle. The following strings are concatenated:
1. a secret that only this device knows. This would typically be a
crypto random string of bits;
2. the current time, rounded to the nearest minute;
3. the URI of the request, the Call-ID, the From tags, and the
branch tag for a proxy or the To tag for a UAS.
The string is hashed with SHA1 to form the pre-image. The pre-image
is appended to the string "z9hG4bK", and the SHA1 hash of this is
computed to get the value of the image. A value 'work' indicates how
many bits of the pre-image are to be removed. The value 'work' could
be a configurable parameter, or it could be dynamically discovered by
the software based on how long a hash should take and the speed of
the computer it was running on. In the latter case, the resulting
software would automatically choose larger values of 'work' as
computers get faster. The low order 'work' bits of the pre-image are
set to zero. The puzzle consists of the chosen value of 'work', the
pre-image (with the low order bits set to zero), the image, and the
'value'. The 'value' would typically be set to 160 as this is the
size of the SHA1 hash.
4. Semantics
4.1 UAS Creating Puzzle
When a UAS wishes to challenge a request, it MAY create a puzzle,
encode this puzzle in a Puzzle header field value, and return the
Jennings Expires August 19, 2005 [Page 3]
Internet-Draft SIP Puzzles February 2005
puzzle in a 419 response.
4.2 UAC Receiving Puzzle
When a UAC receives a 419 response, it needs to look at the 'work'
and 'value' requested and decide whether or not to try to solve this
puzzle. This decision can be made based on the programmed policy and
possibly human input. The UAC should not tackle a puzzle that will
take longer than the age of the universe to solve. If the UAC
chooses to try to solve the puzzle then it proceeds along the
following steps:
1. Check that the 'work' bottom bits of the pre-image are all zero.
If they are not, this is an invalid puzzle and the 419 response
MUST be considered an error response.
2. Set Y to low( value, image ).
3. Create a loop where X ranges from the value of the pre-image to
the value of the pre-image plus 2 raised to power of the 'work'.
4. For each interaction through the loop check if low( value, sha1(
"z9hG4bK" | X )) equals Y. If it does, a solution X has been
found and the loop can terminate.
If the loop terminates without a solution being found, the puzzle was
bad and the 419 response MUST be considered as an error response.
Once the solution to the puzzle, X, is found, a new request is formed
by copying the old request and adding an additional puzzle header
field value. The new puzzle header field value MUST have the 'work'
set to 0, the pre-image set to the value X, the image set to the
value of the image in the original puzzle, and the value parameter
set to the same as the value parameter in the original puzzle. Note
that if a request was challenged by one proxy and a new request was
generated with a solution, and then this request was challenged by a
second proxy, a third request would be generated that had two Puzzle
header field values. If a UAC, through some out of band mechanism,
knows that it will be challenged and what the puzzle will be, it MAY
include the appropriate puzzle header field value in the initial
request.
4.3 Proxy Behavior
SIP allows proxies to act as UASs when generating 4xx responses.
This same mechanism can be used to allow a proxy to generate the
challenge on behalf of a UAS in its domain.
Proxies may also act on behalf of the UAC and compute the solution to
a puzzle on behalf of the UAC in either a request or response that
passes through the proxy. Typically a proxy would only do this for a
Jennings Expires August 19, 2005 [Page 4]
Internet-Draft SIP Puzzles February 2005
UAC that had authenticated to the proxy and for which the proxy had a
service relationship.
5. Example
TBD
6. Syntax
The Puzzle header field carries the puzzle and solution information.
It has a parameter called 'work' that has the number of bits of the
pre-image that have been set to zero for this puzzle. It has a
parameter called 'pre' that carries the pre-image string base64
encoded, and a parameter called 'image' that carries the image string
base64 encoded. In addition there is a parameter called 'value' that
indicates how many bits of the resulting hash will match the 'image'
string. The base64 encoding is done as described in RFC 3548 [1].
When the header field value is carrying a solution to a puzzle, the
work parameter will be set to zero.
Example:
Puzzle: work=10; pre="XPokF1n0+NG6iwRcYzeXuETrtDo=";
image="XPokF1n0+NG6iwRcYzeXuETrtDo="; value=160
The ABNF for the header is:
Puzzle = "Puzzle" HCOLON puzzle-parm *(COMMA puzzle-param)
puzzle-param = puzzle-bits SEMI puzzle-pre SEMI puzzle-image
SEMI puzzle-value *( SEMI generic-param )
puzzle-work = "work=" 1*DIGIT
puzzle-value = "value=" 1*DIGIT
puzzle-pre = "pre=" quoted-string
puzzle-image = "image=" quoted-string
This document updates the dreaded Table 2 of RFC 3261 to be:
Header field where proxy ACK BYE CAN INV OPT REG
------------ ----- ----- --- --- --- --- --- ---
Puzzle amr o o - o o o
SUB NOT REF INF UPD PRA
--- --- --- --- --- ---
o o o o o o
Jennings Expires August 19, 2005 [Page 5]
Internet-Draft SIP Puzzles February 2005
7. Security Considerations
Still TBD.
The concatenation with "z9hG4bK" is done so that this mechanism
cannot be used as a distributed computation to reverse arbitrary hash
values, as that would present a security risk for other hash based
security schemes.
TODO - Advice on selecting the size of 'work'.
TODO - Comment on proof of work proven not to work paper.
8. IANA
This specification registers a new header and a new response code.
IANA is requested to make the following updates in the registry at:
http:///www.iana.org/assignments/sip-parameters
8.1 Puzzle Header
Add the following entry to the header sub-registry.
Header Name compact Reference
----------------- ------- ---------
Puzzle [RFCXXXX]
8.2 419 Response
Add the following entry to the response code sub-registry under the
"Request Failure 4xx" heading.
419 Puzzle Required [RFCXXXX]
9. Acknowledgments
This approach was motivated by [5].
10. References
10.1 Normative References
[1] Josefsson, S., "The Base16, Base32, and Base64 Data Encodings",
RFC 3548, July 2003.
[2] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Jennings Expires August 19, 2005 [Page 6]
Internet-Draft SIP Puzzles February 2005
Levels", BCP 14, RFC 2119, March 1997.
[3] Rosenberg, J., Schulzrinne, H., Camarillo, G., Johnston, A.,
Peterson, J., Sparks, R., Handley, M. and E. Schooler, "SIP:
Session Initiation Protocol", RFC 3261, June 2002.
[4] Eastlake, D. and P. Jones, "US Secure Hash Algorithm 1 (SHA1)",
RFC 3174, September 2001.
10.2 Informational References
[5] Black, A., "http://www.hashcash.org/", February 2005.
Author's Address
Cullen Jennings
Cisco Systems
170 West Tasman Drive
MS: SJC-21/2
San Jose, CA 95134
USA
Phone: +1 408 421 9990
EMail: fluffy@cisco.com
Jennings Expires August 19, 2005 [Page 7]
Internet-Draft SIP Puzzles February 2005
Intellectual Property Statement
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
Disclaimer of Validity
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Copyright Statement
Copyright (C) The Internet Society (2005). This document is subject
to the rights, licenses and restrictions contained in BCP 78, and
except as set forth therein, the authors retain all their rights.
Acknowledgment
Funding for the RFC Editor function is currently provided by the
Internet Society.
Jennings Expires August 19, 2005 [Page 8]