Re: [Hipsec] Memory-bound puzzles in BEX

[Robert Moskowitz <[e-mail]>]

On 05/28/2010 02:28 AM, Miika Komu wrote:
> On 27/05/10 18:45, Robert Moskowitz wrote:
>
> Hi,
>
>> On 05/27/2010 11:33 AM, Miika Komu wrote:
>>> On 27/05/10 15:18, Tobias Heer wrote:
>>>
>>> Hi Tobias,
>>>
>>> I'd be leaning a bit towards CPU-bound puzzles but perhaps just
>>> because we've been just using them earlier. Big puzzles of both types
>>> can be problematic for e.g. sensor devices with limited memory and CPU
>>> capabilities, so in that sense it's a tie. Perhaps it's actually
>>> battery life (drained by CPU usage) time that seems to suffer from
>>> technological advances, so perhaps that could used to promote either
>>> of the types.
>>
>> Some good points. What is memory bound mean to a 8Gb notebook compared
>> to a 64K sensor? How do you design a memory bound puzzle that fits each?
>> Or does BEX have one and DEX have another?
>
> I think BEX and DEX should have the same puzzle. Maybe you could 
> artificially limit the puzzle difficulty in DEX and recommend a 
> smaller size (independently of what puzzle technology will be used).

Can't entirely.  DEX does not have a hash primative, nor the HMAC 
function.   Dave McGrew has told me he was looking for a good compress 
function for HIT generation from a small ECC key, but this will not be 
good to use for the puzzle as the underlying hash.  My plan is to build 
the puzzle around CMAC.  I am not sure about how appropriate CMAC is for 
this.  Another option is to use ECC encrypt function:  find a keypair 
that encrypts a value to generate the puzzle.  It would be very short 
keypairs....


>> Battery drain is a dangerous path to go down. Granted that CPU bound
>> SHOULD be harder on a battery than memory bound.
>>
>>
>>>
>>> The current CPU-based puzzles are parallelizable which means that a
>>> bot net could be used for solving a puzzle in a distributed way.
>>
>> Does this lead to memory bound puzzles as a way to mitigate botnet
>> attacks against a puzzle?
>>
>>> As an alternative, we could also switch to serialized puzzles.
>>
>> I am not getting what a serialized puzzle is.
>
> Brent Waters, Ari Juels, J. Alex Halderman, and Edward W. Felten.
> New Client Puzzle Outsourcing Techniques for DoS Resistance. In Pro-
> ceedings of the 11th ACM conference on Computer and communications
> security CCS ’04, 2004.

URL?

>
> R.L. Rivest, A. Shamir, and D. Wagner. Time-lock puzzles and timed-
> release crypto. Technical Report MIT/LCS/TR-684, MIT, 1996.

Oh, time based.  I THINK I get it.

>
>>> Anyway, I don't think this has big impact - I guess it's ok to
>>> distribute the solving in the end.
>>>
>>>> Hi everyone,
>>>>
>>>> RFC5201 states that memory bound puzzles should be reconsidered for
>>>> future versions of the document. The exact text is here:
>>>>
>>>> NOTE: The protocol developers explicitly considered whether
>>>> a memory bound function should be used for the puzzle
>>>> instead of a CPU-bound function. The decision was not to
>>>> use memory-bound functions. At the time of the decision, the
>>>> idea of memory-bound functions was relatively new and their
>>>> IPR status were unknown. Once there is more experience
>>>> about memory-bound functions and once their IPR status is
>>>> better known, it may be reasonable to reconsider this
>>>> decision.
>>>>
>>>> I am asking the list if the time for reconsideration has come. Should
>>>> we delve deeper into non CPU-bound puzzles for RFC5201-bis or should
>>>> we keep this note for future revisions.
>>>> Is there anyone with a background on memory-bound puzzles interested
>>>> in having them in RFC5201-bis?
>>>>
>>>> Best regards,
>>>>
>>>> Tobias
>>>>
>>>>
>>>>
>>>>
>>>>
>>>
>>> _______________________________________________
>>> Hipsec mailing list
>>> [e-mail]
>>> https://www.ietf.org/mailman/listinfo/hipsec
>>>
>> _______________________________________________
>> Hipsec mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/hipsec
>
> _______________________________________________
> Hipsec mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/hipsec
>