The STARK is a Zero-Knowlege proof system that is transparent. In other words, the prover and verifier didn't need to use a third generated parameters to produce the proof and check the validity of the claim, respectively. Conversely, it would be a lack of security in zk-SNARK systems (these schemes are based on Common Reference Strings (CRSs)).

Let there is a data center to answer the users' queries. For instance, in the CODIS system which is addressed by the STARK whitepaper, verifiers want to know whether a specific DNA profile exists in the FBI data center or not (to prevent further crimes by quickly identifying recidivists). In this term, it is so important for this data center to not only decrease the complexity of executing the protocol for each query but also be secure under the attack of a third trusted party (revealing the information and compromising the privacy by using the Master Key).

Suppose there are 1 million DNA profiles and the data center as a prover wants to produce just a proof for all profiles to convince the verifier. A crazy solution would seem to be the data center produce a proof for each profile but it is not efficient (i.e. doubly efficient).
Regarding the Reed-Solomon (RS) error-correcting codes, the prover is able to obtain the encoded function corresponding to all DNA profiles. For each RS code, $RS[F, S, \rho]$ is the family of functions $f: S\to F$ which these functions are evaluations of polynomials of degree less than $\rho|S|$. Precisely, the output of encoding is a polynomial which the prover claims if the verifier put each DNA profile in this polynomial as input the output is equal to zero (i.e. is a root of a low-degree polynomial). The significant point is that the verifier never knows any information about the rest of the profiles.

But as you know, this is not enough for the verifier to check whether the claimed function is good or bad! I mean regarding the Schwartz-Zipple lemma two distinct polynomials with degree $d$ have at most d intersections so the function $f$ is not unique for 999.999 DNA profile. Moreover, the verifier needs to check all profiles to become sure about the validity of function (i.e is a low-degree polynomial).
The way that is addressed by the authors of the STARK whitepaper is the FRI (Fast Fourier Transform Reed Solomon Interactive Proximity of Testing) scheme. It is a solution for solving the low-degree proximity testing problem. This scheme tried to reduce the number of elements in the set of S step by step to convince the verifier just by checking the low degree polynomial for a smaller polynomial instead of the original structure. (The degree of polynomial chooses less than the number of profiles to provide better soundness, for instance, a polynomial with degree 10.000 for 1 million DNA profiles)

The FRI scheme is based on Interactive Oracle Proof (IOP) systems which the verifier selects some random numbers and the prover provides corresponding oracle access for him/her. Finally, after some rounds, the verifier can decide about the correctness of the prover claim. It is possible to provide non-interactive IOP, also.

The critical point is about the arithmetization in which the prover wants to produce a proximity testing problem corresponding to a circuit satisfiability problem. In other words, the prover and verifier agree for a circuit to prove and check the validity of the execution of it, respectively. This term is based on some techniques to make to solve the problem in logarithmic complexity instead of NP-complete (3SAT is an NP problem). I just mention these techniques here and if you need to know more send a comment.

The circuit satisfiability $\to$ algebraic constraint satisfaction problem (CSP) $\to$ 3SAT $\to$ 3-Coloring problem $\to$ de-Bruijn Graphs to solve 3 coloring problem and so on.

For more information:
https://www.starkware.co/

https://vitalik.ca/

https://drive.google.com/open?id=1zzgOry0ERwTJB3PR5HXGIhrcdH_LcenB

https://drive.google.com/open?id=12K363jIO0bhDSxM_AKYVxG8eNBn9qQ0K


The catch is that for decryption to work reliably for all keys, the subkeys must be the same for encryption and decryption with order reversed. With many DES implementations, that implies the sum of the rotations in the key schedule should be a multiple of $28$, the width of the C and D registers.

Use say $15,2,2,2,2,2,2,1$ rather than your $1,1,2,2,1,2,2,1$ and you should be flying (assuming the code handles these larger values, and does not use the optimization enabled by the fact that after removing the first value in the DES key schedule table $1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1$, the $15$ remaining entries are a palindrome). Note: I have changed my suggested values so that the subkeys used match the ones in the last $8$ rounds of encryption in standard DES; that reuses some of the work made by DES designers when crafting PC-2 w.r.t. the key schedule.

Alternatively, use $1,1,2,2,2,2,2,2$ for encryption and make an extra rotation by $14$ before decryption. That way we use the same subkeys as for the first $8$ rounds of encryption in standard DES.

Update: the modified question tells us that the implementation uses different tables for encryption and decryption. In that case, $1,1,2,2,2,2,2,2$ for encryption and $14,2,2,2,2,2,2,1$ for decryption should work (with rotation counts in opposite directions and before the use of the generated subkey). The first decryption value must equal the sum of encryption values$\pmod{28}$. The following decryption values are obtained by dropping the first encryption value and reversing the list.

Caution: care should be taken that all keys bits are used about evenly and regularly, by considering the interaction of rotation counts with PC-2. Because I'm lazy I kept the original first $8$ $rotations, which is at least not disastrous in this respect.


What are the integers in an RSA PEM file?

Here is a labeled example output (don't worry I created a new key):

Which you can verify for example in Sage. Although, surprisingly, it apparently doesn't allow decryption because the exponent is too large.


I understand the question as asking for a method such that:

after step 3., we'll have a reasonably small password P2;
deciphering MJ using P1 will give "Mocking Jay";
deciphering MJ using P2 will give "The Hobbit", or a meaningful extract of that, at least comparable in size to MJ;
MJ is produced at step 2. without "The Hobbit" as input.

By an entropy argument, that's impossible; for that would imply that the amount of information necessary to go from "Mocking Jay" to "The Hobbit" (or a meaningful extract thereof) can be summed-up in the short password P2.

Update: a possibility is that "The Hobbit" (or a meaningful extract thereof) is embedded in the decoding program, but that brings back the problem stated in the last paragraph of the present answer.

Remove the requirement that MJ is produced without "The Hobbit" as input, and it becomes possible. We can devise an encryption process with input ("Mocking Jay", P1), ("The Hobbit", P2), or more generally any arbitrary collection of literary work and distinct associated passwords, producing a ciphertext; and a matching decryption procedure accepting ciphertext and password, that will produce the appropriate work for the password, and an error (or garbage) for other passwords. The system can be resistant to cryptanalysis and key search, even for relatively short passwords, if we accept that the decryption procedure requires a few seconds, which enables password stretching using e.g. scrypt.

Thanks to data compression, the ciphertext can be smaller than "The Hobbit" (I assume "Mocking Jay" is smaller). We can even think of reusing the compression dictionary built from "The Hobbit" to compress "Mocking Jay", so that the ciphertext is of size more comparable to a mediocre compression of "The Hobbit", if we accept that P2 is necessary in addition to P1 to read "Mocking Jay", or equivalently that P1 is some extension of P2, or that the cipher protecting "The Hobbit" is of mediocre security.

Update: I have no implementation in mind, but this is a relatively simple matter with competent use of data compression, key stretching, and symmetric cryptography.

Huge problem is: an intelligent person caring to analyses the decryption procedure or the file format specification will likely understand that it is intended for deniable encryption, and then the risk is high that rubber-hose cryptanalysis will be used; something that would be avoided if the original problem could be solved; but it can't.


How do you prove the soundness property of the ZKP from the paper without witness extraction (which seems not possible)?

It is perfectly possible and you've almost done it already! You are right that unknown order groups make your life very complicated when you want to build proofs of knowledge - we know results in this direction (the one you cite) -- although it should be mentioned that they break down as soon as you use a CRS (e.g. as we did in this paper).

But if you only want soundness and not the stronger knowledge extraction, you do not need to compute this cumbersome $(c_i-c'_i)^{-1}\bmod \varphi(n)$.

Let $z_i \gets y_i - y'_i$ and $d_i \gets c_i - c'_i$.

From equations (1) and (3), you get $g^{z_i} = b_{i-1}^{d_i}$.

From equations (2) and (4), you get $b_{i-1}^{z_i} = b_{i}^{d_i}$.

Therefore, it is necessarily, mathematically true that there exists an exponent $x$ such that $g^x = b_{i-1}$ and $b_{i-1}^x = b_i$. Indeed, this $x$ is equal to $z_i\cdot d_i^{-1}\bmod \varphi(n)$. So sure, you can't compute it - but the fact that it exists suffices to prove soundness of the protocol! In other words, $(z_i, d_i)$ still constitute a certificate that the word is in the language, which you can extract whenever the prover produces an accepting proof. This certificate is not a witness with respect to the target relation, but it's existence still suffices to guarantee membership to the language.

Answering questions from the comments

  Can you please point to the witness that we can extract with their protocol ? (and how? :-) )

Consider the following relation $R$: $(a,b,c)$ is in the language if there exists values $(x,y)$ such that $a^x = b^y$ and $b^x = g^y$. That is, $R((a,b,c), (x,y))$ returns 1 iff $a^x = b^y$ and $b^x = g^y$ (and $0$ otherwise). A witness for this relation is a pair $(x,y)$.

First, observe that the language captured by this relation is exactly the same as the language of tuples $(a,b,c) = (g,g^z,g^{z^2})$. The difference is that in the first case, what you see as a witness is a pair $(x,y)$ such that $a^x = b^y$ and $b^x = g^y$, while in the second case, it is a single exponent $z$ such that $a^z = b$ and $b^z = c$. This correspond to a different relation $R'$ for the same language: $R'((a,b,c), z) = 1$ iff $a^z = b$ and $b^z = c$.

In the protocol above, you indeed extract a pair $(x,y)$, which is a witness according to the relation $R$ (hence suffices to prove knowledge for a witness of membership to this language - but a witness with respect to a different relations compared to the one you had in mind, which is the second one, $R'$). Indeed, just set $y_i - y'_i$ to be the $x$ and $c_i - c'_i$ to be the $y$, and you have exactly your extracted witness (since the extractor knows of course $y_i, y'_i, c_i, c'_i$).

  But what is the proof of this soundness? To prove this, you need to prove that if a cheating prover can convince the verifier that a pair not in the language, is in the language - then it can also do something intractable. Can you perhaps tell how would you prove such a thing?

You are getting confused with the situation where we prove computational soundness using some hard problem. If a protocol is only computationally sound, then a proof will look as follow: suppose the word is not in the language, and the prover manages to provide a convincing proof of membership. Then I can use this prover to break a hard problem.

Here, we are in a scenario where the proof is much more direct: the soundness is unconditional. This means that I do not have to show that a prover that proves membership of a word outside the language can be used to break a hard problem: I can directly show that if any prover provides a successful membership proof, then necessarily, the word has to be in the language. No hard problem involved.

To spell it (a bit more) formally:

soundness: the protocol above is unconditionally sound if there does not exist a malicious prover $P$ (even with unbounded power) and a word $(a,b,c)$ outside of the language $L = \{(a,b,c) = (g,g^z,g^{z^2})\}$ such that $P$ provides a convincing membership proof for $(a,b,c)\in L$.

proof of soundness: Fix any word $(g,b_{i-1},b_i)$, and any prover $P$. Use rewinding; with non-negligible probability, we get values $(y_i, y'_i, c_i, c'_i)$ satisfying equations (1) to (4) of your questions. But this implies that there exists values $(z_i,d_i)$ such that $g^{z_i} = b_{i-1}^{d_i}$ (by 1 and 3) and $b_{i-1}^{z_i} = b_{i}^{d_i}$ (by 2 and 4). But now, those two equations imply that there exists some value $z$ such that $(g,b_{i-1},b_i) = (g, g^z, g^{z^2})$. This $z$ is in fact equal to $z_i/d_i \bmod \varphi(n)$: it exists, but you cannot compute it. But since it exists, we can conclude that the word $(g,b_{i-1},b_i)$ does in fact belong to the language $L$! In other terms: each time the prover produces a convincing proof for $(g,b_{i-1},b_i) \in L$, then it is indeed the case that $(g,b_{i-1},b_i) \in L$ -- hence, the prover cannot possibly produce an accepting proof when $(g,b_{i-1},b_i) \notin L$, which proves soundness.

  If the prover guesses the $c_i$ the verifier would send, it can send $z_i = g^{y_i}\cdot b_{i-1}^{-c_i}$ and $w_i = b_{i-1}^{y_i}\cdot b_{i}^{-c_i}$ and the verifier would accept any $b_i,b_{i-1}$ no? Now if it can do it once, it can do it twice, with probability $1/R^2$ which is negligible but still not exactly   ⇒$(g,b_{i-1},b_i) \in L$... what am I missing?

The above attack you suggest does not work, for the following reason: to execute the attack, you must guess $c_i$ and send $z_i = g^{y_i}\cdot b_{i-1}^{-c_i}$ and $w_i = b_{i-1}^{y_i}\cdot b_{i}^{-c_i}$. Then, you say "if it can do it once, it can do it twice, with probability $1/R^2$". But this is not true! Remember that when rewinding the protocol, the same first flow is reused for the two rewinds. Hence, the prover does not get any occasion to create "another" pair $(z_i, w_i)$ by guessing $c'_i$.

Now, it is still true that the above soundness proof can fail, because there is some probability, when you sample a random $c'_i$, that it is equal to $c_i$; when this happens, $c_i-c'_i = 0$, and therefore the word is not guaranteed anymore to be in the language.

But in fact, the only reason this trivial attack applies is because I decided to keep things simple, for the sake of readability. If you want to understand exactly why this issue is not a real problem, here is a high-level sketch of how the fully formal security analysis would proceed:

Sketch of the Fully Formal Proof

Assume that there is a prover $P$ that can break soundness. What (statistical) soundness formally says is that for any (possibly unbounded) candidate prover $P$ which picks a word $X$ and interacts with the verifier $V$, the probability that ($X \notin L$) AND ($V$ is convinced) must be negligible. So assuming a prover that can break soundness means assuming that there exists a $P$ which outputs a word $X$ and interacts with the honest verifier $V$, such that

$\mathsf{Pr}[X \notin L \wedge V \text{ is convinced}] \geq \varepsilon,$

for some non-negligible quantity $\varepsilon$ (warning: I'm again hiding some technicalities here about the exact quantifiers when defining "negligible" and "non-negligible").

Hence, what we have is a prover that outputs a word $X$ and interacts with $V$ such that it happens simultaneously that $X$ is not in $L$ and $V$ accept the interaction, with some non-negligible probability $\varepsilon$.

The first question is:
How do we extract from this prover the values which satisfy equations (1) to (4) in your question?

The answer I gave before was just "we use rewinding", but this does not explain why it works. A single run of the prover outputs a word $X$ and a transcript $T$ of his interaction with $V$, such that $X \notin L$ and $V$ accepts, with proba $\varepsilon$. But what we want is to get two accepting transcript, with respect to the same word $X \notin L$, and also with respect to the same first flow.

It turns out that there is a simple lemma, the splitting lemma, that allows exactly to do that -- see for example page 10 of my paper (which I already mentioned in this answer). This lemma allows to show that we can fix the word and the first flow, and repeat the rest of the protocol twice; and still, the word $X$ will not be in $L$ yet both transcripts (with the same first flow, but a different second flow) will be accepted, with overall probability at least $\varepsilon^2/4$. This is not too hard, but not entirely trivial either - it's a good exercise in probabilities.

Now, if we found two transcripts as above, then we can do exactly as I said previously and use equations (1) to (4) to verify that $X$ must be in the language, therefore reaching a contradiction (hence such a cheating prover $P$ does not exist). Note that we do not need to find these transcripts with probability 1: the simple fact that we could find them with some non-negligible probability already suffices to reach the contradiction.

Another way to view it is that extracting the witness (for the relation $R$) cannot usually be done with a single run of the protocol: you need to repeat the above procedure on average $4/\varepsilon^2$ times (which is polynomial) to successfully extract a witness by the above procedure. This issue is exactly the reason why the standard definition of proofs of knowledge does not say that the witness can be extracted in strict polynomial time, but rather in expected polynomial time. Here, we can extract a witness successfully, but the running time of the extraction procedure will only be $O(4/\varepsilon^2)$ in expectation.


Use additional keys to thwart key compromise?

There is no one answer.  It depends why you think that keys might be compromised.  That has to depend upon a threat analysis, based upon how the protocol will be deployed  and what the most likely failure modes and forms of compromise might be.

For instance, it is pretty clear that a key that is stored in software on an Internet-connected computer is (all else being equal) probably at higher risk of compromise than a key that is stored on a computer that is never connected to any network.  This then leads to protocols where a long-term signing key is stored in a hardware security module (HSM) that's airgapped and never connected to any computer, and is used to sign certificates for emphemeral public/private keypairs, where the private key is stored on an Internet-connected computer.  Such a use of additional keys might have security benefits.

However, just adding extra keys "just in case" often doesn't make any sense, if it's not done to defeat a specific threat.  For instance, suppose we take a protocol that uses some key $k_1$ to encrypt data, and we now introduce a new key $k_2$ that is used to encrypt $k_1$.  If the key-encrypting key $k_2$ and the data-encrypting key $k_1$ are stored on the same computers, and if the underlying encryption algorithms are secure, it is not clear what failure modes would cause compromise of one of those keys without the other being compromised at the same time too -- so in such a case, adding an additional key might not add any significant security benefit.


What constructions for data authentication are subject to the birthday paradox?

It turns out that the birthday paradox figures into both the suffix-MAC $H(m \mathbin\Vert k)$ and the HMAC $H((k \oplus \mathrm{opad}) \mathbin\Vert H((k \oplus \mathrm{ipad}) \mathbin\Vert m))$, but in different ways.  And, curiously, there is no theoretical formalism in the field of ‘provable security’ for the way that it figures into suffix-MAC, which is the one that, as you observed, is practically relevant.

The quick summary is that, for a $b$-bit hash function $H$, when $k$ is unknown to an attacker, for suffix-MAC $H(m \mathbin\Vert k)$, the attacker can spend $2^{b/2}$ work offline to find messages $m_a \ne m_b$ that collide under $H$, whereas for HMAC, the attacker must interact online with your system for $2^{b/2}$ messages before they're expected to stumble upon messages $m_a \ne m_b$ that collide under $\operatorname{HMAC-}\!H_k$.

Because $2^{b/2}$ offline work is sometimes feasible, e.g. if $b = 128$ as in MD5 (which also has nongeneric collision attacks that reduce the work to something negligible), whereas $2^{b/2}$ online interactions with a single application is nearly unthinkable, when summarizing MAC security we usually paper it over and say that suffix-MAC has $b/2$ bits of security while HMAC has $b$ bits of security—but you'll find the gory details in papers analyzing the ‘provable security’ of any MAC.

In a little more detail:

The suffix-MAC construction $H(m \mathbin\Vert k)$ for an iterated hash function $H$, i.e. roughly where $H(m_0 \mathbin\Vert m_1 \mathbin\Vert \cdots \mathbin\Vert m_{n-1}) = f(\cdots(f(\mathit{IV}, m_0), m_1)\cdots, m_{n-1})$, is vulnerable to collisions in $f$: if you can find initial message blocks $m_a \ne m_b$ such that $f(\mathit{IV}, m_a) = f(\mathit{IV}, m_b) = h$, then the messages $m_a$ and $m_b$ always have the same authenticator $$H(m_a \mathbin\Vert k) = f(f(\mathit{IV}, m_a), k) = f(h, k) = f(f(\mathit{IV}, m_b), k) = H(m_b \mathbin\Vert k),$$ as do any pairs of messages that start with $m_a$ or $m_b$ and share a common prefix, $m_a \mathbin\Vert m'$ and $m_b \mathbin\Vert m'$.

An adversary who knows $f$ and $\mathit{IV}$—which are a public function and constant, respectively, in cases like SHA-256—can work offline to try to find such a collision.  Once they've found one, and they will know when they've found one because they can just test it, they may be able to break your application immediately with probability 1 and no prior interaction.

This is practically relevant: cryptosystems based on MD5 and SHA-1 were broken in practice by finding such collisions, and MD5 was even exploited to forge HTTPS certificates in a widely publicized incident of international industrial sabotage by the United States and Israel against Iran (although with RSASSA-PSS signatures, rather than with symmetric authenticators).

What's curious is that there's no theoretical formalism in the field of provable security about this.  Every fixed compression function like SHA-256 has collisions.  We just don't know any yet.  We can't say anything formal about an attacker's success probability after a certain amount of work for attacks on these constructions, because there is nothing randomized about them.  Either the attacker knows a collision (and one certainly exists) or they don't, and while we can informally conjecture about their expertise in cryptanalysis, no formalism in cryptography helps with quantifying probabilities about that knowledge.
$\operatorname{HMAC-}\!H_k$ is vulnerable to an internal collision in $H((k \oplus \mathrm{ipad}) \mathbin\Vert m)$: for every $k$, there are guaranteed to be many pairs of messages $m_a \ne m_b$ such that $$H((k \oplus \mathrm{ipad}) \mathbin\Vert m_a) = H((k \oplus \mathrm{ipad}) \mathbin\Vert m_b).$$  In that case, the two messages share a common authentication tag under the key $k$, and so if the sender provides an authentication tag for $m_a$, the attacker can replace the message by $m_b$ and leave the tag intact, and the receiver will be none the wiser.  (A collision may also happen in the outer $H$, of course.)

But the attacker can't try offline to test whether $m_a$ and $m_b$ collide under $\operatorname{HMAC-}\!H_k$, because they don't know $k$, in the formalism of provable security.  So, the attacker's best strategy (in the cases where we do have security reductions) is just to try substituting messages without changing their authentication tags, and the expected number of attempts at forgery before a collision will be about $2^{b/2}$.

The same applies to other constructions, like CMAC, and this is why, if you look closely at the security reductions for many of these constructions, you will find references to the birthday bound, and forgery probabilities in terms of numbers of queries $q$ as long as $q \lll 2^{b/2}$.  A notable exception to this is polynomial evaluation one-time MACs, which work differently, but that will have to be a bedtime story for another night.


Decrypting Multi-Prime RSA with e, N, and factors of N given

In multi-prime RSA, the definition of a valid private exponent $d$ is the same as in regular RSA: any $d$ such that $e\,d\equiv1\pmod{\lambda(N)}$, where $\lambda$ is Carmichael's function. That includes any $d$ such that $e\,d\equiv1\pmod{\varphi(N)}$, where $\varphi$ is Euler's totient.

With the factorization of $N$ into primes $p$, $q$, $r$, $s$ known and under the assumption that these 4 primes are distinct, computing a valid $d$ can be done as
$$d\gets e^{-1}\bmod\operatorname{lcm}(p-1,q-1,r-1,s-1)$$
or
$$d\gets e^{-1}\bmod\bigl((p-1)\,(q-1)\,(r-1)\,(s-1)\bigr)$$

If some of the primes are equal, we need to use more general expressions of $\lambda(N)$ or $\varphi(N)$. The simplest might be that $\varphi(N)$ is the product of factors of $N$ with the first occurrence of a unique prime replaced by one less than this prime. For example, if $p=q$ and $r=s$ and $p\ne r$, we can use
$$d\gets e^{-1}\bmod\bigl((p-1)\,q\,(r-1)\,s\bigr)$$

Also, be aware that the function $x\mapsto x^e\bmod N$ no longer is a bijection over $\Bbb Z_n$; in other words, some rare ciphertexts can correspond to multiple plaintexts. That affects plaintexts that are non-zero multiples of a prime present two times in the factorization.

For example, with

$N=67\times71^2\times73=24655531$,
$\varphi(N)=66\times70\times71\times72=23617440$,
$e=13$,
$d=10900357$, but we have the problem that
$71^e\bmod N$ and $3125420^e\bmod N$ both are $6603710$.

Note: the rationale of using multi-prime RSA is to obtain speedups that require not using $d$; but using $d$ will work anyway, only slower.


How long it takes for new cryptographic results to become generally accepted?

How long would it take until most practitioners evaluate and peer review it [...]?

Unfortunately peer review tends to be more of a "push" than a "pull" based process. Meaning that experts in that area tend not to crawl the internet for schemes to investigate and "declare good to use" but rather that the authors of such schemes work hard to get that attention. And even then, most schemes - even those with somewhat famous authors - have excellent chances at never being used seriously in practice. This is the case even if the relevant people have used much of their time to analyse such proposals and found no flaws.
The best example for this is actually the on-going NIST Post-Quantum Competition where chances are really slim for any candidate kicked out in the third round to see any real usage.
So even if a scheme is good - and it has to be reasonably secure and performant - and it is published in the right place at the right time with a large amount of serious, convincing self-analysis, there's a good chance that it never sees real usage outside of that the author implements themself.
This situation doesn't get better if the scheme in question has no properly formatted paper with lots of relevant, convincing cryptanalysis and security proofs, which hasn't even been submitted / accepted at the right venue / journal.
If one would really want to have such initial analysis it might be worth to try and hire a serious, professional cryptographer as a consultant and either have them analyse the scheme - which is unlikely to be very useful given that this kind of work takes a lot of time and thus money - or to collect (some) likely relevant initial background material to start working on the analysis in a way that is generally accepted. Additionally such professional help would likely also be able to review the analysis to give potential improvement suggestions to the analysis and its presentation to lessen the chance of an instant reject if and when it is tried to be submitted to a serious venue.


Can I use computational diffie hellman problem in the following scheme?

Well, the problem "given $X, Y$, recover $R$" is impossible, even to a computationally unbounded adversary.  The reason is that any value of the form $e(X, Y)^k$ is possible; for any set of nonzero values for $X, Y, n, m, k$, there exists values for $r, P, Q$ that is consistent with the observed $X, Y$ values, and which $R=e(X,Y)^k$

However, that is unlikely to be the only way to attack this system; as stated, your system is informationally secure (in that the attacker literally doesn't have enough information to attack the system), and that is quite rare in cryptography.  Most likely there is some additional information that is available to the attacker; what this information is is vitally important in deciding on the security of the system.


So let's assume you have the function $f$, which is publicly known, and you publish the value $y = f(x)$. And then you want to prove that you know $x$. You said $f$ is a deterministic random number generator (and I guess you meant a CSPRNG) - but from the given information I guess it's just important that it is one-way?

Anyway, there are two cases for $f$:

$f$ is defined in algebraic structures like finite groups/ rings/ fields and can be expressed as a polynomial, has structure preserving properties (like being bijective), etc. Then it might be possible to create an elegant proof of knowledge for that specific function, similar to Schnorr's protocol. But there is no catch-all method for all possible functions $f$, and it's possible that you can't find a proper proof of knowledge without revealing $x$ - it all depends on the function.
$f$ is actually non-algebraic, e.g. binary input and binary operations, and it most likely does not preserve structure of any kind, for example the practical hash functions and CSPRNGs. Then the following paper might give you an indication how this could be achieved: Zero-Knowledge Using Garbled Circuits: How To Prove Non-Algebraic Statements Efficiently by Jawurek,Kerschbaum and Orlandi (2013). SHA256 was one of the examples in there - however this is a very different kind of proof of knowledge than Schnorr's identification protocol. And of course, in this case it would also depend entirely on $f$, if this works - and if you are willing to accept its overhead. The example  in the paper took around 5 seconds for a single proof of knowledge of a SHA256 preimage.


The importance of randomness in the creation of a key

When humans generate random key, there is some bias. For instance, in your example "93298762" there are only 2 turning points where as normally there should be 4 (you can argue that it is a single sequence and it is not long enough to seriously speak about statistics, but nevertheless...)

Even if an attacker does not know what generator you used, it makes sense for him to check first (after dictionary) the keys that a human would generate. This reduces essentially the entropy and thus the resources needed to brute-force the key. That's why it is important that generator has much entropy.

In cases where a human participation is possible, like password generation, a good generator will eliminate keys that have relatively high probability to be generated by a human (dictionary keys, keys with human specific anomalies). That's why when such generator generates a key "12345678" it would eliminate it and proceed with generating until the likelihood with human generated keys is below some threshold.


What is the difference between .pem, .csr, .key and .crt and other such file extensions?

File extensions can be (very) loosely seen as a type system.

.pem stands for PEM, Privacy Enhanced Mail; it simply indicates a base64 encoding with header and footer lines. Mail traditionally only handles text, not binary which most cryptographic data is, so some kind of encoding is required to make the contents part of a mail message itself (rather than an encoded attachment). The contents of the PEM are detailed in the header and footer line - .pem itself doesn't specify a data type - just like .xml and .html do not specify the contents of a file, they just specify a specific encoding;
.key can be any kind of key, but usually it is the private key - OpenSSL can wrap private keys for all algorithms (RSA, DSA, EC) in a generic and standard PKCS#8 structure, but it also supports a separate 'legacy' structure for each algorithm, and both are still widely used even though the documentation has marked PKCS#8 as superior for almost 20 years; both can be stored as DER (binary) or PEM encoded, and both PEM and PKCS#8 DER can protect the key with password-based encryption or be left unencrypted;
.csr or .req or sometimes .p10 stands for Certificate Signing Request as defined in PKCS#10; it contains information such as the public key and common name required by a Certificate Authority to create and sign a certificate for the requester, the encoding could be PEM or DER (which is a binary encoding of an ASN.1 specified structure);
.crt or .cer stands simply for certificate, usually an X509v3 certificate, again the encoding could be PEM or DER; a certificate contains the public key, but it contains much more information (most importantly the signature by the Certificate Authority over the data and public key, of course).

There are quite a few other extensions that you will find as well:

.p8, .pkcs8 are private keys. PKCS#8 defines a way to encrypt private keys using e.g. a password. However, quite often, only the inner unencrypted PKCS#8 structure is used instead (which just defines the type of key). The inner structure can then e.g. contain a PKCS#1 formatted private key for RSA or a SEC1 one for Elliptic Curves.
[dave_thompson: X9.62 defined commonly-used formats for EC public key and parameters (curve), but I'm pretty sure not private key although I won't spend my money to verify; for publickey and parameters SEC1 cites X9.62,  and rfc5480 cites both SEC1 and X9.62, but for privatekey rfc5915 cites only SEC1 which cites nothing. Also I would say: generally not transported, but still fairly commonly PEM encoded, because many programs that use a separate key file or section, often via the OpenSSL library, require or prefer PEM: Apache httpd, nginx, haproxy, nodejs, python, wget and some curl; also Apache tomcat depending on version and option. But Java natively uses PKCS#8 DER, unencrypted.]

.p12 or .pfx is a PKCS#12 defined key store, commonly password protected. It can contain trusted certificates, private key(s) and their certificate chain(s), but also other information such as secret keys and (very uncommonly) other personal information; .p12 is usually binary / DER encoded. PKCS#12 has lots of options plus extensions (i.e. attribute OIDs) with varying support, so it is not safe to assume that every P12 file will work in anything that uses (some) P12 files.

.crl is a Certificate Revocation List which is defined within the X.509v3 certificate specifications, and this is usually DER encoded as well.

.p7b or .p7c is a specialized kind of PKCS#7/CMS message: a SignedData that doesn't contain data and isn't signed, and is used only to as a way to conveniently handle a group of certificates and/or CRLs. In particular it is often used as a way to handle the certificates which make up a 'chain' or 'bundle' as a single, well-defined unit. Other kinds of PKCS#7/CMS messages exist but are less used, and may have extensions like .p7 or .p7m, except that detached signatures, as a special case, are usually .p7s. In addition S/MIME is layered on top of CMS: S/MIME messages are really CMS messages wrapped in MIME format, and as such are usually identified by the MIME-type (aka media-type) in the message not by a file extension.

Beware that not everyone may use the same extensions - there is no official register or anything like that. You're probably better off using the POSIX file command line utility first.

There are also proprietary formats that are relatively common.

.jks stands for Java Key Store. It can be used to store private keys with their certificate chains (root CA, intermediate CA's, leaf certificates or just a single self-signed certificate), certificates of other parties (usually but not necessarily CAs) to form a trust store, or both. The JKS format (like the Java KeyStore API) is technically agnostic and can use any type of certificate for which the installed crypto-providers offer a CertificateFactory object, but in practice the only CertificateFactory implemented is X.509 (or PKIX) and the main applications in Java for keystores - code signing, S/MIME, XML/SOAP, and SSL/TLS - use only X.509. .jks key stores are password protected, using a proprietary (and weak) cipher Sun created back during the munitions-list era, but they have been deprecated since 2017 in favor of PKCS#12 with transitional support.

[dave_thompson: the JSON formats, JWS/JWE/JWT/JWK, are now common for communication (and not proprietary), but IME rarely stored in distinct files]


Different padding rules for Merkle–Damgård and Keccak/sponge function

Actually, the Merkle–Damgård construction also specifies a padding bit after the message. The length is there the ensure that a padded message cannot be the suffix of a different longer message. A collision at the prefix leads to a collision in both messages.
With a padding bit, a singe byte message 0x30 vs a 2 byte message 0x30 0x00 are padded to 0x30 0x80 and 0x30 0x00 0x80, ensuring the compression function input is not the same for that block, even without the message length at the end of the padding.
The sponge construction does not require the same message suffix protection because of the way it mixes the input into the state. The size of the state as well as how much data is mixed/squeezed (block size) determine the chance of both a state collision as well as an output collision.
Example collision over multiple blocks
Here we have a toy hash function with a 48-bit block size and 48-bit internal state size. It has no length padding, but does use a single bit padding after the message. The hash is not secure, and suffers from a collision between "THIS IS NOT " and "ENACT ", which are unpadded 2 block and 1 block inputs to the compression function:
Message 1 "THIS IS NOT A TEST!", length 19 bytes (152 bits):
initial value     Block 1 "THIS I"  Block 2 "S NOT "
0x67452301AB89    0x544849532049    0x53204E4F5420

** state collision here **

Block 3 "A TEST"  Block 4 "!" and padding bit
0x412054455354    0x218000000000

Hash Output
0xFE25B6A1C8C0

Message 2 "ENACT A TEST!", length 13 bytes (104 bits):
initial value     Block 1 "ENACT "
0x67452301AB89    0x544849532049

** state collision here **

Block 2 "A TEST"  Block 3 "!" and padding bit
0x412054455354    0x218000000000

Hash Output
0xFE25B6A1C8C0

Because the last 2 input blocks are the same and (since the padding is the same), the state collision at the unpadded prefixes causes a collision in the outputs.
We modify the hash function to add the length; we save the final 2 bytes of space for the length, for a 65535 bit message length limit:
Message 1 "THIS IS NOT A TEST", length 19 bytes (152 bits):
initial value     Block 1 "THIS I"  Block 2 "S NOT "
0x67452301AB89    0x544849532049    0x53204E4F5420

** state collision here **

Block 3 "A TEST"  Block 4 "!" and padding bit and length
0x412054455354    0x218000000098

Hash Output
0x7F266204EDAF

Message 2 "ENACT A TEST", length 13 bytes (104 bits):
initial value     Block 1 "ENACT "
0x67452301AB89    0x544849532049

** state collision here **

Block 2 "A TEST"  Block 3 "!" and padding bit and length
0x412054455354    0x218000000068

Hash Output
0xE7D693B5011B

Once the length is added to the padding, it prevents this from happening in the output, even though there is a state collision. As above, the padding bit 1 prevents near identical messages with different lengths of trailing 0 bits from being processed the same way in the compression function, which will cause a collision at the block level.
Keccak uses a much larger state and block size, say 1600-bits and 1088-bits (for a 256-bit hash). The chance of an internal state collision is much less than the security provided by the hash size, so a length is not required. Not having a length padding also simplifies implementations, since you do not need to keep track of the data you are processing. The padding bit 1 is still required for the same reason as an MD hash. The final padding bit (in 10*1) is required to prevent identical messages from causing a collision when the sponge rate is different, this would not be required if the rate was fixed.
For most MD hashes, the state and output are the same, with a larger block size, this means the chance of a state collision is most likely higher than the specified security level of the hash, hence the strengthening by adding the length.


Why do memory-hard functions rely on a time-space trade-off?

In order to create such a function you fill up memory with results of some computation; the memory-hard function then reads these values to further the computation later on.

Rather than saving the values, one could theoretically re-calculate them when needed. So the memory is not really a hard requirement. The memory hard functions are however build in such a way that they require much more computation without memorization of the intermediate values. This is the time / memory trade off.


Slide attack: creating an actual attack on the Simon Cipher

You should read David Wagner's original paper.  You can see all of his work here.

He authored the 'Slide Attack', 'Advanced Slide Attacks' and a few more related to the attack.

Wikipedia has a good introduction here

Feistel ciphers like Simon are very vulnerable to Slide Attacks and similar.  Removing the round constants from the key schedule will likley lead to an easy break in the cipher.  Partial attacks on the real cipher seem possible if multiple round keys can be forced to collide in a related key attack.


Why create a subkey in the digital signature algorithm

What's the use of that k?

The following lines of the wiki tell you:

Compute $r := ( g^k \bmod p  )  \bmod    q$

Compute $s := ( k^{−1} ( H(m) + xr  ) ) \bmod    q$

That is, it is used to compute both $r$ and $s$.

However, that's not what your really asking.  You're asking "why did they design DSA that way?"

Well, it's actually a variation on a noninteractive Schnorr proof of knowledge of a discrete log (in particular, of the private key); the modifications are there to reduce the size of the signature.

And, since Schnorr requires a "commitment" (what you call a subkey), well, so does DSA


why DES encryption uses different modes like ECB,OFB?

DES is a block cipher. It consists of a pair of algorithms, one for encryption and one for decryption. Each algorithm takes two inputs: the key, and the block to encrypt or decrypt; the output is the encrypted or decrypted block. For DES, the size of a block is 64 bits. So DES only tells you how to encrypt or decrypt data that consists of exactly 64 bits.

If you have more or less than 64 bits of data, you need to specify how the data is split into 64-bit blocks, what processing to apply to each block, and how to combine the output blocks together. By definition, this is called a mode of operation. Usually the splitting and combining is trivial, but the part about processing each block can be more or less complex.

Even when you happen to have exactly one block of data, modes can achieve things that DES alone doesn't. In particular, DES is deterministic: encrypting the same plaintext with the same key always leads to the same ciphertext. All good modes include a unique tag as part of the encrypted data (called an initialization vector in most modes), so that no two runs of the encryption algorithm ever produce the same ciphertext, which avoids leaking the fact that two messages are equal. Modes can also build algorithms that do things other than encryption, such as a message authentication code, or authenticated encryption which combines encryption and MAC together in a single algorithm.


Elliptic Curve Cryptography, decrypting returns false result

I would imagine your calculator doesn't know how to handle the point at infinity because it relies fully on affine points. You can compute that

\begin{align*}
    C_2 &= P + k*e_2 \\
        &= (45,48) + 47*53*(3,25) \\
        &= 5*(3,25) + 47*53*(3,25) & (\text{since }(45,48) = 5*(3,25)) \\
        &= 2496*(3,25) \\
        &= \infty & (\text{since }2496\equiv0\bmod 64)
\end{align*}
This computation seems to go wrong somehow, possibly because it can't represent $\infty$ internally.


They're actually sampling $5n$ elements from $\Psi_{16}$. Perhaps Protocol 2 on page 5 shows this most clearly, where $\textbf{s}, \textbf{e} \stackrel{\$}{\leftarrow} \Psi_{16}^n$ and $\textbf{s}', \textbf{e}', \textbf{e}'' \stackrel{\$}{\leftarrow} \Psi_{16}^n$ are sampled (on line 3 on Alice' side, and line 1 on Bob's).

This probably also answers part of your follow-up question, but for completeness: the values $\textbf{s}$ and $\textbf{s}'$ are sampled independently by Alice and Bob, and are thus not at all related. The final shared secret is neither $\textbf{s}$ nor $\textbf{s}'$, but the reconciled $v$.


Testing Kasiski Test and Mutual Index of Coincidence on Vigenere Encryption on Vigenere Encryption?

Vigenere algotrith suppose that Alice would send a message (M) to Bob.
The message is written in some language and has a length ML (symbols that compose the message have a known frequency and belong to an alphabet A with a given size AL).
To encript a message Alice use a key (K) that in Vigenere alogrithm is a seqeuence of symbols called Worm shortest (by definition) than the message, both Alice and Bob knwon K that does not need to be exchanged.
The encripotion is applied by adding the value of each message symbol by the value of the corresponding worm sybol (worm could be completly random) modulo AL.

Eg :

M = "hello world today is fine"
ML = 25
K = "abc"
KL = 3

M as values :
68 65 6C 6C 6F 20 77 6F 72 6C 64 20 74 6F 64 61 79 20 69 73 20 66 69 6E 65
K as values :
61 62 63

As you can see because the worm is short than message (by definition) we need to repeat it, again and again to reach ML

M as values :
68 65 6C 6C 6F 20 77 6F 72 6C 64 20 74 6F 64 61 79 20 69 73 20 66 69 6E 65
K as values (repeated) :
61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61

What we obtain indeed is a sequence of three Caesar encription (in the general case the number of Caesar encription is KL = Key Length):

This is the first Caesar

M as values :
68 65 6C 6C 6F 20 77 6F 72 6C 64 20 74 6F 64 61 79 20 69 73 20 66 69 6E 65
|        |        |        |        |        |        |        |        |
K as values (repeated) :
61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61

Caesar SubMessage : 68 6C 77 6C 74 61 69 66 65
Caesar Key : 61

This is the second Caesar

M as values :
68 65 6C 6C 6F 20 77 6F 72 6C 64 20 74 6F 64 61 79 20 69 73 20 66 69 6E 65
   |        |        |        |        |        |        |        |
K as values (repeated) :
61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61

Caesar SubMessage : 65 6F 6F 64 6F 79 73 69
Caesar Key : 62

This is the third Caesar

M as values :
68 65 6C 6C 6F 20 77 6F 72 6C 64 20 74 6F 64 61 79 20 69 73 20 66 69 6E 65
      |        |        |        |        |        |        |        |
K as values (repeated) :
61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61

Caesar SubMessage : 6C 20 72 20 64 20 20 20 6E
Caesar Key : 63

Symbol frequencies on the main message remain the same if we "regulary split" it on the submessage, so classical attack on Caesar (the ones based on frequency) is still applicable on the three Caesar Submessage.

As you can image if you double the Vigenere encription the complexity of the attack does not change ( EG : add K1 = "def").

M as values :
68 65 6C 6C 6F 20 77 6F 72 6C 64 20 74 6F 64 61 79 20 69 73 20 66 69 6E 65
K as values :
61 62 63

K1 as values :
64 65 66

This because Vigenere encription is composed by Caesar encription and Caesar encription is an associative operation so :

( 68 + 61 mod AL ) + 64 mod AL = ( 68 + ( 61 + 64 mod AL ) ) mod AL

so a double encription is equivalent to a change of the key in a single encription, but the key nature (random or not) does not fix any security problem of that alogrithm.

In the example above (about the double encription) the resulting key, obtained by combining K and K1 is called K2 (i have assumed that AL = 256 and A is the ASCII table) :

K2 = C5 C7 C9

So the double encription is equivalent to a single instance like the below

M as values :
68 65 6C 6C 6F 20 77 6F 72 6C 64 20 74 6F 64 61 79 20 69 73 20 66 69 6E 65
K2 as values (repeated) :
C5 C7 C9 C5 C7 C9 C5 C7 C9 C5 C7 C9 C5 C7 C9 C5 C7 C9 C5 C7 C9 C5 C7 C9 C5

That istance certainly is not stringer than the first ones.


What if the CSR is intercepted in transit while sending it to CA?

Normally CSR does not need to be secret. CSR is signed by the applicants private key. If an attacker intercepts a CSR, changes email address and sends CSR on CA, CA will reject it, because the signature will not match the content of the CSR. If the attacker signs the changed CSR with attackers private key, the signature will still be invalid, because it cannot be verifyed by the public key contained in the CSR.
Here is a good short explanation of the verification process: How does RSA signature verification work?.
To sign the CSR with the changed email, a private key of the applicant is needed. If the applicant keeps the private key properly, then the attacker cannot get it and cannot create a valid CSR with another email.
TLDR
CA will consider the changed CSR as invalid because the attacker cannot create a valid signature.


Generally speaking, the public key and its corresponding private key are linked together through their internal mathematical structure; such keys are not "just" arbitrary sequences of random bits. The encryption and decryption algorithms exploit that structure.

One possible design for a public key encryption system is that of a trapdoor permutation. A trapdoor permutation is a mathematical function which is a permutation of some space, such that computing the function in one way is easy, but the reverse is hard, unless you know some information on how the trapdoor permutation was built. Encryption is applying the function on a message, decryption is about using the trapdoor to reverse the function.

For RSA, a well-known asymmetric encryption algorithm, consider a rather big (say 300 digits or more) integer $n$. $n$ is composite: it is the product of two big prime integers $p$ and $q$. There are more such composite integers than there are particles in the observable universe, so there is no problem in generating such an integer. $n$ is called the modulus because we will compute things "modulo $n$". It turns out that:

it is easy to compute cubes modulo $n$ (given $m$, compute $m^3 \mod n$);
if $p$ and $q$ were chosen appropriately (I skip the details), raising to the cube is a permutation modulo $n$ (no two integers modulo $n$ will have the same cube, so any integer between $0$ and $n-1$ has a unique cube root modulo $n$);
computing the cube root of an integer modulo $n$ is extremely hard
... unless you know $p$ and $q$, in which case it becomes computationally easy;
recovering $p$ and $q$ from $n$ (that's factorization) is extremely hard.

So the public key is $n$, the trapdoor permutation is raising to the power 3, and the reverse is computing a cube root; knowledge of $p$ and $q$ is the private key. The private key can remain "private" even if the public key is public, because recomputing the private key from the public key is a hard problem.

There is a bit more to RSA than the description above (in particular, RSA does not necessarily uses the power 3), but the gist of the idea is there: a function which is one-way for everybody, except for the one who selected the function in the first place, with a hidden internal structure which he can use to reverse the function.

SSL (now known as TLS) is a more complex beast which usually uses some asymmetric encryption during the initial stages of the connection, so that client and server end up having a "shared secret" (a commonly known sequence of bits); the shared secret is then used to apply conventional encryption and decryption to the rest of the data ("conventional" meaning: same key to encrypt and decrypt).


Why did Histiaeus tattoo his slave's head?

Exact motives will remain unknown, since we only have Herodotus's word for the whole story, and he doesn't say. However, we can imagine a plausible reason: the whole ordeal provides some level of authentication.

Indeed, Histiaeus's slave could hardly have made himself the tattoo, and certainly not without Histiaeus noticing. Since hair growing is slow (and cannot be accelerated, at least not in Ancient Greek times, where hair grafting was not known), the presence of the message as a tattoo shows at least a purposeful dedication in time to the process. In modern terminology, it is a "proof of work". A contrario, a purely verbal message could be made up on the spot by the slave himself. Aristagoras could believe such an oral transmission to be merely the invention of a disgruntled slave.

Alternatively, this could be Herodotus having absorbed too much Samos wine. He tries to be careful, but since most of what he writes is hearsay, he at times swallows wonderfully extravagant stories, such as some about giant ants that can devour adult camels (one hypothesis is that he confused "giant ants" with marmots, but these peaceful rodents don't attack camels either!).


If you hashed a hash an infinite number of times would you end up with a unique hash?

If you repeatedly apply a generic function on its result, in a finite domain, you tend to obtain a "rho" structure: at some point, you enter a cycle whose length is (roughly) $\sqrt{N}$, where $N$ is the size of the output space for your function. In the case of MD5, $N = 2^{128}$ (MD5 outputs 128-bit values), so the cycle will have length about $2^{64}$ values. You can hash "infinitely", you will never end up on a unique value. See this answer for some details and a picture.

Well, strictly speaking, you might end on a unique value, which would be called a fixed point, but we don't know if such fixed points actually exist with MD5. For a randomly selected function, there is a probability of about $63\%$ that a fixed point exists at all. But existence of a fixed point does not mean that you will reach it. In fact it is expected that for most cases you will end in the "big inner cycle"; if there is a fixed point at all, you will ultimately hit it only with probability $1/\sqrt{N}$ or so, i.e. pretty rarely.

In all generality, when starting from some input and hashing repeatedly, you always end up walking a cycle, and that never ends. A fixed point is a special case of a cycle with only one element. For a given function, one expects that
there is a "big" cycle that you ultimately reach for most inputs, and a collection of much smaller cycles that you almost never reach.


What happens if CBC-mode uses the same IV for all processes?

If the modification is done, the encryption looks like this:

$$C_i=E_K(\text{IV}\oplus P_i)$$

and assuming the "IV" is public, this is essentially ECB mode with a security-irrelevant pre-processing by XOR'ing a constant into the message.

Assuming the "IV" is non-public, this is essentially an XOR cipher encrypted with ECB mode and in particular this is still vulnerable to the standard ECB attack that you can detect repeated blocks, which means that the mode / construction can be broken under a standard (formal) ciphertext-only attack where the attacker-chosen messages are 2 blocks.


Non Repudiation - Message Authentications methods

When Alice and Bob are using a message authentication code (MAC) scheme, both of them have the shared MAC key, and both of them can generate valid MAC tags. Between Alice and Bob, they can be sure who is the sender. For example, if Bob receives a message with a valid MAC, and the message was not sent by himself, then the message must come from Alice. Hence "Message authentication methods verify that the message is from the right sender". Here essentially, MAC enables private verifiability among the two parties.

However, non-repudiation is about convincing a third party (or requires public verifiability). A third party, without the MAC key, when seeing a message with a MAC cannot verify the MAC is valid. Hence it has no way to decide who was the sender. Even if Alice and Bob give up the key, the third party can only say the sender is either Alice or Bob, since both of them can generate the tag. Thus Alice and Bob can always deny she/he was the message sender (and say the sender was the other party).


Why is PerfectForwardSecrecy considered OK, when it has same defects as salt-less password hashing?

Salt-less password hashing is only a problem since the amount of passwords actually used in practice is comparably small and also not evenly distributed. Thus it is both in terms of time and memory possible to generate a table with pre-computed hashes and then check the salt-less hashes against this table to reverse the hash. The protection against this are thus salts (increase of time and memory needed for pre-computation) and slow hashes (increase of time).

But, this pre-computing will no longer be feasible if the choice of passwords is not biased against "few" often chosen passwords but if instead there would be a huge amount of possible passwords and none of these would be more likely than the other. It would simply not be practically possible in terms of time and memory to pre-compute and store the hash for all possible passwords. And that's exact the case you have with PFS - it is simply impossible to pre-compute even a relevant small part of all the possible values.


Security of Even-Mansour scheme with keyed shuffle?

To understand the Even-Mansour security result, it helps to first understand the random oracle model.  Roughly speaking, the random oracle model says that a hash function should behave like a randomly chosen function, and have no detectable patterns or structural properties that a random function wouldn't have.  Of course, the hash function is publicly known, so anyone can compute it, but apart from that, it shouldn't have any other structural properties.

Even-Mansour uses something similar, but now for permutations.  The requirement in the Even-Mansour proof is that $F$ is a random permutation oracle: it has to behave just like a randomly chosen permutation (random bijective function), and have no detectable structural properties that a random permutation wouldn't have.  Of course, $F$ can be publicly known (so given $x$ anyone can compute $F(x)$ and $F^{-1}(x)$), but apart from that, it shouldn't have any other structural properties.

This is like an unkeyed version of the ideal cipher model.  See What is the ideal cipher model?.

Once you understand the ideal cipher model, you can then evaluate whether some specific construction would qualify.  It basically comes down to whether your other construction qualifies as a reasonable instantiation of a random permutation oracle (i.e., as a reasonable instantiation of an unkeyed version of an ideal cipher).

Fisher-Yates is not suitable except for constructing block cipher, as the running time of Fisher-Yates is super exponential: if you want a random permutation on $b$ bits, the running time of Fisher-Yates is at least $(2^b)!$, which grows asymptotically as something like $2^{(b-1.44) \cdot 2^b}$... i.e., huge.


Length Extension attacks in SHA1 and MD5?

You forget one little step of how Merkle–Damgård construction works; the padding, here SHA-1 padding:

  append the bit $\texttt{1}$ to the message e.g. by adding $\texttt{0x80}$ if message length is a multiple of 8 bits.

  append $0 \leq k < 512$ bits $\texttt{0}$, such that the resulting message length in bits is congruent to $$−64 \equiv 448 \pmod{512}$$

  append ml, the original message length, as a 64-bit big-endian integer.
     Thus, the total length is a multiple of 512 bits.

Therefore the real input is

$$\text{SHA-1}(\text{secret_key}\mathbin\|\text{known_data}\mathbin\|pad1)$$

because the attackers only get the hashed value. And, you need

$$\text{SHA-1}(\text{secret_key}\mathbin\|\text{known_data}\mathbin\| \text{pad1}\mathbin\|
 \text{appended_data} \mathbin\| \text{pad2})$$

for extension attack. This works similarly for any hash function that uses the same padding mechanism.

The attackers can access the hash of a padded message and they can extend it in this way. This is due to the artifact of Merkle–Damgård construction. SHA-3 is safe from this attack by design and later the new SHA2 modes SHA512/256 and SHA512/384 and other truncated versions of SHA2 also have resistance to length extension attack.

SHA-1 or MD5 is not considered secure. Use modern Hash functions like SHA3 or Blake2 with good output sizes to prevent the generic collision attacks like at least 256-bit.


Given a Message and Decryption Key, is it possible to find the Cipher in RSA?

TL;DR: don't go here, it's a common mistake by starting cryptographers.

This is a reinvention of a signature scheme, as fgrieu mentions. If you want to integrate (part of) the message into the signature then you are talking about signature schemes giving (partial) message recovery.

The decryption key is the private key. It contains the modulus and private exponent, plus possibly all the CRT parameters and the public exponent. Now the public exponent doesn't need to be easy to guess, but it is if all the parameters or the exponent itself is given. Besides that, usually the public key exponent is set to a small prime number, which is easy to guess. Usually it is just 65537, the fourth prime of Fermat (F4). In other words, anybody who has the private key can generate the public key as well.

You can of course flip the public and private key and give out the public key instead. Even then there are problems with the scheme, take a look at my self answered question here - and note that I wrote this Q/A because many StackOverflow errors before.

And of course, just distributing the keys is not enough; the key of Alice must be trusted to be the key from Alice. Otherwise anybody can distribute keys instead of Alice. It may be tricky to find a scheme that protects public keys instead of private keys, if that is used.


Well, you are as surprised as I believe most of us are...

AES-CTR and AES-CBC are "obsolete", whilst AES-CTR is used by AES-GCM. Okay, so maybe he recommends authenticated modes (which don't require making your own authentication). But those aren't obsolete, they are just harder to code properly...
DH and all variants of RSA are "obsolete". Only ECDSA and ECDH... There are many  asymmetric algorithms that showed up which are meant to replace RSA, but RSA isn't obsolete and will probably remain huge until quantum computers.
HKDF-CTR is "obsolete". Should we use PBKDF2 which is designed for passwords and not keys?
RSASSA-PKCS1-v1_5 is kind of a problematic choice. Many people still use it, but I believe moving to OAEP and PSS is better in long run. Of course this doesn't mean "obsolete", at most "unrecommended".

All in all, I think "obsolete" isn't correct word. More like: Algorithms that newbies shouldn't use because they aren't obvious what they do. Of course then we should throw in AES-KW and ECDH, because those both are rather not obvious. I think person who created this site wanted to give "best recommendations", but deprecating HKDF-CTR is questionable at least.

TL;DR: This isn't by any means correct, except for SHA-1.


This would appear to be impossible.

You require that $|x_1 - x_2| < \epsilon$ implies that $|f(f(x_a, k_a), k_b) - f(f(x_b, k_b), k_a)|<\delta$ ; this implies that $f(f(x_a, k_a), k_b)$ is continuous over $x_a$.

Now Charlie knows $k_a, k_b$ and can compute the target value $f(f(x_a, k_a), k_b)$; a simple bisection search over the function $f(f(x, k_a), k_b)$ would allow him to recover $x_a$ (or at least, a good approximation).


For most classical encryption schemes from the literature, what you want will in fact be trivial, as it is common that every possible ciphertext is a valid encryption of at least some message $m$ with respect to the public key. This is not implied by the standard security properties (and does not hold, for example, with respect to IND-CCA secure encryption schemes), but it holds for many IND-CPA secure encryption schemes.

Take for example ElGamal over a group $\mathbb{G}$, with public key $(g,h)$ ans secret key $s$ such that $h = g^s$. Then any pair $(c_1,c_2)$ correspond to a valid encryption of some message $m$: set $r$ to be the value such that $c_1 = g^r$ (it exists since $g$ is a generator of $\mathbb{G}$), and set $m$ to be $c_2/h^r$. Then, you obviously have $(c_1,c_2) = (g^r, h^rm)$.

The bottom-line is: if you want such a zero-knowledge proof, you should specify which encryption scheme you want it for - for some classical schemes, no proof is needed.


Prove that pseudorandom generator is a one way function

$$l = \log n: \Pr[B(Un+\log n)]≥2^n/2^{n+\log n} \cdot 1/p(n)$$
Since even if the input of $B$ is from the image of $G$, the probability to invert it is $1/p(n)$.
So you need to correct this case and it will help you with $l = 1$.


Organizational Internal Man In The Middle Scenario

Yes, your understanding is correct.

This is a TLS (or any other secure transport protocol) capable proxy. What it does is that it generates site certificates on the fly. You connect to a site through the proxy with your client and it performs a man-in-the-middle, as the TLS connection is setup before anything else.

First it will connect with the remote site, and create a connection with it using the normal server certificate. Hopefully it completely verifies and validates that computer's certificate. So that's taken care of the connection with the remote server.

Now to spoof your connection the proxy must have a certificate for a specific hostname (as Common Name in the certificate). It probably first looks up the certificate in the cache and uses that together with the private key. If it cannot find the certificate it generates a key pair and signs a temporary certificate for it. Then it sets up the connection with your client.

Once it has both TLS sessions running it can act as a normal proxy. Now it can (deep) inspect any data send through the connection in either direction.

Alternatively, it can send a redirect to the client so that it connects to a different hostname. That way it can use a single, long term server / device certificate. Of course your client will have to accept this redirection for the scheme to work.

Of course it is not that easy, as a random certificate will be rejected by your client - there is no certificate chain to a trusted certificate. Basically this can be solved by injecting a trusted CA certificate in your trust store. This can be a Windows trust store, or the trust store of the client application that you're using (e.g. a firefox browser). Usually the certificate is simply pushed using the Windows group policy together with some script for the most common browsers.

The proxy will now act as its own Certificate Authority, signing any certificate it generates using the private key with it's own CA certificate. Once the certificate chain is trusted your client will lite up "green" as it cannot see the difference with any other chain.

Alternatively, the proxy could use a broken (or otherwise controlled) CA, like Iran did with the DigiNotar CA, when it requested certificates for Google.

Of course even deep packet inspection will not be capable of detecting all possible covert channels, so I'll leave it up to you to hack out of the system (with the possible repercussions that come with it).


Though the general idea of a three pass exchange has merit, when implemented using exponentiation over a finite field it doesn't have much advantages over the far more common Diffi Hellman.

Both get their security from the hardness of descrete logarithm. (Though we don't know to reduce Dlog to either).

Obviously a three pass protocol requires more message passing and requires them sequentially. Also in it's simple form only one party affects the final key which could be seen as a disadvantage over a symmetric protocol.

So DH is symmetrical, has fewer messages which don't rely on each other and is more widely adapted and better studied.

If you are not looking at is a key exchange but as a means to send a message the three pass can be apppied to the message directly or the message could be encrypted and sent along with the first message. While with DH you can only send content after the exchange is complete. So the number of messages required for the initiator to send content ia the same 3 messages.

With DH a third party can hold half keys which can be given someone to establish a secure connection. This allows for asynchronous protocols to work well with DH. Won't work with a three pass protocol.


Attack against $\operatorname{DESA}_{k,k_1} (x) \underset{\text{def}}= \operatorname{DES}_k(x)⊕k_1$

Normal DES
Let's say you have a normal DES plaintext-ciphertext pair encrypted with 56 bits key $k$ where $C_1=DES_k(P_1)$.
In the worst case, one needs to try the $2^{56}$ possible keys to find the encryption key. And later on, one can decrypt all Ciphertext encrypted with the key $k$
DESA
Let's say one has 2 pairs of plaintext-ciphertext pairs ecnrypted with
$k$ (the usual 56 bits key size) and $k_1$ (64 bits since the block size)  where $C_2=DESA_{k,k_1}(P_2)$ and $C_3=DESA_{k,k_1}(P_3)$
So one can x-or given two ciphertext and:
$C_2\oplus C_3 = DESA_{k,k_1}(P_2)\oplus DESA_{k,k_1}(P_3)= DES_k(P_2)\oplus k_1\oplus DES_k(P_3)\oplus k_1=DES_k(P_2)\oplus DES_k(P_3)$
So, $k_1$ is gone. In the worst case, one tries $2^{56}$ times and get $k$ with two plaintext-ciphertext pair.
Then, for any ciphertext with the help of previous equation one can calculate the $k_1$
$$C_1 = DES_k(P_1)\oplus k_1$$
knowing the key $k$ one can calculate $k_1$.
So in total $2^{57}+1$ DES encryption is called, instead of $2^{56+64}$ key size.


Plausibly deniable authentication for agents on multiple teams

It would be possible to do this if the authentication method was designed to allow for redundancy. The simplest example would be if team members authenticated to each other with a password, but they were allowed to send redundant characters along with the password. (I'm assuming here that all teams use the same authentication method!)

So let's say the blue team password is "BERRY" and the green team password is "LEAF". Now, the string "ASDBERRYFOO" would successfully authenticate a blue team member. However, "FOOBERRYLEAF" would successfully authenticate a member to both teams! The teams don't know each others' passwords, so the latter does not look any more suspicious to anyone than the former. Eve doesn't know the passwords of red or blue teams either, so she cannot know whether that string actually includes a password to one or more teams.

Of course, this method is highly vulnerable to replay attacks. Eve can very well just go ahead and send "FOOBERRYLEAF" to anyone she might encounter, and that way she would find out that it authenticates to both blue and green teams (even if she still doesn't actually know the passwords -- they might as well be "OOBE" and "RYLEA"!).

One could try to improve the scheme by only accepting a certain authentication string once -- so if "FOOBERRYLEAF" has been used, it shouldn't work again. Alice can still create an unlimited amount of similar strings as she knows the passwords.

A better method would be to use one-time passwords so that even the "BERRY" part does not repeat.

The redundancy part is still my main issue though: why would anyone actually use a scheme where the same message could be interpreted in two different ways? Obviously my "FOOBERRYLEAF" example is too naive. I think in reality you wouldn't just concatenate strings, but you'd find some clever hash collision or something like that to achieve the same result. But I'll leave that part for others to ponder...


Lagrange-Gauss algorithm can also be seen as LLL in dimension 2.  Here is an implementation using GP/Pari:

\\ Given A modulo N, it returns a fraction u/v s.t. A = u/v (mod N)
Gauss(A,N) = {
  local(L,L3);

  L = [1,0;lift(A),N];
  L3 = L*qflll(L);

  return(L3[2,1]/L3[1,1]);
}

EDIT: Consider the lattice defined by the two column vectors $\begin{pmatrix}1\\A\end{pmatrix}$ and $\begin{pmatrix}0\\N\end{pmatrix}$.  The vectors in the lattice are:
$$\alpha  \begin{pmatrix}1\\A\end{pmatrix} + \beta \begin{pmatrix}0\\N\end{pmatrix} = \begin{pmatrix}\alpha\\ \alpha A + \beta N\end{pmatrix}$$
As we are in dimension 2, LLL will return the shortest (non-zero) vector in the lattice.

Let's call $$\vec{v} := \begin{pmatrix}v_1\\v_2\end{pmatrix} = \begin{pmatrix}\alpha^*\\ \alpha^* A + \beta^* N\end{pmatrix} \in \mathbb{Z}^2$$
the vector returned by LLL: $v_1$ and $v_2$ are small.  Clearly, we have
$$v_2 = \alpha^* A + \beta^* N \equiv \alpha^* A \equiv v_1 A \pmod N$$
and thus
$$A \equiv \frac{v_2}{v_1} \pmod N$$
with $v_1$ and $v_2$ small.


Well, the idea behind the CRT optimization is that if we know the factorization of the modulus $N$ (which we may if we have the private key), then we can split up the message $M$ into two halves (one modulo $p$, and one modulo $q$), compute each modulo separately, and then recombine them.  That is, we compute:

$m_1 = (M^d \bmod N) \bmod p = ((M \bmod p)^{d \bmod p-1}) \bmod p$

$m_2 = (M^d \bmod N) \bmod q = ((M \bmod q)^{d \bmod q-1}) \bmod q$

(Note that the exponents are reduced modulo $p-1$ and $q-1$; we can do this because $p$ and $q$ are prime (and Fermat's little theorem); this is the source of a good portion of the speedup).

Then, we recombine them; that is, we find a number $m$ such that:

$m \equiv (M^d \bmod N) \mod p$

$m \equiv (M^d \bmod N) \mod q$

Because of the Chinese Remainder Theorem (and because $p$ and $q$ are relatively prime), we can immediately deduce that:

$m \equiv (M^d \bmod N) \mod pq$

which is exactly what we were trying to compute.

Now, the questions in your comments appear to be asking about the details of this recombination step.

Now, it is actually fairly easy to see the correctness of the algorithm.  To make the last step work, we need to show that we have come up with a value $m$ such that:

$0 \le m < pq$

$m \equiv m_1 \mod p$

$m \equiv m_2 \mod q$

As for the the first criteria $0 \le m < pq$, well, that's straight-forward; we know that $0 \le m_2 \le q-1$, and $0 \le h \le p-1$, and so the smallest that $m$ can be is $0 + (0 * q) = 0$, and the largest it can be is $q - 1 + ((p-1)*q) = pq - 1$

As for the third criteria, that's also straight-forward; $(m_2 + (h * q)) \bmod q = m_2 \bmod q + (h*q) \bmod q = m_2 \bmod q$

The second one is a little tricker: $(m_2 + (h * q)) \bmod p = (m_2 + q * q_{inv} * ( m_1 - m_2) \bmod p) \bmod p = (m_2 + q * q_{inv} * (m_1 - m_2)) \bmod p$

Now, $q_\mathit{inv}$ is defined to be the number that, when multiplied by $q$ modulo $p$, results in 1 (that is, $q * q_\mathit{inv} \equiv 1 \mod p$).  Now, because the above equation is, in fact, computed modulo $p$, we can replace $q * q_\mathit{inv}$ with 1, which gives us:

$m \bmod p = (m_2 + 1 * (m_1 - m_2)) \bmod p = m_1 \bmod p$

QED


Discovering private exponent from public key

When using a Discrete Logarithm based scheme, such as SRP, the rule of thumb is to always use private exponents with a bit length twice the desired security strength. Hence, a 128 bit exponent $a$ will at most give you 64 bits of security. If you want 128 bit security, you need (at least) a 256 bit exponent. This is because the algebraic structure of the groups used for such schemes, make it possible to calculate discrete algorithms using a meet-in-the-middle approach that effectively halves the necessary effort, compared to a naive brute force approach.

In this case, for instance, let $q$ be the order of $g$ in $\mathbb Z_N$. Calculate $y = A(g^{q-x2^n}) \bmod N$ for all $0 \le x \lt 2^{128-n}$ and put the pairs $y,x$ in a table for fast access, indexed by the $y$ component. Next calculate $y' = g^z \bmod N$ for all $0 \le z \lt 2^n$. If you find a $y$ in the table such that $y = y'$, then you know that $z = a - x2^n \bmod q$, and hence that $a = z + x2^n$.

The latter calculations might be carried out in parallel and might be more effectively optimized than the former, so the optimal trade-off might e.g. be to set $n = 80$, meaning you put $2^{48}$ pairs $y,x$ in your table and perform a total of $2^{80}$ parallel calculations $y' = g^z \mod N$. This is feasible using modern hardware.


Is one time pad cipher reuse and random key secure?

If your goal is to ensure only the legitimate sender with knowledge of $s_1$ and $s_2$ can answer the challenge, then this protocol fails to achieve your goal: eavesdropping a single challenge/response pair $(y, z)$ is enough to forge any number of subsequent responses pairs with the same $s_1$ and $s_2$.

Specifically, $z = y \oplus s_1 \oplus s_2$, so to forge the correct response $z' = x' \oplus s_2$ to a subsequent challenge $y' = x' \oplus s_1$ it suffices to recover $s_1 \oplus s_2 = z \oplus y$ and then to compute $$z' = y' \oplus s_1 \oplus s_2 = x' \oplus s_1 \oplus s_1 \oplus s_2 = x' \oplus s_2$$ as expected.

If each $x$ is independently uniformly distributed, then you can't recover $s_1$ or $s_2$ from it (effectively, you have encrypted $s_1$ with the one-time pad $x$ in this scenario!), but seldom is the pad the object you're interested in protecting in the end!

So what are you really trying to accomplish here?


Generalizing the conversion of Diffie-Hellman to El Gamal

The conversion of Diffie-Hellmen into Elgamal is assisted by a few factors that are not inherent to key exchange/agreement protocols in general, but a general conversion may be possible.

The DH $\rightarrow$ Elgamal case. In Diffie-Hellman, Alice generates $a$ and sends a representation of it: $g^a$. Bob generates $b$ and sends $g^b$. Both parties can compute $g^{ab}$. To convert to Elgamal, Alice starts the protocol generating $a$ and posts $g^a$ so anyone can complete Diffie-Hellman with her. If Bob wants to complete the protocol, he generates $b$ and sends $g^b$. To make it encryption, he generates the shared secret $g^{ab}$ and multiplies in his message $mg^{ab}$ and sends that as well.

Why is this CPA-secure? Under DDH-assumption $g^{ab}$ is indistinguishable from a random group element so it works as a sort of one-time pad. Since the sender contributes $b$ to the random mask, each encryption of the same message results in a different ciphertext.

What is needed for a general conversion? (These is just "brainstorming" and not meant to be comprehensive).

It is important to have a DDH-type assumption that shows the shared secret is indistinguishable from random.
The shared secret must be an element of a group so there is a permissible operation that can be used to combine it with the message with closure.
The conversion is also assisted by being from an unauthenticated key exchange. Most other common key exchange protocols are authenticated (or mutually authenticated). This doesn't necessary prevent a conversion, just adds unnecessary weight to the encryption scheme (and if you strip off the authentication, you may find yourself back at basic Diffie-Hellman).
As per @Paulo's comment, Alice's first move must be securely repeatable.
While in DH, this does not occur, there is not problem with Bob using Alice's output from the first move to generate his share. So two-round protocols are fine when only one party is needed in the second round.

It would be interesting if you could provide some examples of other key exchange protocols that are eligible for conversion. I think you'll find the majority are either based on adding properties to Diffie-Helman that assists in making it a better key exchange but doesn't assist you in a conversion, or they don't lend themselves to conversion (too many rounds, they already use public key encryption, etc.)


Verification using recovered public key from ECDSA signature and normal verification: what are the differences?

Recovering the two potential public keys and comparing them to the known public key is related to, but distinct from the normal ECDSA signature verification algorithm, and is somewhat more costly.

The notation I'll use:

$r, s$ are the values from the signature
$h$ is the hash of the message being verified (truncated, if the length of the hash is longer than the group size)
$P$ is the public key
$G$ is the group generator
$|Q|_x$ is the x-coordinate of the point $Q$
$\{R, R'\}$ are the two curve points with x-coordinate $r$

Then, the standard verification algorithm is:

$$r \ \overset{?}{=}\  |(hs^{-1}G + rs^{-1}P)|_x$$

To evaluate this requires two point multiplications and one point addition, which with Shamir's trick, can be done in not much more time than one point multiplication.

In contrast, the 'recover the private key, and compare' logic would be:

$$P \ \overset{?}{=} r^{-1}s\{R, R'\} - r^{-1}hG$$

Where you accept the signature if either $R$ or $R'$ satisfies the equation.

This may require three point multiplications (or two applications of Shamir's trick); rather more than the standard logic; even if you get lucky and pick the correct $R, R'$ initially, you're no better off.  You could rearrange this to make this more efficient (as you have the potential value $P$ in hand); however if you do, you'll find that you'll arrive back at the standard ECDSA verification logic.


Authentication scheme to protect against fake devices

There is no cryptographic solution, that is one secure under the assumption that keys are the only secrets.

The requirement Authenticated and Replay-resistant imply that fake slaves can't interpret commands intended for genuine ones; hence the use of encryption. Since the master is assumed unable to hold any secret, only public key cryptography with a private key in the slave could secure that encryption, or its key establishment. And the slaves are hypothesized not powerful enough for that.

This is not changed even if we relax the requirements to allow:

Random number generation in the slave (which often is possible, especially in a device with a secret; e.g. by enciphering a counter held in EEPROM memory, or careful accumulation of entropy from analog sources, including clock drift and timing of external stimulus).
Public-key cryptography in the slave limited to the public-key side (a PIC18F24Q10 costing less than a dollar can do the public-key side of RSA in a fraction of a second, and that might be needed only once the first time an instance of the master establish connection).

For something with cryptographic security, we need at least one of:

Public-key cryptography with a private key in the slave; that rules out RSA, perhaps not ECC (depends on hardware, power budget..).
Some secret in the master (see final section)

Cryptography can help on one thing: the serial number of each genuine slave can come with a static cryptographic signature written at factory and checked by the master. That won't prevent cloning genuine slaves with their serial number and signature, but will make it impossible to manufacture a larger quantity of clones with distinct serial numbers than one has managed to gather signatures; it might also allow to blacklist clones according to serial number (e.g. in new releases of the master).

On the slave side that requires only persistent storage and transmission of about 64 bytes with EdDSA, for 128-bit security (and slightly more compact signatures exist). The master checks the signature against a public key that it embeds (we must assume integrity of the master). The private key is used only for production of genuine slave devices.

White-box cryptography (our tag white-box) could allow a secret in the master. Even though it typically fails under determined attack, that's the closest thing to a satisfactory solution. Sketch:

slave is asked and gives its serial number;
master uses white-box crypto to encipher that serial number using a master key implemented by the white box, and that gives the slave's diversified secret that was written in the slave at fabrication time;
master and slave now have a shared secret and use (authenticated) symmetric encryption like AES-GCM (though if the genuine slave is to be protected against replay, it neeeds a RNG or a persitent storage).

Refinements:

white-box crypto is used in the master beyond computation of the slave's diversified secret;
use of a session key for the authenticated symmetric encryption;
the slave contains several secrets, and selects which it uses according to a key version given by the master (that allows to recover from extraction of the master key from the white box; slave clones made using that will stop to work with new releases of the master, which can use improved white-box crypto);
use of a static cryptographic signature (see second section), best transmitted only encrypted by the slaves to make their collection slightly harder.


Is there a cryptography algorithm that will remain safe if P=NP?

Whether P = NP is a question about the asymptotic growth of computational costs of algorithms as functions of input sizes.  It may provide hints about concrete computational cost estimates of algorithms for specific input sizes, but doesn't provide answers.

In the eyes of the asymptotic setting, an $O(n^{10000})$ cost is ‘smaller’ than an $O(1.0001^n)$ cost because for sufficiently large values of $n$, past some boundary $n_0$, all values of $1.0001^n$ exceed the corresponding values of $n^{10000}$.

Does that mean an instance of a cryptosystem that costs $128\;\text J$ energy to compute and costs $128^{10000}\;\text J \approx 10^{20000}\;\text J$ to break is less secure than a cryptosystem that costs $128\;\text J$ to compute and costs $1.0001^{128}\;\text J \approx 1.01\;\text J$ to break?  Certainly not!

For example, finding $k \in \{0,1\}^{128}$ given $\operatorname{AES}_k(0)$ takes $O(1)$ time because the input size $n$ is a constant, but that fact implies nothing about its feasibility in practice.  The asymptotic growth of the NFS and ECM costs guide us toward parameter growth curves for, e.g., RSA, but they require concrete analysis to attain confidence in concrete choice of parameters.

For a particularly goofy example of this, see

  Daniel J. Bernstein, Nadia Heninger, Paul Lou, and Luke Valenta, ‘Post-quantum RSA’, PQCrypto 2017, Springer LNCS 10346, 2017, pp. 311–329,

which shows how to take advantage of a merely quadratic difference between a user's asymptotic costs and an attacker's asymptotic costs to make a cryptosystem, with a recommendation for specific input sizes guided by concrete use and attack cost estimates, that is just barely usable by rich users but likely out of reach of attackers even if they had access to a large quantum computer.

So would it matter if there turned out to be an asymptotically polynomial-time algorithm to solve every NP-complete problem in $O(f(n)^{10000})$ time when testing a solution takes $O(f(n))$ time for polynomial $f$?  No, not really.

Could it matter, if there were a really amazing trick to use a low-degree polynomial that is, in concrete terms, cheap to compute?  Maybe, but at this point that seems implausible—and cryptography might survive nevertheless by high-degree polynomial asymptotic gaps and exorbitant concrete gaps between user and attacker costs even if they're not exponential.


Is this hypothetical key-exchange secure?

This is exactly where automatic protocol analysis tools can help you. For example, using the Scyther tool, the protocol description using symmetric encryption is:

/*
 * Protocol description for Scyther
 *
 * Note we use 'K' to model 'k' since Scyther assumes 'k(.,.)' refers
 * to pre-shared keys between two agents.
 */

// The protocol description with E^2 instantiated as symmetric
// encryption

hashfunction H;

macro msg1 = { R }K ;
macro msg2 = { S }k(A,B) ;
macro msg3 = { K }k(A,B) ;
macro sessionkey = H(R,S);

protocol testSymmetric(A,B)
{
    role A
    {
        fresh R: Nonce;
        fresh K: Nonce;
        var S: Nonce;

        send_1(A,B, msg1 );
        recv_2(B,A, msg2 );
        claim(A,Running,B,R,S);
        send_3(A,B, msg3 );

        claim(A,Secret,sessionkey);
        claim(A,Alive);
        claim(A,Weakagree);
        claim(A,Commit,B,R,S);
        claim(A,Niagree);
    }

    role B
    {
        var R: Nonce;
        var K: Nonce;
        fresh S: Nonce;

        recv_1(A,B, msg1 );
        claim(B,Running,A,R,S);
        send_2(B,A, msg2 );
        recv_3(A,B, msg3 );

        claim(B,Secret,sessionkey);
        claim(B,Alive);
        claim(B,Weakagree);
        claim(B,Commit,A,R,S);
        claim(B,Niagree);
    }
}

If you run this through the Scyther tool, you will find the key is secret, but agreement fails: an attacker can, for example, replace the random value in the first message by anything, causing B never to compute the key, but A still finishes and might think B now agrees on the values.
Thus, the protocol does not give you any decent authentication, but the partner is supposedly alive. This is what Scyther shows you:

If you modify the message macros for the asymmetric version, i.e.,

macro msg1 = { R }K ;
macro msg2 = { S }pk(A) ;
macro msg3 = { K }pk(B) ;

then the situation is much worse. Although the key is still secret, even the most basic authentication notion fails: along the lines of the previous attack, the attacker can complete a run with B without A ever being present.
A slightly more interesting attack is one on the A role (where the intended partner Bob is never alive):

In this case, the attacker just reroutes the messages and A thinks B is alive but completed the protocol with Charlie.

If you use the compromising adversaries version of Scyther you can also analyse KCI, UKS, and (w)PFS attacks, which will probably yield interesting results.


Can one trade off the number of iterations for key length with the PBKDF2?

When using the PBKDF2, is one taking on significant risk if one chooses to lower the number of iterations and choose to have very long keys?

Yes. PBKDF2's method of generating keys longer than the length of PRF output is... a really bad idea. I'll use the same notation that the Wikipedia article on PBKDF2 currently uses to explain why.

The derived key is defined to be $$DK = T_1 \| T_2 \| ... \| T_{dklen/hlen}$$ where $\|$ means concatenation.

The way each $T$ is derived is very important to this question.

Each one of these $T$ are calculated by iterative hashing. $U_1, U_2, U_3, ...$ each need to be computed sequentially for each block of output $T$. $U_2$ needs the result of $U_1$. $U_3$ needs the result of $U_2$. And so on. But each $T$ block does not have any dependency on the sequential hash computed by other blocks.

$T_2$ can be computed without calculating $T_1$. Each block is solely a function of the password, salt, cost parameter, and the output block number (subscript $i$ of $T_i$). Denoted in the article as $$T_i = F(Password, Salt, c, i)$$

If you use PBKDF2 in applications like password authentication or for deriving a stream cipher's key-stream then this is  a problem. The password storage example is easier to demonstrate as a problem.

Each block of output can be computed independently of the other. In that sense using PBKDF2 with $dklen = hlen * k$ is basically the same as publishing $k$ hashes for a single password. To test if a candidate password is correct, a password cracker does not need to compute all $k$ blocks of $T$. It suffices to compute only one of them.

If any one block doesn't match the hash you are trying to crack then you know the password is wrong. A hash based PRF with output length $m$ will only produce false positives with a probability of $2^{-m}$, low enough that we don't need to consider it in estimating the password cracker's cost-per-password-test.

As the legitimate party trying to hash a password by telling PBKDF2 to output $k$ times the PRF output length you are forcing yourself to do $c * k$ work. The password cracker on the other hand only needs to test one block and thus only needs to use $c$ work per guess.

The same logic applies to a PBKDF2 style stream cipher. To encrypt every block of plaintext you have to do $c$ work per block. Someone that wants to brute-force decrypt a single block of ciphertext, on the other hand, only needs to do work proportional to $c$ once per guess. You make the eavesdropper's job $k$ times easier than yours if you need to encrypt $k$ blocks. Not only that, once someone correctly decrypts one block they will know what password was used to compute every other block.

The bad guy never needs to do more than $c$ work to recover the password used to derive EVERY $T$ block. If you decide you want $k$ blocks of output and you compensate by decreasing $c$ by a factor of $k$ you are just making the hacker's job easier. This is a huge flaw in PBKDF2's design.

If you really needed to use PBKDF2 for key derivation (as opposed to Argon2 or scrypt), or something like it, then what you should instead do is use the CPU-time you've budgeted to password hashing to deriving one key with a length no greater than $hlen$. Call this the master key. Take all the resources in your budget and put them into computing just one block of output that's as strong as you can afford to make it. Your passwords will be $k$ times more difficult to brute force this way.

If you need more key-bits than $hlen$ then use your master key to derive child keys. You derive the master key from a password using a password-based KDF. Then you derive each child key using a key-based KDF.

A password-based KDF is designed to be expensive to compensate for passwords being weaker than keys. A key-based KDF lets you derive new keys from a single strong secret key very efficiently. (Or just use one key with an authenticated encryption algorithm. Which is what one normally would do.)

Always be wary of password hashing scenarios where you're incurring unnecessary (including redundant) expense for yourself. If you were planning to spend that much time hashing you should have spent it with a single stronger hash.

And speaking of stronger hashes you should be using Argon2 for now, both for password-database user authentication and for key derivation. Argon2, along with scrypt and "balloon hashing", is what's called a "memory-hard" algorithm. It is designed to make heavy use of RAM, in addition to CPU time (which is all PBKDF2 and bcrypt do for you). Memory-hard functions are thought to be more resistant to CPU-based, GPU-based, and ASIC-based password cracking.

Edit: Clarification in response to a comment

Suppose the absolute maximum amount of compute time (work) you can dedicate to password-stretching is some number denoted $W$. Consider $C_D$, the cost a defender pays to generate their entire derived key (per password entry), and $C_A$ the cost an attacker pays to test a candidate password.

We'll ignore the PRF parameter because the question is only about trading off number of iterations (c in the wiki article) and the key length (dklen in the article). Instead of worrying about dklen, hlen, and the number of blocks $T$ and doing the arithmetic to convert between each variable let's simplify things by measuring hlen in terms of PRF's output length.

Instead of dklen bytes and hlen bytes per block T, let's just say dklen and hlen are in units of $T$'s block size. This is easier because hlen is automatically 1 by definition. We can use $k = \lceil dklen / hlen \rceil$, the number of T in

DK = T1 || T2 || ... || Tdklen/hlen

The cost of generating one block T is however much work is needed to compute $c$ iterations of the PRF function. The cost to generate the entirity of DK is $k$ times the cost to generate one $T$. So we get $C_D = k \times c$.

For the defender to maximize the strength of their password-hash they will want to set $C_D = k \times c = W$. This is the trade-off between iteration count and key length. If you want to double your key length ($k = 2$) then you need to half $c$.

On the other hand the attacker doesn't need to generate all of DK. It suffices to generate any one $T$ and check that block to see if their password guess was correct. Therefore no matter what value $k$ is, $C_A$ always equals c.

The ratio $\frac{C_D}{C_A} = \frac{k \times c}{c} = k$. So if you double $k$ then you force the good guys to do twice as much work as the password crackers. If you triple $k$ then the defender does three times as much work per password tried as the bad guys. You want to minimize the ratio to give the attacker the smallest advantage. Therefore you are always better off using $k = 1$. That's why I said use a key-based KDF if you need more than hlen bytes of output.

Joke answer: Or you could set $k = 0$ and use Argon2 instead. It's stronger and it has the advantage that you don't need to think about this kind of stuff... as long as you follow the recommended procedure for choosing parameters.