Subject: Re: [Cfrg] The SESPAKE protocol and PAKE requirements

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Tue, 19 Apr 2016 08:44:40 +0300

Dear Jörn,
Thank you for an updated version of the draft – we'll revise it one more
time in a week (a week prior to the deadline marked by Alexey yesterday).

Now I'd like only to mention a small misprint: "Cryptograpic" in reference
[P1363].

Thank you for your work on the draft.

Kindest regards,
Stanislav

2016-02-25 8:39 GMT+03:00 Stanislav V. Smyshlyaev <[email-masked]>:

> Dear Jörn,
> Thank you very much for your comments! SESPAKE will of course work with
> any underlying hash/HMAC/elliptic curve/PBKDF and we’ll prepare a new
> version of our draft which will explicitly stress it.
> I do not insist on addition of any specific words about primitives
> specification in the requirements draft. In contrary to the question with
> counters handling (our previous discussion), I think it is ok if this issue
> will be addressed by any author of a draft at his own discretion.
>
> Kindest regards,
> Stanislav
>
>
> 2016-02-23 9:52 GMT+03:00 Schmidt, Jörn-Marc <
> [email-masked]>:
>
>> Dear Stanislav,
>>
>> Thank you for your input!
>>
>> >What do you think about defining a policy of algorithm usage in PAKE
>> protocols?
>> >For example, in the current version of SESPAKE RFC draft we are based on
>> Russian standards – GOST R 34.11-2012 hash and HMAC, but of course the
>> >document that refers only to GOSTs cannot become a CFRG document.
>>
>> >Shouldn't we require multi-algorithm support – as in the PAKE
>> requirements, as in our SESPAKE?
>>
>> You mean to add a requirement to state which algorithms can be used as
>> underlying primitives?
>> I haven't analyzed SESPAKE in detail - but wouldn't it work with any
>> cryptographic hash function?
>> In case a PAKE requires a special property of the underlying hash
>> function/cipher/etc., I think this could be covered with
>> "R2: A PAKE scheme SHOULD come with a security proof and clearly state
>> its assumptions and models." by adding a sentence about useful primitives.
>>
>> I personally would leave it up to the designer of the PAKE scheme to
>> decide whether the scheme mentions a specific primitive (e.g. is specified
>> using AES & SHA2) or leaves it up to the implementer (e.g. speaking of
>> block cipher & hash function in an abstract manner). Do you think we should
>> push in one direction in the requirements draft?
>>
>> Best regards,
>>
>> Jörn
>>
>>
>>
>>
>

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Fri, 22 Apr 2016 15:41:11 +0300

Good afternoon!

I don't see any major problems with the current version of the draft, just
some proposals.

Maybe it will be helpful to add in Section 4 (after it is stressed that "PAKE
scheme should come with a security proof and also clearly state its
assumptions and used models"), which threats are most relevant (and thus
which threats must be addressed in adversary models considered in secutiy
proofs)? For instance, a threat of distinguishing a key from a random
string and a threat of false authentication.

And one more small misprint: after "However, each proof and model is based
on assumptions" the first letter in "Often" shouldn't be capital.

Best regards,

Stanislav V. Smyshlyaev, Ph.D.,

Head of Information Security Department,

CryptoPro LLC

2016-04-19 11:43 GMT+03:00 Schmidt, Jörn-Marc <
[email-masked]>:

> Hi Stanislav,
>
> thank you for the feedback. I'm looking forward to your comments.
>
> Best regards,
>
> Jörn
>
> -----Ursprüngliche Nachricht-----
> Von: Stanislav V. Smyshlyaev [mailto:[email-masked]]
> Gesendet: Dienstag, 19. April 2016 07:45
> An: Schmidt, Jörn-Marc
> Cc: [email-masked]; [email-masked]; Paterson, Kenny; Mike
> Hamburg; Paul Lambert
> Betreff: Re: The SESPAKE protocol and PAKE requirements
>
> Dear Jörn,
>         Thank you very much for your comments! SESPAKE will of course work
> with any underlying hash/HMAC/elliptic curve/PBKDF and we’ll prepare a new
>                 >What do you think about defining a policy of algorithm
> usage in PAKE protocols?
>                 >For example, in the current version of SESPAKE RFC draft
> we are based on Russian standards – GOST R 34.11-2012 hash and HMAC, but of
> course the >document that refers only to GOSTs cannot become a CFRG
> document.
>
>                 >Shouldn't we require multi-algorithm support – as in the
> PAKE requirements, as in our SESPAKE?
>
>                 You mean to add a requirement to state which algorithms
> can be used as underlying primitives?
>                 I haven't analyzed SESPAKE in detail - but wouldn't it
> work with any cryptographic hash function?
>                 In case a PAKE requires a special property of the
> underlying hash function/cipher/etc., I think this could be covered with
>                 "R2: A PAKE scheme SHOULD come with a security proof and
> clearly state its assumptions and models." by adding a sentence about
> useful primitives.
>
>                 I personally would leave it up to the designer of the PAKE
> scheme to decide whether the scheme mentions a specific primitive (e.g. is
> specified using AES & SHA2) or leaves it up to the implementer (e.g.
> speaking of block cipher & hash function in an abstract manner). Do you
> think we should push in one direction in the requirements draft?
>
>                 Best regards,
>
>                 Jörn
>
>
>
>
>
>
>
>

---

From: Schmidt, Jörn-Marc <[email-masked]>
Date: Tue, 26 Apr 2016 12:22:30 +0000

Hi Stanislav,

thank you for reviewing the document and your feedback. 

>Maybe it will be helpful to add in Section 4 (after it is stressed that "PAKE scheme should come with a security proof and also clearly state its assumptions and used models"), which threats are most relevant (and >thus which threats must be addressed in adversary models considered in secutiy proofs)? For instance, a threat of distinguishing a key from a random string and a threat of false authentication.

I'm not completely sure how to address this. My understanding of a proof for a PAKE scheme is that Eve must not learn more than that there was a key agreement when listening to one. In case she hits the password by guessing, she wins - that's something you cannot prevent. I tried to describe this in the Section 4: 
"That is, if Eve is unable to take information from a passive attack or a single active attack and enumerate through her dictionary then the only attack left is repeated guessing attacks.  Eve learns one thing from a single active attack: whether her single guess is correct or not. In other words, the security of a PAKE scheme is based on the idea that Eve, who is trying to impersonate Alice cannot efficiently verify a password guess without interacting with Bob (or Alice) and hence is detected. "

Do you have a suggestion how to improve this section to underline specific threats? 

Best regards,

Jörn

---

From: Станислав Смышляев <[email-masked]>
Date: Tue, 26 Apr 2016 17:40:49 +0300

‎Dear Jorn,

Thank you very much for your response.

That's my point: Eve obviously can always guess the password with a nonzero probability, but that doesn't mean that we do not need to address false authentication attacks at all - this only means that it has to be proven that for a certain PAKE protocol the probability of Eve's false authentication has the form of q/|D| + \nu(n), where D is the password set, n is the security parameter, q is the limit of trials (online) and \nu(n) is negligible if all used primitives are strong. ‎

A proof of a statement of this kind is crucial to evaluate the real security (in fact, probability of a false authentication or obtaining some info about a key) for a specific allowed limit of trials, password length and alphabet and adversary resources. 

‎Thus I think it is important to specify that the PAKE proposal must have a clear (and proven) security evaluation (kind of "Pr <= q/|D| + \nu(n)" ) for threats of 1) key distinguishing and 2) false authentication. 
‎
Best regards,
Stanislav‎
  Исходное сообщение  
От: Schmidt, Jörn-Marc
Отправлено: вторник, 26 апреля 2016 г., 15:22
Кому: Stanislav V. Smyshlyaev
Копия: [email-masked]
Тема: AW: The SESPAKE protocol and PAKE requirements

Hi Stanislav,

Best regards,

Jörn

---

From: Schmidt, Jörn-Marc <[email-masked]>
Date: Wed, 27 Apr 2016 06:34:22 +0000

Hi Stanislav,

I think I got your point: it's necessary to explicitly point out what to proof, right?

What about adding something like "In particular, the proof must show that (1) a passive adversary cannot learn anything about the password by eavesdropping a key agreement and (2) the probability of an active adversary to succeed is limited by the number of guesses divided by the password-length." after the last sentence ("[...]assumptions and used models.")?

Best regards,

Jörn

-----Ursprüngliche Nachricht-----
Von: Станислав Смышляев [mailto:[email-masked]] 
Gesendet: Dienstag, 26. April 2016 16:41
An: Schmidt, Jörn-Marc
Cc: [email-masked]
Betreff: Re: The SESPAKE protocol and PAKE requirements

‎Dear Jorn,

Hi Stanislav,

Best regards,

Jörn

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Wed, 27 Apr 2016 09:54:00 +0300

Hello, Jörn!

>>  it's necessary to explicitly point out what to proof, right?
Yes, exactly!

>> What about adding something like "In particular, the proof must show
that (1) a passive adversary cannot learn anything about the password by
eavesdropping a key agreement and (2) the probability of an active
adversary to succeed is limited by the number of guesses divided by the
password-length." after the last sentence ("[...]assumptions and used
models.")?

Two points must be corrected in the sentence (2):
- not "divided by the password length", but "divided by the cardinality of
the set of possible passwords" (for example, if you use passwords of digits
0-9 of length 8, the probability of success for 3 trials is estimated not
as 3/8, but as 3/(10^8)).
- not "limited by [the number...divided...]", but something like "limited
by [the number...divided...] plus a negligible value" (it is always a
possibility with a negligible probability, that adversary breaks a CDH
instance etc).

Moreover, since the requirement (1) in your statement can be trivially
achieved without any PAKE (if you just use simple DH without any passwords,
it's OK for the case of a passive adversary), I'd prefer to modify your
statement in this way:
"In particular, the proof must show that the probability of an active
adversary to (1) pass authentication or (2) to learn anything about the
password or (3) to learn anything about the established key is limited by
the number of guesses divided by the ...."

С уважением,

Станислав Смышляев, к.ф.-м.н.,

Начальник отдела защиты информации

ООО «КРИПТО-ПРО»

2016-04-27 9:34 GMT+03:00 Schmidt, Jörn-Marc <[email-masked]
>:

> What about adding something like "In particular, the proof must show that
> (1) a passive adversary cannot learn anything about the password by
> eavesdropping a key agreement and (2) the probability of an active
> adversary to succeed is limited by the number of guesses divided by the
> password-length." after the last sentence ("[...]assumptions and used
> models.")?
>
> Best regards,
>
> Jörn
>
> That's my point: Eve obviously can always guess the password with a
> nonzero probability, but that doesn't mean that we do not need to address
> false authentication attacks at all - this only means that it has to be
> proven that for a certain PAKE protocol the probability of Eve's false
> authentication has the form of q/|D| + \nu(n), where D is the password set,
> n is the security parameter, q is the limit of trials (online) and \nu(n)
> is negligible if all used primitives are strong. ‎
>
> A proof of a statement of this kind is crucial to evaluate the real
> security (in fact, probability of a false authentication or obtaining some
> info about a key) for a specific allowed limit of trials, password length
> and alphabet and adversary resources.
>
> ‎Thus I think it is important to specify that the PAKE proposal must have
> a clear (and proven) security evaluation (kind of "Pr <= q/|D| + \nu(n)" )
> for threats of 1) key distinguishing and 2) false authentication.
> ‎
> Best regards,
> Stanislav‎
>   Исходное сообщение
> От: Schmidt, Jörn-Marc
> >Maybe it will be helpful to add in Section 4 (after it is stressed that
> "PAKE scheme should come with a security proof and also clearly state its
> assumptions and used models"), which threats are most relevant (and >thus
> I'm not completely sure how to address this. My understanding of a proof
> for a PAKE scheme is that Eve must not learn more than that there was a key
> agreement when listening to one. In case she hits the password by guessing,
> she wins - that's something you cannot prevent. I tried to describe this in
> the Section 4:
> "That is, if Eve is unable to take information from a passive attack or a
> single active attack and enumerate through her dictionary then the only
> attack left is repeated guessing attacks. Eve learns one thing from a
> single active attack: whether her single guess is correct or not. In other
> words, the security of a PAKE scheme is based on the idea that Eve, who is
> trying to impersonate Alice cannot efficiently verify a password guess
> without interacting with Bob (or Alice) and hence is detected. "
>

---

From: Schmidt, Jörn-Marc <[email-masked]>
Date: Wed, 27 Apr 2016 07:22:56 +0000

Hello Stanislav,

You're right, the two points are not precise enough - my sentence was too sloppy. I'll use your suggestion for the active adversary. I think it covers also passive adversaries - if eavesdropping leads to any information about the password, there is no "guess" needed. Which reminds me that "guess" is again not the best term - I'll use something like "interaction with legitimate parties"..

Thanks a lot!

Best regards,

Jörn

----
>- not "divided by the password length", but "divided by the cardinality of the set of possible passwords" (for example, if you use passwords of digits 0-9 of length 8, the probability of success for 3 trials is estimated not as 3/8, but as 3/(10^8)).
>- not "limited by [the number...divided...]", but something like "limited by [the number...divided...] plus a negligible value" (it is always a possibility with a negligible probability, that adversary breaks a CDH instance etc).

>Moreover, since the requirement (1) in your statement can be trivially achieved without any PAKE (if you just use simple DH without any passwords, it's OK for the case of a passive adversary), I'd prefer to modify your statement in this way:
>"In particular, the proof must show that the probability of an active adversary to (1) pass authentication or (2) to learn anything about the password or (3) to learn anything about the established key is limited by the number of guesses divided by the ...."

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Wed, 27 Apr 2016 11:11:59 +0300

Thank you for your response, Jörn, it will be a pleasure to continue our
discussion after your modifications!

Kindest regards,

Stanislav.

2016-04-27 10:22 GMT+03:00 Schmidt, Jörn-Marc <
[email-masked]>:

> Hello Stanislav,
>
> You're right, the two points are not precise enough - my sentence was too
> sloppy. I'll use your suggestion for the active adversary. I think it
> covers also passive adversaries - if eavesdropping leads to any information
> about the password, there is no "guess" needed. Which reminds me that
> "guess" is again not the best term - I'll use something like "interaction
> with legitimate parties"..
>
> Thanks a lot!
>
> Best regards,
>
> Jörn
>
> ----
> >- not "divided by the password length", but "divided by the cardinality
> of the set of possible passwords" (for example, if you use passwords of
> digits 0-9 of length 8, the probability of success for 3 trials is
> estimated not as 3/8, but as 3/(10^8)).