Re: [TLS] TLS Client Puzzles

Hi, Yoav.  Brandon Williams pointed that IPsecME doc out to me earlier today
and it's linked from later on in the draft.

I was proposing something very similar using a SHA256 or HMAC-SHA256 as a
starting point.
Based on discussion here last year, I let the puzzle level parameter be
specified directly
(rather than as an exponent) as that allows servers to scale difficulty
more linearly.
I believe that for this proposed puzzle, the average solution time should
be
half the worst-case time for a given client (but the best case could be
better).

Incorporating a puzzle with a memory-hard component (I give one poor example
where that component is symmetric) may be an option for mobile clients who
are more CPU constrained than memory-bandwidth constrained.  We have
some other ideas here we're still exploring.

Thanks, Erik

On Thu, Jul 2, 2015 at 6:23 PM, Yoav Nir <ynir.ietf@gmail.com> wrote:

> Hi, Erik
>
> You might be interested in the similar work we’re doing at IPsecME:
> https://tools.ietf.org/html/draft-ietf-ipsecme-ddos-protection-01#section-3
>
> After discussing multiple puzzle schemes, we (for now) settled on a puzzle
> that uses a MAC function such as HMAC-SHA256.
>
> The server sets the puzzle level to n and generates a calculable challenge
> (for TLS it could be random). The client finds a key k for the MAC function
> such the result of MAC(k,challenge) has at least n trailing zero bits.
>
> The expected time to solve such a puzzle is 2^n invocations of the MAC
> function. There are two issues:
>   1. The time it takes to find a key that works varies a lot. A puzzle
> that takes on average 1 second to solve could take an unlucky client half a
> minute.
>   2. Clients are diverse. Mobile phones and embedded devices are far
> weaker than desktop computers. What’s hard enough for one machine is too
> hard for another.
>
> We can solve #1 by increasing the number or required distinct solutions
> while reducing the number of zero bits:
> http://www.ietf.org/mail-archive/web/ipsec/current/msg09844.html
>
> We don’t know how to solve #2.
>
> Yoav
>
> On Jul 3, 2015, at 12:40 AM, Erik Nygren <erik+ietf@nygren.org> wrote:
>
> Following a discussion last year in Denver, I've written up a proposal
> for a TLS Client Puzzles extension.  It is specific to TLS 1.3 in that
> it is constructed using the HelloRetryRequest request flow (although
> it could be adapted to HelloVerifyRequest with prior versions of DTLS).
>
> The puzzles here are placeholders meant as a starting-point for discussion
> (and also take in some feedback from discussions on this list last year)
> and will likely evolve.
>
>         Erik
>
>
> ---------- Forwarded message ----------
> From: <internet-drafts@ietf.org>
> Date: Thu, Jul 2, 2015 at 5:30 PM
> Subject: New Version Notification for
> draft-nygren-tls-client-puzzles-00.txt
> To: Erik Nygren <erik+ietf@nygren.org>
>
>
>
> A new version of I-D, draft-nygren-tls-client-puzzles-00.txt
> has been successfully submitted by Erik Nygren and posted to the
> IETF repository.
>
> Name:           draft-nygren-tls-client-puzzles
> Revision:       00
> Title:          TLS Client Puzzles Extension
> Document date:  2015-07-02
> Group:          Individual Submission
> Pages:          12
> URL:
> https://www.ietf.org/internet-drafts/draft-nygren-tls-client-puzzles-00.txt
> Status:
> https://datatracker.ietf.org/doc/draft-nygren-tls-client-puzzles/
> Htmlized:
> https://tools.ietf.org/html/draft-nygren-tls-client-puzzles-00
>
>
> Abstract:
>    Client puzzles allow a TLS server to defend itself against asymmetric
>    DDoS attacks.  In particular, it allows a server to request clients
>    perform a selected amount of computation prior to the server
>    performing expensive cryptographic operations.  This allows servers
>    to employ a layered defense that represents an improvement over pure
>    rate-limiting strategies.
>
>    Client puzzles are implemented as an extension to TLS 1.3
>    [I-D.ietf-tls-tls13] wherein a server can issue a HelloRetryRequest
>    containing the puzzle as an extension.  The client must then resend
>    its ClientHello with the puzzle results in the extension.
>
>
>
>
> Please note that it may take a couple of minutes from the time of
> submission
> until the htmlized version and diff are available at tools.ietf.org.
>
> The IETF Secretariat
>
>
> _______________________________________________
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls
>
>
>