6

The goal of SCRAM is to determine whether the two endpoints share a common secret. SCRAM achieves this by having both parties compare/exchange $\textrm{HMAC}(s,i)$ where $s$ is the secret and $i$ is a counter/nonce. There is more to it than this, but this is the main essence. If $s$ is a high-entropy cryptographic secret, then this is fine: seeing some HMAC ...


6

Even after your updates, the first part seems unnecessary. However, steps 4-5 do indeed prevent the attacker from learning future nonces they could ask the key MAC values for. So the protocol steps 4-7 would be secure with a secure MAC. I agree with CodesInChaos that using HMAC would be better, because H(m||k) has some weaknesses, while HMAC is standard. ...


5

Yes, there are several ways in which Mallory could pretend to be Amy. One obvious way, which doesn't even involve Amy herself in any way, would be for Mallory to perform steps 1 and 2 of the protocol normally, as if he were Amy. Then, given Betty's nonce $n_b$, Mallory can start a second, parallel instance of the protocol, again pretending to be Amy, and ...


3

They're just different things. A protocol may be challenge-response or not, and zero-knowledge or not; all four combinations are possible. Plain password authentication is not challenge-response and not zero-knowledge. The manual-lookup copy protection in old games is challenge-response and not zero-knowledge. Another example would be CAPTCHA. Non-...


3

$\newcommand{\NP}{\mathsf{NP}}\newcommand{\lang}{\mathcal{L}}\newcommand{\rel}{\mathcal{R}}\newcommand{\bin}{\{0,1\}}$ Let $\lang\subseteq\bin^*$ be any $\NP$ language with a corresponding $\NP$ relation $\rel$. Now assume that every statement in $\lang$ has a short witness, i.e. a witness of constant (as in your question) or at most logarithmic length. I.e. ...


3

The attacker can use replay attack, i.e, he/she can replay a challenge that is signed by the user in the past(which is used as a challenge to server) and can send this as a nonce to the server. To avoid this, server generates and sends the challenge.The idea works if server maintains a list of previous nonce used but this has its limitations on practical ...


3

Here is a small scheme how this works : Server Client | | | r,n | S: Find s such as HMAC(s,r) = xxxx0000 | ==========> | | | C: *compute HMAC(0,r) = 123456789* | | C: *compute HMAC(1,r) = 124687946* | | C: *compute HMAC(2,r) = 164946518* | | C:...


3

This is vulnerable to a length extension attack. Given a valid nonce/MAC, the nonce can be extended to forge a new valid nonce/MAC value. This is because $m_4$ is appended to the end inside the outer hash. How this affects you will depend on how you validate your nonce. But in general, this is not a secure construction. There's probably more things wrong ...


3

This is called a proof of retrievability or provable data possession (slightly different definitions for these two concepts). You will find many papers discussing constructions. Two of the most cited papers in this area are: Shacham & Waters: Compact Proofs of Retrievability Ateniese et al: Provable Data Possession at Untrusted Stores


3

Yes, because Mallory can use Amy and Betty to get any encrypted nonce; Amy and Betty are oracles for Mallory. She just has to send the nonce she has to encrypt to either one of them and they perform the task for her (in another "authentication attempt", using step 1 & 2). Usually you protect against this kind of situation by performing an encryption ...


3

The Wikipedia article points out a good reason for using a random challenge value: preventing replay attacks. If the hash was always the same (as the hash of the symmetric key would be), then having listened in on one challenge-response cycle, a malicious listener could pass further handshake tests.


3

Yes! Here is one such scheme. Let $s=\mathcal S(x)$ be what that the question's tiny device produces for 64-bit input $x$, and $\mathcal V(s,x)$ the public verification function for that, which outputs $1$ if $s$ matches $x$, $0$ otherwise. I'll assume this resists existential forgery under adaptive chosen message attack, and we want to extend it to ...


3

You must change the IV every time. It has been noted in various places (see for example Joux "Authentication Failures in NIST version of GCM" section 3) that a single repeated IV is very likely to give an a attacker the ability to compute authentication tags for themselves. Together with the malleability of counter mode, if the attacker knows the ...


2

As long as properly implemented using secure algorithms, there is no real security difference. In both cases the protocol is secure as long as the underlying signature or encryption algorithm is. However, one difference is the random number used: In scheme A the numbers must be unique. If the server ever reuses a number, then an adversary could replay a ...


2

Designing such a challenge is Impossible. If we assume that having a connection is equal to being able to exchange any piece of knowledge at any given time then the proof of impossibility of such challenge is as follows: Proof. First assume that there is such a challenge and Alice is capable of querying such a challenge to correctly determine whether the ...


2

Since N xor C reveals the first 64 bits of S, the secret cannot be reused. Also, a MITM attacker can observe the message sent from A to B then drop it. Then the protocol cannot restart with a new nonce. If you prefer a challenge-response protocol, maybe just use S to hash the nonce and send the result to the other party.


2

First off, what you are trying to construct here is called an augmented or asymmetric password-based key exchange (aPAKE). As for your concrete construction: Does this scheme work? Yes, it will be functionally correct. Does it actually achieve the security guarantees of an aPAKE scheme? No, an attacker can look at the transcript, see $Q_s=[k]Q_a$ and knows ...


2

This is because: For the commitment $t$, it comes first and uses the difficulty of the discrete logarithm problem to protect the value $v$. Once you've published the value $t=g^v \bmod q$, if someones knows the value $v$, then they can easily verify that the value $t$ corresponds to the value $g^v \bmod q$, but on the other hand it is really difficult to ...


2

Regarding your Q1, well, ECDSA is fine as long as you have a good random generator on the signer side, while deterministic ECDSA tries to address the randomness issues and thus is good (as long as you do not include fault attacks in your model). I personally prefer Ed25519 amongst the deterministic signatures scheme, but that is a question of personal taste, ...


2

Pedersen commitments would appear to address your problem. A Pedersen commitment is a value $t = g^w h^r$ (for the witness value $w$ and a random value $r$); someone cannot recover $w$ from that value (actually, even a computationally unbounded adversary cannot do that). This is true even if $w$ is of low entropy. And, it is straight-forward to come up ...


2

Nobody should use a primitive which is known to be broken in any new development or deployment. Anything involving SHA-1 is basically deprecated at this point. A break in collision-resistance is a crack that might be exploited further by follow-on research; this happened with other hash functions in the past. Attacks only get better, they never get worse. ...


2

ZKPP is a zero-knowledge form of challenge-response authentication. I agree the 2nd quoted text in the question is unclear. Especially the sentence "challenge-response protocols improve on this". And "simple password protocols" should read "simple challenge-response protocols". In simple terms, the difference is that in a ZKPP ...


2

Is this protocol design secure? See below. What would be the advantage to use HMAC (or any other MAC) instead of AES encryption? HMAC was originally proposed as a construct that turns a Merkle-Damgaard hash function based on compression functions built from block ciphers, into a message authentication code. Although there's no decryption in HMAC, you ...


1

This isn't really how it works, on multiple levels. Here is a ciphertext that I encrypted using Vigenère: GJRYWP. Can you decrypt it ? Probably not, because depending on the key you try, you can obtain HELPME, BANANA or every other 6-letters possibility. It's the same here. Now you could "fix" this issue by giving more ciphertexts, or maybe a ...


1

Using the same certificate/private key for different purposes should not be allowed whenever possible. The answer to your question firstly relies on the security of the signature scheme you use. If the signature scheme is unforgeable, then you should be largely fine. Unforgeability means the malicious server who can chosen any messages and get the ...


1

Yes, this defeats the purpose of generating a challenge in the first place. The main reason to use a challenge-response mechanism is to prevent replay attacks and man-in-the-middle attacks. The server only knows that some signature (or other kind of answer to the challenge) is fresh, if the challenge did not exist previously. If the client generated the ...


1

Standard approach: $n=10^{12}$ challenges are drawn; assume each challenge is $k$ unbiased independent random bits; odds that there is a collision is less than $(n^2/2)\cdot2^{-k}$, by a first order approximation of the birthday problem, always erring on the safe side, and negligibly so for large $n$ and low odds of collision (our goal); we want the odds to ...


1

No, there are no problems (which I could see) with re-using the signature key in this scenario. There are two potential concerns: It may be possible to learn something about the private key using the challenge-response protocol It may be possible to re-use the signature of a run of the challenge-response protocol for TLS The first concern is clearly ...


1

From your question, I believe that what you are looking for is a proof of storage. I will point you in the direction of one paper, and you can use that to look for other work on the topic.


Only top voted, non community-wiki answers of a minimum length are eligible