Is it easier to crack the Vernam Cipher with more than two ciphertexts

Yes, in practice the more ciphertexts you have with the same key, the easier it is to break the encryption:

With more ciphertexts, you'll have more chances of hitting a crib, the more plaintext you'll reveal when you do, and the easier it is to be sure that a particular match is correct and not just plausible-looking by chance.
The more ciphertexts you have, the more opportunities you'll have for extending a decrypted segment, since you only need to guess how one of the messages continues outside the segment.

This homework exercise with 11 messages XORed with the same key is a good example: you can solve the puzzle almost entirely simply by starting with the assumption that the plaintexts (mostly) consist of ASCII letters and spaces, and observing that — due to the way the ASCII code is arranged — XORing a space with a letter has a specific and distinctive effect (it just flips the case of the letter) that is easily distinguishable from the result of XORing two letters (producing numbers, punctuation and/or non-printable control characters) or two spaces (which just produces a null byte).  With 11 plain English ASCII messages, most positions in the aligned ciphertexts end up containing a space in at least one of the messages, and the few remaining gaps are then easy to fill in.


If all you're using HKDF for is deriving subkeys from a uniformly random master key, you don't really need the Extract part of HKDF.  So you can simply use your master key directly as the IKM input to HKDF-Expand, and the serial number (plus possibly other identifying information, if you e.g. may need to derive multiple keys per card) as the info input.


What are the cryptographic assumptions in the Dolev Yao model?

In Dolev-Yao and other formal models, the assumptions about adversary behavior are encoded via the grammar and entailment relation, and there's no mention of a specific computational definition of encryption security.

But your question is still meaningful, and can be interpreted as follows:

  If my encryption scheme is CPA secure, and my protocol is secure in the sense of Dolev-Yao, then is my protocol necessarily computationally secure?

This question has been studied, starting in a very nice paper by Abadi and Rogaway.  For your question, their answer is "No, but CPA is almost enough."  Caveats in the security definition involve whether the adversary can detect if two ciphertexts were generated with the same key, or if you encrypt "key cycles", whether message length is leaked, etc.  The linked paper resolves all of these details.


Does a cipher exist with the following properties?

Could you be looking for a password hashing KDF function with a secret parameter (a.k.a. pepper)?

With the correct password, the verification succeeds in a flash; without it, you can neither find the password, nor the keys derived from it.

Also, since it's not data/message encryption, the input and output are "short".

Of course, what appears to meet the description could still fail to provide the functionality that you want, so you have to rethink from the start to determine what security service(s) you want.

E.g.

confidentiality,
integrity protection,
authenticity guarantee,
non-repudiation,
recipient exclusion,
proof-of-work.


Time taken for Brute Force Attack on DES

You got $2^{56}$ different keys and the attacker can test $10^{13}$ keys per second.

In the worst case, the last tested key is the solution. For that you need $2^{56} / 10^{13} \approx 7205$ sec. -> around $2$ hours.

In the best case, the first tested key is the solution. This takes about 1 second.

On Average you need to test half of the keys. That means: $0.5 * (2^{56} / 10^{13}) \approx 1$ hour.


Why is Diffie Hellman used alongside public keys?

DH is often used to build session keys, which are used to provide forward secrecy. If you only use the public key in the certificate, then corrupting the private key may reveal all the previous encrypted messages. The attacker can first decrypt the symmetric keys then decrypt previous messages if it keeps records of the previous communications. Using DH can prevent this. Even if you have the private key, you still can not figure out any previous DH results to get the symmetric keys. In this way, the privacy of previous messages is still maintained.


Two mutually untrusted parties want to exchange data: how to ensure each one gets the data it needs?

It can be done, but the algorithm is a bit complex and the hashes have to be specially constructed. The basic idea is this:

What you need is a way for each party to give the other a verifiable "clue" that reduces the search space for the possible file, say by a factor of 10. As soon as one party stops giving clues, the other stops giving clues as well. So a deceiver can, at worse, give you one fewer clue than you have given him.

That means you may have to do 10 times as much computation as he does to recover the file, but that's not enough to make the task possible for him but impossible for you.

One way to do this is to encode the file such that every byte is needed to recover any byte of it (for example, you can do this with no waste of bytes using an erasure code). Then you can make the hash actually include four hashes. One is of the entire encoded file. The next is of the file with the last two bytes missing. The next is of the file with the next three bytes missing. The last is of the file with the next four bytes missing.

You can then exchange all but the last 10 bytes of the file with the other side and validate this by hash. Then you can exchange the next four bytes and validate. Then the next three, and so on through the four rounds. At worse, a deceiver leaves you with 256 times more work to do than he has. So if he needs the file within a day, at worse you get the file within 256 days.

You can switch to nibbles and make this 16 instead of 256 at the cost of more hashes and more exchanges.


Is this paper's technique for factoring RSA 2048 with noisy qubits realistic?

I'm one of the authors of the paper.

In order to make the paper more approachable, we factored each major optimizations out into its own paper. There are three of these sub-papers, and they each stand on their own mostly independent of the others.

"Approximate encoded permutations and piecewise quantum adders
". We put small amounts of padding at various places in our registers so that we can perform addition operations in piecewise fashion and also avoid normalizing modular integers into the [0, N) range until the end of the computation. There are information leakage issues that we had to solve in order to apply these operations in a quantum context, and these cause the representation with padding to be approximate, but otherwise it's a known standard classical technique (e.g. it's called "nails" in GMP).

Modular addition using these approximate representations are significantly more efficient than modular adders using the normal representation. For example, here is a comparison of the time*space of each addition when targeting a 0.1% total approximation error rate over the entire algorithm. The "runway" entries are the ones using the approximate representations. The runway entries are significantly better across the entire span of register sizes:

These representations build on previous work by Zalka from 2006.
"Windowed quantum arithmetic". Classically, if you know what constant you are going to multiply by when producing a physical multiplication circuit, you can specialize the circuit to that factor. This allows you to make the circuit smaller and more efficient. There is a quantum equivalent to this optimization, where the quantum program can be optimized using knowledge of the classical constant you are going to multiply by. We use this to make n-bit quantum-classical multiplication programs log(n) times shorter.

We then generalize the technique, apply it simultaneously to the exponentiation part of the circuit, and save another factor of log(n).

This paper builds on previous work by R. Van Meter from 2005 (although we didn't actually know this when writing the paper, so it is not cited in the current version).
"Flexible layout of surface code computations using AutoCCZ states". This one is by far the most quantum-mechanics-y, so I won't try to explain the details. You can think of it as finding a better way to pack the computation, reducing the amount of space overhead used when routing data around and also allowing it to progress at a rate limited by the classical control system's reaction time instead of by the error correction code distance.

The main contribution here may actually be saying what the layout is in the first place, as opposed to just talking about it in the abstract. We have an operating area where the ripple-carry addition zig-zags back and forth horizontally, while input data streams through vertically, and the operating area is gradually moved as the data is processed.

Location of data (rows from top to bottom) over time (left to right):

A mocked up snapshot of the 2d data layout during a small amount of time:

The ideas in this paper build on previous work by Fowler from 2012.

In summary, there are a lot of ideas in the paper but they are not radically new (they build on previous work) and they are not strongly coupled (if one is wrong, the others will still stand). So I see the savings as being on pretty strong footing. I'm more worried about whether or not people will be able to build quantum computers with 20M qubits than I am about the estimate being off by a factor of 2.


is $T^{1-1/n}$

Proof:

Suppose we have a sample set $M$, with $|M| = m$. We choose a set $N$ with $|N| = n$ among the set $M$, which is $O(m^n)$ (you know $O(m^n)=m\cdot(m-1)\cdot...\cdot(m-n+2)\cdot(m-n+1)$). In particular, we suppose $A_1, A_2, ...., A_n$ make a $n$-collision $H(A_1)=H(A_2) , H(A_2)=H(A_3) , ... , H(A_{n-1})=H(A_n)$ just as you want. Since each one of these $n-1$ events happens with probability $1/|T|$, the probability that a particular set $N$ chosen from $M$ is a $n$-collision is $O(1/|T|^{n-1}))$.Using the union bound, the probability that some set $N$ is an $n$-collision is $O(m^n/|T|^{n-1})$ and since we want this probability to be close to 1, the bound on $m$ is $T^{1-1/n}$


Are variable-length crypto hash functions still susceptible to collisions?

Is there any work done to show or prove collision resistance gained by increasing digest length?

Actually, as CodesInChaos has mentioned, the variable length versions of Keccak ("SHAKE128" and "SHAKE256") are known not to have any collision resistance beyond their security level, independent of how long we make the output.

So, what's the point?  So, as you ask:

  What are the other benefits of allowing variable and arbitrary length output?

That's because collision resistance isn't the only property we want from a random-looking function.  One such alternative use is a Key Derivation Function; this is a function that takes as input some secret data (e.g. DH shared secrets) and some public data (e.g. nonces) and converts that into session keys; these are a series of encryption and MAC keys (and as we might have several such keys, and they're of variable length, this set of session keys is long and of variable length).  Now, a number of KDFs are in use by real protocols (such as TLS), however these constructions are ad hoc, and actually rather ugly looking.  It would be nice to use a single function that's designed to do that; a "variable length hash" (or XOF, that's what NIST dubs it) may be cleaner.


Trapdoors for Lattices: CCA-secure encryption

You misunderstand what "decode" does. As mentioned earlier in the paper:

  The system has message space $\{0,1\}^{nk}$, which we map bijectively to the cosets of $\Lambda/2\Lambda$ for $\Lambda = \Lambda(G^t)$ via some function encode that is efﬁcient to evaluate and invert. Concretely, letting $S \in\mathbb{Z}^{nk×nk}$ be any basis of $\Lambda$, we can map $m \in\{0,1\}^{nk}$ to $encode(m) = Sm \in\mathbb{Z}^{nk}$.

This is to say that encode is a function from $\{0,1\}^{nk}\to \Lambda/2\Lambda$, and decode is therefore a function from $\Lambda/2\Lambda\to\{0,1\}^{nk}$.
Note that your expression is of the form:

$$\underbrace{2(\overbrace{s^th(u)G\bmod q}^{\in\Lambda})}_{\in 2\Lambda} + \overbrace{encode(m)\bmod 2q}^{\in \Lambda/2\Lambda}$$
Note that $\Lambda/2\Lambda$ is (by construction) invariant under translation by elements of $2\Lambda$. The construction is simply adding an element of $2\Lambda$ to $encode(m)$, which by the aforementioned invariance will not impact decoding.
Note that this may map the particular representative you've chosen of $\Lambda/2\Lambda$ to a different representative, but all of these representatives are viewed as "the same" in $\Lambda/2\Lambda$.

Concretely, consider if you have $\Lambda = \mathbb{Z}$.
Say $encode(m) = b\in\mathbb{Z}/2\mathbb{Z}$. If you add an element of $2\mathbb{Z}$ to this, you'll get something of the form $b + 2k$ for $k\in\mathbb{Z}$ (abbreviated as $b + 2\mathbb{Z}$).
But $decode(b + 2\mathbb{Z})$ is a function from $\mathbb{Z}/2\mathbb{Z}$ to the message space --- it should be the same for any particular representative of an element of $\mathbb{Z}/2\mathbb{Z}$ you give it, so you should freely add any element of $2\mathbb{Z}$ to it without impacting the correctness of decoding.

To be even more concrete, in this situation $decode$ is a function that says "I only care if my input is even or odd, no other details matter". Since adding an even number to any other number doesn't impact its parity, you have that:
$$decode(encode(m) + 2\mathbb{Z}) = m$$
Similarly, in the protocol we have that:
$$decode(encode(m) + 2\Lambda) = m$$


At what point can you you implement crypto algorithms?

"Allowed" or "forbidden" are not the right terms; the Pope won't excommunicate you if you dare implement your own algorithms. The question is rather whether doing your own implementation is a smart move or not.

For learning, doing your own implementation is a good idea. It will teach you a lot on how the said algorithms work. A lot of details on how cryptographic algorithms are designed, in particular symmetric encryption and hash algorithms, come from implementation considerations -- the algorithm designer always tries to find the structure that will ensure the required security properties with the maximum efficiency (speed, code size... on a variety of architectures).

For "production", beware. Cryptographic algorithms, by design, are meant to process confidential elements (in particular keys, that concentrate a lot of secret in a few bits), so it is of the utmost importance that the implementation does not leak information. This is a lot harder than usually assumed. For instance, a very common and, I dare say, highly fashionable theme is about timing attacks through cache behaviours on software platforms (both the L1 cache for RAM access, and the in-CPU cache for jump prediction). This kind of attack can be used, at least conceptually, to extract keys from running systems, typically from another VM that runs on the same hardware (such attacks have been repeatedly demonstrated in lab conditions, so it seems plausible that they may be applicable in practice). Writing an AES or RSA implementation that is immune to cache timing attacks is possible, but it requires a lot of care, and very clear notions on how they work and how computers work. Even if you do not write assembly code, you must at least think about how the compiler for the language you are using will translate your code into assembly.

The bottom-line is that deploying your own implementations in the wild is rarely a good idea. Sometimes you have no choice, because (for instance) there is no available implementation for your target architecture and language, with a license compatible with what you want to do. This is not the common case, though.

Using the same libraries as everybody else means that whenever a nasty bug is found in your products, then your competitors have it too. From a business point of view, this is a good thing.

So you should really write your own cryptographic library... and not use it. If you can write a library, let two months pass, read it again, and not find anything wrong or suboptimal in it, then you are not trying hard enough.


Berlekamp-Massey to construct minimal LFSR

There are no issues with negative indices, even the first (or zero-th depending
on how you want to count them) iteration.

The quantity $d$ is called the discrepancy. During the $N$-th iteration,
$d$ is the difference between $s_N$, the $N$-th bit of the given sequence for
which you are finding the LFSR, and the bit computed by the LFSR that you
have synthesized thus far.  If $d=0$, the bit produced by the LFSR is
the same as the bit in the given sequence and so the current LFSR, which
is guaranteed to produce $s_0, s_1, \ldots, s_{N-1}$, need not be changed:
it is producing $s_N$ also.  On the other hand, if $d \neq 0$, then the
current LFSR needs to be updated, that is, you need to find the shortest
LFSR that produces not just $s_0, s_1, \ldots, s_{N-1}$ but also $s_N$.
How to go about doing this is the crux of the Berlekamp-Massey algorithm.
Note that it is easy to find an LFSR that will produce
$s_0, s_1, \ldots, s_{N}$:
the trick lies in finding the shortest LFSR that will do so.

With that as background, and the further information that $L$ is
an upper bound on the number of stages in the current LFSR, consider
the discrepancy calculation
$$d = s_N + c_1s_{N-1} + c_2s_{N-2} + \cdots + c_Ls_{N-L}$$
which really ought to be expressed as
$$d = c_0s_N + c_1s_{N-1} + c_2s_{N-2} + \cdots + c_Ls_{N-L}$$
but the simpler version works because $c_0 = 1$ always (see the
initialization).  Now, we begin with $c_0 = 1$ and all other $c_i = 0$,
that is, a trivial LFSR with no stages that will produce $0$s for
all eternity if you ask it to.
In the very first calculation when
$L=0$ and $N=0$, we have
$$d = c_0 s_0 = s_0.$$
If you want to use the full-fledged form
$$d = s_0 + c_1s_{-1} + c_2s_{-2} + \cdots + c_9s_{-9}$$
that is fine, as long as you remember that $c_1=c_2=\cdots=c_9 = 0$,
and the values you choose to
ascribe to $s_{-1}, s_{-2}, \ldots, s_{-9}$ don't affect the computation
at all.  But more realistically, you should note that $L=0$ and $N=0$, and so
the term $c_Ls_{N-L}$ that makes no sense to you is just $c_0s_{0-0}=c_0s_0=s_0$,
just it ought to be.

In the form
$$d = s_N + c_1s_{N-1} + c_2s_{N-2} + \cdots + c_Ls_{N-L}$$
correctly interpreted, you never run out of bits because
$c_{L+1}, c_{L+2}, \ldots$ are all guaranteed to be $0$ and
$L$ is upper bounded by $N$ and so $s_{N-L}$ can reach down
to $s_0$, the leading bit of the given sequence, but no farther.

  There are no negative subscripts on $s$ (or $c$) that we ever need
  to worry about.


Are all homomorphic encryption schemes based on latticed-based schemes?

It depends what you mean with "homomorphic".
If you mean "compact and fully-homomorphic" (i.e., one can evaluate arbitrary polytime-computable functions on the ciphertexts, and the ciphertext size does not grow with the function being evaluated), then the answer is essentially yes. All known fully-homomorphic encryption schemes with compact ciphertexts use lattice techniques. Note, though, that this requires interpreting "lattice-techniques" in a relatively broad sense. Indeed:

One can build FHE from indistinguishability obfuscation (here). In essence, this is a construction of a very different nature compared to standard lattice-based constructions. However, all known modern candidate constructions of iO use LWE somewhere (among other, sometimes non-standard, assumptions). See e.g. here, here, and here for the three latest results on this front. Also, any FHE built using this line of work would be completely inefficient in practice.
One can build FHE from different assumptions related to approximate GCD, see this work. However, while the assumption is formally different, this employs essentially the same approach and ideas, but simply instantiated in a different setting that does not directly involve lattices.

If you do not mean "compact and fully-homomorphic", then no. More precisely:

If you do not insist on compactness, there are generic methods to make any encryption scheme fully homomorphic - but the ciphertext will grow exponentially with the size of the evaluated circuit in general. See e.g. this work and this work.
If you want compact ciphertexts, but not necessarily the ability to evaluate arbitrary functions, then there are many homomorphic encryption schemes around. (Textbook) RSA is multiplicatively homomorphic. The additive variant of ElGamal is additively homomorphic when the plaintexts are small enough. Goldwasser-Micali is homomorphic for the XOR operation. Paillier is additively homomorphic over $\mathbb{Z}_n$. BGN allows to evaluate degree-two polynomials, provided that the plaintext remains small. In addition, there are generic techniques to boost these limited homomorphisms (e.g. boosting degree-1 to a subclass of degree-2 polynomials), see e.g. this work.


number of active s-boxes in a block cipher?

There many methods to find the number of active sboxes such as:

search algorithm , you input different scenarios , it is time-expensive process.

Matsui algorithm. code

Mixed integer linear programming.
I recommend you to try MIxed integer linear programming

References:
Differential and Linear Cryptanalysis using Mixed-Integer Linear Programming
Automatic Security Evaluation of Block Ciphers with S-bP Structures against Related-key Differential Attacks
New Impossible Differential Search Tool from Design and Cryptanalysis Aspects


Rabin cryptosystem - How many solutions?

How much will we have solutions?

Assuming:

$p, q, r, ..., z$ are distinct odd primes
$b$ is relatively prime to $n$
There exists at least one solution

Then, yes, there will be precisely $2^k$ solutions.

This is straight-forward to show; as we know there exists a solution $x_0$ such that $x_0^2 = b \pmod n$, then this implies that:

$$x_0^2 = b \pmod p$$

$$x_0^2 = b \pmod q$$

...

$$x_0^2 = b \pmod z$$

We know that the first equation has two solutions modulo $p$; $x_0$ and $-x_0$ (as $b$ is relatively prime to $p$, and hence $x_0 \ne 0 \pmod p$, and $p$ is odd, so $x_0 \ne -x_0 \pmod p$).  We also know there cannot be a third (as that would imply a nontrivial factorization of $p$, contradicting the assumption that $p$ was prime).

Similarly, the rest of the equations have 2 solutions; hence using the Chinese Remainder Theorem, there are $2^k$ was to recombine these solutions into an $x$ value that satisfies all these equations (and hence the original one).

We can also show that any value of $x$ not in the set of $2^k$ will not satisfy one of the prime equivalences, and hence cannot satisfy the original, hence we have precisely $2^k$ solutions.


What good is a hash accompanying a program?

Well, if you can assume that the website hasn't been hacked, then providing a SHA2 hash of a program would allow you do make sure you downloaded (from anywhere on the internet) a good version of the software.

You are right, however, that since the method is publicly known, if someone can replace the binary on the site, they can also replace the hash on the site.

This is why a number of sites now publish PGP signatures of their software, instead of a simple hash. Now an attacker would have to forge the signature, which is computationally infeasible. This assumes that you know the valid public key. How do you get the public key? Well, that is another can of worms.


Elliptic Curve Cryptography insecure when input does not lie on the curve?

Suppose you publish a public key $P = [n]G$ for a secret scalar $n$, where $G$ is the standard base point.

If you are willing to tell me $H([n]Q)$ given $Q = (x, y)$ for any coordinates $x$ and $y$ of my choice, then I can send you a point $Q$ of (say) order 2 on some other curve whose arithmetic law happens to coincide with the curve you meant to use, and learn $H([n]Q) = H([n \bmod 2]Q)$.

How does this work?  Suppose you use the short Weierstrass form $y^2 = x^3 + a_4 x + a_6$.  Since the addition law doesn't involve the constants $a_4$ or $a_6$ at all, and the doubling law involve only $a_4$, it turns out that you will happily compute scalar multiplication of points on any curve with the same $a_4$, so all I need to do is find some $a'_6$ whose curve has low-order points.

When I get back the answer, it is either $H([0]Q) = H(\mathcal O)$ or $H([1]Q) = H(Q)$, so by examining which one you returned, I can learn $n \bmod 2$.  The same applies if I send a point of order 3, 4, 5, etc., and I can combine the results with the Chinese remainder theorem to interactively compute the discrete log $n$ of your public key $P = [n]G$ with your help.

Of course, if you expose the point $[n]Q$ instead of the hash $H([n]Q)$, then my task may be even easier!


A counter has a practical advantage: it makes a random stream seekable instead of purely sequential. Which doesn't matter for a CSPRNG but does for a DRBG and parallelization.

But it also works around two possible issues with recursive calls to a hash function: the cycle length, and fixed points.

Hitting a fixed point would be particularly nasty; what should have been a random number generator would start generating the same value forever.

In practice, the risk is negligible unless your function is not a secure hash function, or has a really small block size. The cycle length is not an issue either, if only because storing all the observed values before biases become exploitable is not practical.

Still, using a counter is reassuring. Hitting a fixed point would have zero security implications. Neither would a point with a very short cycle length.


First I find the question legitimate and trying to evaluate the complexity is not an easy problem. But regarding how it looks like, I would mention beforehand that AES or any other crypto algorithm could be written in many different ways.

See for example https://www.iacr.org/archive/asiacrypt2002/25010159/25010159.ps

BTW any crypto function appears like a map $\{0,1\}^n \times \{0,1\}^m \longrightarrow \;\{0,1\}^n$, with appropriate identification of message and key spaces. We then can mathematically modelize with the theory of boolean functions.

For a chosen m-bit key; $y_i=f_{k,i}(x_1,\cdots,x_n)=\sum_{(u_1,\cdots,u_n)}a_u.x_1^{u_1}\cdots x_n^{u_n}=\sum_u.a_ux^u$, with a compact representation where $u=(u_1,\cdots,u_n)$ and $u_i \in \{-1,0,+1\}$, and $u_i^{-1}=1-u_i$ represents the ONE-complement of the bit $u_i$.

This representation by the boolean function is to indicate the complexity of for synthetisation of a crypto algorithm (even in hardware we can easily build a circuit dedicated to DES, AES or even PKC).
The reduction methods employed in logic design analysis (KARNAUGH, QUEEN_McCLUSKEY,...) are generally limited to a restricted number of variables.
However, boolean functions is an active field of research in cryptography and attacks. See for example how Linear and Differantial cryptanalysis manage the question.

I hope this gives a general idea of this interesting question.


Public key cryptography for website access

Yes and no.

Yes, there is a public-key SSH-like authentication on the internet which is supported by all major browsers and TLS implementations: TLS client authentication. You just have to specify a list of CAs (possibly your own, non-publicly-trusted CA) that are allowed to issue valid certificates and they and only they are going to yield a successful connection.

However there are drawbacks / little benefits to it which is why it isn't actually deployed usually.

No, it is the client who has to own the private key for authentication. Suppose it was otherwise. Everybody could potentially learn the public key, otherwise it would be just a password. So if everybody can learn it, everybody can use it to impersonate the legitimate client making the entire authentication process completely pointless.


First let's clarify notations. $f(x)=x^e \pmod N$ is non-standard, hesitating between

$f(x)\equiv x^e\pmod N$ , meaning $N$ divides $x^e-f(x)$
$f(x)=x^e\bmod N$ , additionally specifying that $0\le f(x)<N$.

What's meant in RSA encryption is the later.

A permutation  of a set is a bijection from that set to that same set. Any injective function from a finite set to a set with the same cardinality (number of elements) is a bijection. Thus we only need to prove that for any integers $x$ and $y$ in $[0,N)$ , if $f(x)=f(y)$ , then $x=y$. We do that in the following.

We assume $f(x)=f(y)$. By definition of $f$ that means $(x^e\bmod N)=(y^e\bmod N)$. That implies $N$ divides $x^e-y^e$. That implies any prime factor $p$ of $N$ divides $x^e-y^e$, that is $x^e\equiv y^e\pmod p$.

It is hypothesized $1=\gcd(e,(p-1)\cdot(q-1))$. Therefore $e$ and $p-1$ are coprime, the multiplicative inverse of $e$ in $\mathbb Z_{p-1}$ is well defined, and there exists a positive integer $d_p$ and a non-negative integer $k$ such that $e\cdot d_p=1+k\cdot(p-1)$.

Raising $x^e\equiv y^e\pmod p$ to that power $d_p$, we get that $(x^e)^{d_p}\equiv (y^e)^{d_p}\pmod p$; thus $x^{e\cdot d_p}\equiv y^{e\cdot d_p}\pmod p$; thus $x^{1+k\cdot(p-1)}\equiv y^{1+k\cdot(p-1)}\pmod p$.

For any prime $p$ and any integer $x$, Fermat's little theorem states that $x^p\equiv x\pmod p$. That allows to prove by induction on $k$ that for any non-negative integer $k$, $x^{1+k\cdot(p-1)}\equiv x\pmod p$.

Thus $x^{1+k\cdot(p-1)}\equiv y^{1+k\cdot(p-1)}\pmod p$ becomes $x\equiv y\pmod p$, that is $p$ divides $x-y$. Similarly, $q$ divides $x-y$.

Here we hypothesize that $p\ne q$ (which is unstated in the question). If distinct primes divide an integer, their product does. It follows that $p\cdot q$ divides $x-y$, that is $x\equiv y\pmod N$, that is $x=y$ given that both belong to the set $[0,N)$; that completes our proof.

Note: the hypothesis $p\ne q$ is necessary. Illustration: $p=q=e=3$, $f(3)=f(6)$.


How long does it take to extract a key from a FIPS-140 Level 2 device?

FIPS 140-2 Security Level 2 does not require any form of security measure to prevent extraction of secrets. It simply requires tamper evidence, that is, it should be possible to notice that such attack took place by looking (for instance) at some seal on the device or at a log file.

To answer your question, extracting a secret may therefore take 0 seconds and 0 dollars.

Only Security Levels 3 states that the cryptographic module must respond to attacks, even though the requirements are not phrased in terms of attack cost, but rather of guidelines the module must follow. For instance, it says that the circuitry should be covered in hard epoxy, but not exactly how, so a manufacturer could also choose a substance a hairdryer can easily melt.

A good source of material to look at is Ross Anderson's group at the University of Cambridge, and more in particular the work of Mike Bond.


AES: a question about dual ciphers and security

Are dual ciphers just as secure?  Yes.

The definition is:

  Two ciphers $E$ and $E'$ are called dual ciphers if they are isomorphic, i.e., if there exist invertible transformations $f(\cdot)$, $g(\cdot)$, $h(\cdot)$ such that $$\forall P, K \quad f(E_K(P)) = E'_{g(K)}(h(P)).$$

Note that $f$, $g$, and $h$ are independent of the key and plaintext.  If you had a random algorithm $\mathcal A(F)$ that can distinguish $P \mapsto E_K(P)$ from $P \mapsto U$ for uniform random $K$ and $U$ with some probability $p$, then the algorithm $\mathcal A'(F) = \mathcal A(P \mapsto f^{-1}(F(P)))$ distinguishes $P \mapsto f(E_K(P))$ from $P \mapsto U$ for uniform random $K$ and $U$ with the same probability $p$ and negligible additional cost, to evaluate $f^{-1}$.
The ciphers $E = \operatorname{AES}$ and $E' = \operatorname{AES}$ are trivially self-dual with $f(C) = C$, $g(K) = K$, and $h(P) = P$ for all $C, K, P$.  Proof is left as an exercise for the reader.  (Hint: It's trivial.)
Using a different representation for $\operatorname{GF}(2^8)$ in each round wouldn't substantively change the cipher.  The algebraic structure would remain identical, but you would have a different S-box in each round.

This would probably only make the crypto more expensive for the legitimate users without imposing any real hurdles on attackers—in fact, it would likely make the attacker's job easier by making implementations more likely to be vulnerable to timing side channel attacks.
Now you need to define a pseudorandom generator of irreducible degree-8 polynomials over $\mathbb Z/2\mathbb Z$, and somehow make it independent of everything else in the cipher that uses the same key.  If you're lucky, that might make it harder to attack, at high cost to a cipher that's already painfully slow in software—and probably even make it significantly costlier in hardware.

However, your job, as an aspiring cryptographer, is not to flail around proposing tweaks that might turn out to add security if you're lucky.  Your job is to demonstrate that the changes thwart all existing techniques for cryptanalysis more thoroughly than the simpler approach taken by AES.

Consider starting with smaller, simpler tweaks to AES.  There's an entire book on the design and implementation of Rijndael by the authors, in addition to stacks of literature.  What small tweaks to the design space documented in it can you break or prove resistant to existing cryptanalysis techniques?

As poncho noted in a comment, the easiest way to make AES stronger is to add more rounds.  If your tweak expands the security margin, is its expansion of the security margin greater than that of just adding more rounds?  Is it cheaper than just adding more rounds?


Refreshing Procedure in FHEW: membership test

There are to my knowledge two articles that develop further on generalized member test (or even function) extraction, I hope this may help you out:

https://link.springer.com/chapter/10.1007/978-3-319-22174-8_7 and
https://eprint.iacr.org/2017/996.pdf

A small difference there is that the ring dimension is a prime rather than a power of 2, and this eliminates the symmetry constraint.

I think you are right about the XOR almost for free working also for $t=4$, though it may require to change other parameters to get the error bound right. As for the almost-free part, note that you could extract both the carry and the xor out of the same ciphertext, and the extraction part is much cheaper than the rest of the loop: you get both bit out for essentially one refresh.


For TLS AES_CCM mode how does CBC_MAC work when the message length is not aligned to block size?

See RFC 3610, 2.2 Authentication (page 3):

  The message blocks are formed by splitting the message $m$ into 16-octet blocks, and then padding the last block with zeroes if necessary.


Does “SHAttered” only work for PDF files?

The current version of the SHAttered website has an image that describes the structure of the attack, relative to the PDF.  I believe under fair use we can reproduce the image below:

So the collision blocks reside inside a JPEG image inside the PDFs.  JPEG file formats are a complicated topic, but modern software supports a variety of metadata in JPEGs—this is for example how cameras store the date and time that a photo was taken, the GPS coordinates where the photo was taken, camera settings that were used, pre-rendered thumbnails for quicker display at small resolutions, etc.  So you can create JPEGs that look exactly the same (same image data) but different metadata; and evidently you can also exploit this property to create JPEG files that look different but have the same SHA-1 digest.


Explain the mathematical definition of a cryptosystem using words

The direct translation would be something like :

  For each key $e$ in the set of keys $\mathcal{K}$, there is a key $d$ also in the set of keys $\mathcal{K}$ such that the decryption function using $d$ as a key, called $D_d$, when applied to the encryption function using $e$ as a key called $E_e$ is the identity function, so that when both are applied in a succession, starting with $E_e$, to a plaintext $p$, one will recover the same plaintext $p$.

So, for each encryption key $e$, there is a decryption key $d$ (possibly the same key) which allows to decrypt the content encrypted using the key $e$.


What is the complexity of finding SHA-1 collisions?

Yes, according to the technical paper linked from that site:

  the state-of-the-art collision attack on full SHA-1 was presented by Stevens [Ste13b] with an estimated cost of $2^{61}$ calls to the SHA-1 compression function.

They further state:

  Based on experimental data obtained in this new work and the 2013 state-of-the-art collision attack, we can project that a real SHA-1 collision will take between 49 and 78 days on a 512 GPU cluster. Renting the equivalent GPU time on EC2 will cost between 75K US\$ and 120K US\$ and will plausibly take at most a few months.

I would be surprised if no one has a search running in the next couple of months (if not already).


The truth density $p$ is arguably the same concept as the bulge to 0 $b$ of a Boolean function as $b=1-2p\iff p=(1-b)/2$. The bulge leads to cleaner formulae in many cases though. The language of bulges was common at Bletchley Park. Do you count the General Report on TUNNY as a 1945 or a 2015 publication?


In general, the idea of a Gibbs sampler is to sample from the joint distribution $\Pr(X_1, X_2, \dotsc, X_n)$ on many variables $(X_1, X_2, \dotsc, X_n)$ using samplers for the conditional distributions on each single variable given all the others: $\Pr(X_1 \mid X_2, \dotsc, X_n),$ $\Pr(X_2 \mid X_1, X_3, \dotsc, X_n),$ $\Pr(X_3 \mid X_1, X_2, X_4, \dotsc, X_n),$ and so on.  The process is simply to randomly pick an initial state $(X_1, X_2, \dotsc, X_n)$, and then iterate picking a variable $X_i$, discarding it, and replacing it by a sample from the conditional distribution on it given all the other variables.  Under certain assumptions, in the limit as the number of iterations grows without bound, the distribution of the resulting values for $(X_1, X_2, \dotsc, X_n)$ is the intended joint distribution.

Here, besides the known ciphertext $C$, a sequence of letters, we have a few random variables:

$P$, the unknown plaintext, a sequence of letters
$R$, the unknown key, also a sequence of letters, determined by the plaintext $P$ because $R = (P + C) \bmod 26$
the word boundaries of the unknown plaintext—e.g., if $P$ is expertsexchange, it could be broken down into words as experts exchange or as anything else
the word boundaries of the unknown key—e.g., if $R$ is iamtheverymodel, it could be i am the very model or iam th every mo del

At each step, you can pick some variable to change:

Pick new word boundaries for $P$: instead of uvular laryngeal, try uv ulary n geal, for example.

Exactly how the authors sample from the distribution on word boundaries is unclear, but one possibility is:

Choose a candidate uniformly at random from all possible word boundaries.
Evaluate the probability of the old sequence $\Pr(P)$ and the probability of the new sequence $\Pr(P')$ in the combined word/trigram model.
Flip a coin weighted by $\Pr(P')/\!\Pr(P)$; if it comes up heads, take the new sequence, but if it comes up tails, keep the old sequence.

(This is a kind of local Metropolis–Hastings sampler.  Maybe they have a more efficient way to sample from this distribution.)
Pick new word boundaries for $R$, by the same process.
Given a set of word boundaries for the plaintext, say careful with that, go through each word-length chunk and sample a new word of that length at random from the dictionary—for example, you might kick out careful and draw a new word verdant, or you might kick out the entire sequence of words and replace them by baleful were they.

The distribution on new words is determined by the probability of the new value for $P$ and the new value for $R$ in the combined word/trigram model.  Doing a single word at a time is cheaper, but may be more likely to get stuck; doing a block of words at a time is more expensive but moves around in the distribution more rapidly.

Again, you might use a kind of local Metropolis–Hastings sampler for this, or maybe they have a more efficient way to sample from this distribution.

Another possibility—if the words are independently distributed in a sequence in your word model, which they may not be—is to flip a coin weighted by $\lambda$, and if it turns up heads, pick a word at random from the dictionary, whereas if it turns up tails, pick a word at random from the trigraph model.  This sampler gives words $P$ with the probability distribution $\lambda \Pr(P \mid \text{word LM}) + (1 - \lambda) \Pr(P \mid \text{letter LM})$, under certain assumptions about the word LM and letter LM models.
Same for the words in the key.


How to generate a random number so server cannot cheat?

One possibility is the sloth and unicorn approach of this paper.

The idea is essentially to use a slow (but quickly verifiable) hash.  If the sever publishes a commitment to all the shares within a few seconds of the start of the hash computation (which will start at a agreed-to time), and the hash can't be done in less than an hour, then the server can't select its own share to tilt the game in its favor.

The downside, of course, is this is relatively expensive; we're willing to assume that the server will be willing to devote an hour of computation.  For the point of the paper (trusted Elliptic Curve generation), that's reasonable (as you don't do that all often); for other uses, it might not be quite so realistic.


Formula for the number of expected collisions

The expected number of collisions (assuming that the hash function can be modeled as a random function) is precisely $2^{-n}\binom{m}{2}$; that is, the expected number of pairs of values $x \ne y$ with $H(x) = H(y)$ (and so, to answer Ricky's question, $H(x) = H(y) = H(z)$ would count as three collisions).

The reasoning is the obvious one; there are $\binom{m}{2}$ separate pairs, and each pair has a probability $2^{-n}$ of colliding (and hence has an expected number of collisions of $2^{-n}$), and the expected sum of a set of probabilistic values is the sum of each individual value's expectation.  The probabilities are not independent (for example, if $H(x)=H(y)$ and $H(y)\ne H(z)$, we know that $H(x) \ne H(z)$); it turns out that the expected sum doesn't depend on independence.


In veracrypt when i generate a random keyfile, does the size of the keyfile mean anything?

When you generate a random key file it says that it can create the file anywhere between 64 and 1048576 bytes, so does that mean that a 1048576 byte file is more secure then a 64 byte file?

Mathematically speaking no. 64 bytes is 512 bit at which point guessing the keyfile is as expensive as guess the data encryption keys used for volume directly. Note that even if you use double or triple encryption a 512-bit random string is well beyond feasible for anybody to guess physically, as even guessing a 256-bit secret is.

The only argument for something larger than 64 bytes is that if you assume an attacker that can only say leak 1 byte per hour from memory / your filesystem (or something similarly slow), it would take longer to assemble 1MB than to assemble 64 byte. Of course the question of whether assuming such an adversary is sensible or not depends on your threat model...

In case you are wondering why it says above that the key is 512-bit long when AES-256 is used. The reason is that XTS uses two AES keys which are derived from the password in a secure manner transferring the security of the password to the combined key.


Using scrypt to generate key + IV/nonce together

Yes, this is secure, even though scrypt uses PBKDF2 inside. PBKDF2 has the issue that it the work factor is required $n$ times where $n$ is the number hash outputs concatenated to create the final PBKDF2 output. That means that if you can check the validity of PBKDF2 using only the initial bits (in your case used for the key if the hash was SHA-256, for instance) that you have less of an advantage over an attacker. Basically your initial advantage is divided by $n$.

In scrypt however the final output calculated using a single iteration of PBKDF2, basically turning PBKDF2 into a KBKDF (key based key derivation function) where the calculation of the salt is used as the work factor. As the output size only relies on this single iteration the attacker would not gain an advantage.

That all said, it may make more sense to use a true KBKDF - such as HKDF-expand - to calculate two separate components (key and nonce) from the output of scrypt. In that case the OtherInfo part of the KBKDF (the derivation data) can be just an ASCII representation of the string "key" and "nonce".

So say that p = 1 and MFLen = hLen = dkLen = 32 bytes (output length of SHA-256), then perform:

m = scrypt(Passphrase, Salt, N)
k = HKDF-expand(m, "key", 32)
nonce = HKDF-expand(m, "nonce", 16)

Note that a KBKDF such as HKDF does not contain a work factor; i.e. all the time is still spend in the call to scrypt, not in the calls to HKDF.


Does anyone still use BAN or GNY logic in practice?

I don't think they are even used academically anymore, possibly because of soundness problems and limited expressivity. I would not recommend this approach.


How do I detect a failed AES-256 decryption programmatically?

You should use an authenticated encryption mode.  There are several reasons for that, but one (relatively minor) one is that it automatically gives you the ability to detect incorrect keys, since the authentication will fail.

If you insist on using a traditional non-authenticated encryption mode, or if you'd like to have some way of distinguishing "incorrect key" from "corrupted ciphertext", you can include a key check value together with the ciphertext, and verify it before attempting decryption.  There are several possible ways to implement one.

A traditional method is to encrypt an all-zero block using the raw block cipher (i.e. "ECB mode") and use the resulting ciphertext as the key check value, but note that this makes it possible for an attacker to tell whether two messages have been encrypted using the same key by comparing the key check values.  Alternatively, assuming that you're using an authenticated encryption mode anyway, you could just generate the key check value by encrypting an empty message using the same mode.  Assuming that you're using a unique nonce / IV for each encryption, as you should be, this should eliminate the information leak by making every key check value also unique.

(BTW, note that compressing data before encryption can leak (extra) information about the plaintext.  Basically, this happens because all general-purpose encryption schemes necessarily leak information about the length of the plaintext, and compression makes the plaintext length depend on its content.  Padding reduces this leak slightly, but does not eliminate it.  This has been used in actual attacks.)


What information does $\mu$ leak about $\lambda$?

The safe assumption is: all. It must be assumed that knowledge of $\mu$, together with the public key, allows computing $\lambda$ (which allows decryption and factorization of $n$).

At least, that holds in Paillier's scheme as described in Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography (section 13.2.2). In this we have $p$ and $q$ of equal size, $g=n+1$, $\lambda=(p-1)(q-1)$, and $\mu=\lambda^{-1}\bmod n$. It follows that $\lambda=\mu^{-1}\bmod n$, allowing computation of $\lambda$ from $\mu$ and $n$ (using e.g. the extended Euclidean algorithm, which is inexpensive).

While that does not immediately tell how to compute $\lambda$ from $\mu$ and $n$ in Paillier's scheme as in the question, that's enough to show that we can't safely reveal $\mu$.


Perhaps you are referring to a polymorphic virus?  This is a virus which consists of a decryption program along with the actual virus code which is encrypted.  When the virus runs and subsequently spreads, it re-encrypts itself with a different key, thereby appearing to be different each time it propagates.


It should not be possible to attack this scheme itself. The XOR function will work like a one time pad, where the output of each PRNG can be either the plaintext stream or the key stream. So the output of the function should be random as long as one of the two streams can be thought to be a secure and well seeded PRNG.

In real life scenarios the main cause for concern is not the PRNG itself; the source of entropy (seeding) is much more of a concern. In this scheme entropy is exchanged for a more secure PRNG. It is questionable if this is worth the cause. Using the same entropy is for both PRNGs is not a good idea, it may open the scheme to attacks and will certainly invalidate any security proof.

Furthermore, synchronizing the streams generated by the threads may require large buffers which are effectively representing the state of your new PRNG. It is required to deal with thread synchronizing issues and overhead as well and it is important not to leak any state while doing any of this. It may be easier to put the two functions in the same thread to maintain a small state.

In conclusion, I don't think there are theoretical issues with your scheme, but I don't see how it would be a practical scheme. Most importantly it seems to solve an issue that is not really present. You trade entropy and speed for a more secure PRNG, which is not likely to be a cause of concern in the first place.

Note that I don't see how the results of Boneh and all apply to the new PRNG. Their results are used when multiple hash functions are used on the same data, possibly using XOR. I don't see how it would apply on generating a key stream. That said, it is questionable if any attacks on the underlying hash function translate to the PRNG anyway.

You are likely better off using the additional entropy to reseed more often.


My answer focuses on the AES matrix only. In general, an $A$ matrix with all submatrices having full rank generates an MDS code when concatenated by an identity matrix of the right size to form $[I|A]$, but that's really a coding theory matter.

As to the specific question, this is basic linear algebra but you need to work over the field that AES is defined over. Let the $k\times k$ matrix (like the AES mixing matrix) be
$$A=\left[
\begin{array}{cccc}
a_{1,1}&a_{1,2}&\cdots&a_{1,k}\\
 \vdots &&& \vdots \\
a_{k,1}&a_{k,2}&\cdots&a_{k,k}
\end{array}
\right]
$$

The $1\times1$ submatrices are all nonzero, they're just the entries of $A.$

The $2\times 2$ submatrices: choose any two rows or columns. you can also use the fact that the matrix is circulant to reduce the cases.

So the matrix
$$\left[\begin{array}{cc}
a_{1,1}&a_{1,3}\\
a_{2,1}&a_{2,3}
\end{array}
\right]
$$

is the same matrix as
$$\left[\begin{array}{cc}
a_{2,2}&a_{2,4}\\
a_{3,2}&a_{3,4}
\end{array}
\right]
$$
and thus has the same determinant, etc.

The $4\times$ submatrix is the whole matrix.

Row and column swaps only change the sign of the determinant and can be ignored.

Edit: You need to use the finite field with 256 elements as explained in the link below.

How to use the Extended Euclidean algorithm to invert a finite field element?

This is NOT mod 256 arithmetic.


No.  You can generate such a dataset for yourself by generating lots of RSA keypairs yourself.  Therefore, there's no need for such a dataset (and no reason why anyone would publish one).


It sounds like you're using a password-based key derivation function that accepts an optional salt input to convert a passphrase into an encryption key, which you then use to encrypt messages with a block cipher mode (or possibly some other type of stream cipher) that takes an IV or a nonce, and you want to know whether it's necessary to provide a salt to the KDF, given that you're encrypting every message with a unique IV.

In general, the answer is "possibly, but at least using both won't hurt."

An IV and a salt really have two completely different security goals.  An IV is used as part of the encryption process, and its main purpose is to allow the same key to be securely used to encrypt multiple messages.*  If the same key and IV are used to encrypt more than one message, inspecting the ciphertexts can leak some information about the plaintexts.

(The exact information leaked depends on the cipher mode: for CBC and CFB modes, it includes the length of any common prefix shared by the messages, and possibly some information about the first cipher block that differs; for CTR and OFB modes, reusing the IV leaks the bitwise XOR of the full messages!)

A salt, on the other hand, is used in the key derivation process,** and its main purpose is to slow down certain kinds of brute-force password cracking attacks by, on one hand, ensuring that two users with the same passphrase won't end up with identical keys, and on the other hand, preventing attackers from precomputing passphrase/key combinations in advance.

(Some KDFs may also use the salt to allow multiple quasi-independent keys to be derived from the same passphrase, while other KDFs have a separate parameter for that.  Similarly, some cipher modes may also have additional requirements on the IV; for example, CBC mode needs an IV that is not only unique but also unpredictable to resist certain chosen-plaintext attacks.)

In particular, a password-based key derivation function should implement key stretching, i.e. it should be deliberately resource-intensive to compute in order to slow down brute force attacks.  Including a unique salt in this process is important, because it prevents an attacker from gaining a significant advantage by targeting multiple users in parallel.

Without a salt, an attacker could just run the slow key-derivation process once for each password, and then quickly test the resulting key against every captured message.  Salting the KDF forces the attacker to instead repeat the slow key derivation process for each user / message separately.  An IV will not help here, since it's applied only during the encryption step, after the slow key derivation process is over.

IVs don't really have any effect on brute-force password guessing attacks like this; the kind of attacks prevented by proper IV usage are plaintext-recovery (not key-recovery) attacks based on reusing the same key and IV to encrypt multiple message, which can leak information about the plaintexts for those messages.

Note that, if you're only encrypting a single message with each key produced by your KDF, then you may be able to safely use a fixed IV.  But in that case, you definitely need to use a per-message salt in your KDF, to guarantee that the keys will really be unique.  In any case, even if not strictly necessary in this case, using a random unique IV is still the safe default choice.

Ps. In any case, you really should be using an authenticated encryption mode instead of plain CBC to protect against active tampering attacks.  Among such modes, I'd like to particularly mention SIV mode (RFC 5297), which is designed to offer extra resistance against accidental IV reuse.

*) At least, that's true of the kind of IVs we're talking about here.  More generally, the term "IV" really just means "initialization vector", and is used for all sorts of algorithms, like hash functions, that involve iteratively processing blocks or "vectors" of data.  Alas, the terminology is probably too entrenched to change at this point.

**) Salts are also used for password hashing in password-based authentication schemes.  Actually, password hashing and key derivation are very similar tasks, and so the algorithms and terminology are mostly the same.

Related links:

What is the main difference between a key, an IV and a nonce?
Can you help me understand what a cryptographic "salt" is?
Why should I use an Initialization Vector (IV) when I have unique keys?


As you are asking about the "best" way to pad, the answer is OAEP for Encryption and PSS for signatures. They are well understood, widely used, and considered secure. They also give you some neat additional properties that your system does not achieve, like preventing partial decryptions and making the message "look random" in the case of OAEP.

If you are actually planning to implement your padding scheme in a production system, the short version is: please don't. Instead, use a standard padding mode like OAEP and an implementation that is used by many people and well understood, and you will avoid a lot of pain and potential security holes.

If this is just a question from curiosity, my questions to you would be:

As @Gilles asked, do you want to encrypt or sign?
As @Maarten Bodewes asked, how did you arrive at this scheme? Where do the magic values come from?
How do you detect where the message ends and the padding starts, so you can distinguish between the two after decryption / when verifying the signature?
How do you make sure that the padding is valid after decryption? Padding should be predictable, as that can give you another indicator if the message has been tampered with.

For more information on padding schemes, see, for example, this question and answer. Also, this question has some additional pointers on how to go about designing and publishing a cipher, which in part apply to the case of designing a padding scheme.


Here's a relatively complete list of the papers on deniable encryption (plus papers containing a lower bound against some type of deniable encryption):

Deniable Encryption by Canetti/Dwork/Naor/Ostrovsky [CRYPTO 1997]
Separating Random Oracle Proofs from Complexity Theoretic Proofs: The Non-committing Encryption Case by Nielsen [CRYPTO 2002]
Lower and Upper Bounds for Deniable Public-Key Encryption by Bendlin/Nielsen/Nordholt/Orlandi [ASIACRYPT 2011]
Bi-Deniable Public-Key Encryption by O'Neill/Peikert/Waters [CRYPTO 2011]
On the (Black-Box) Impossibility of Sender-Deniable Public Key Encryption by Dachman-Soled [PKC 2014]
How to Use Indistinguishability Obfuscation: Deniable Encryption, and More by Sahai/Waters [STOC 2014]
Deniable Functional Encryption by De Caro/Iovino/O'Neill [PKC 2016]
Deniable Attribute Based Encryption for Branching Programs from LWE by Apon/Fan/Liu [TCC 2016-B]


Is there a way to verify an original author using encryption?

Yesish, but only for cryptographic purposes within the scope of this forum.  My last bit will show that this isn't worth hill of beans legally, which also makes this question entirely off topic for practical purposes.

You could do this with a time stamping authority:-

All good fun for amateur cryptographers, but the problems start at step 1. A hash is performed of your original document.  Any good cryptographic hash (such as SHA-256) produces effectively unique outputs for any given input.  Even if the inputs only vary by one bit. So

H("Tankobot") ≠ H("Tankobot ")

There's an extra space at the end of the second hash.  The little bits of the two hash outputs will be approximately 50% different. This is due to the avalanche effect inherent in all respectable hashes.

The negative consequence of this is that your plagiarised work will have to be word for word, character for character and bit for bit the same as your original.  It will have to be in the same human language and the same computer character set.  You'll have to retype and re format the suspect work to then perform the validity check to prove ownership. The slightest variation will result in different signed hashes.

That's great for ASCII type text. If your document is graphical, there are sophisticated water marking techniques which are allegedly robust but have not really be field tested. Results for this are below, but I'm not sure how well noise robustness helps if the student redraws your document images:-

That's all wonderful and this answer stops here wrt cryptography.  In the real world, you're wasting your time.  You might as well post the document to yourself and pray. It might work if you catch a student cheating with homework and spank them.

In court, it's worthless.  This type of effort is termed Poor Man's Copyright.  Neither the courts or copyright offices of the UK nor US recognise these clever techniques.  The time stamp has zero evidentiary value in copyright terms.  Independent creation, derivative works and eye witness testimony of copying are some of the easy spanners that smash your system. This is an immense sector of law and I'm not qualified to provide advice. You'd better not be spanking any students as they can sue you if you can't prove they cheated in court.


2DES Meet in the middle attack complexity

Let $(K,K')$ be the key and let $C=E_{K'}(E_K(P))$.

Generate $$L=[(E_K(P),K):K \in \{0,1\}^k]$$ sorted in a hash table on first coordinate with time complexity $O(2^k).$ You can take a hash table of size a few times $2^k$ to avoid long chains by avoiding too many collisions in the table. Or sort the list at cost $O(k2^k)=\tilde{O}(2^k).$

Now try all $K'\in \{0,1\}^k$ and compute $D_{K'}(C)$ and lookup in the table at constant time, until you get a match. Check a few other plaintext ciphertext pairs to ensure the match is not spurious since the permutation $$u\rightarrow E_{K'}(E_K(u))$$ will typically have some fixed points, which may include $u=P.$ This gives overall time complexity $O(2^k)$ if you choose hash sorting.


Can a device prove the identity of its own code?

No, a device can't "prove the identity of its own code" assuming no hardware modification, if we want this secure and achieved automatically from arbitrary software image made available in machine form representing what's supposed to be the executable code, at least when said image is in part adversarially built (and arguably neither if it is built per common practice).

Whatever remotely gives demonstration of what code is running must be inherently trusted; it can not attest of its own integrity, as thought in the question.

The question's "As an example.." method has a weakness: some of the data hashed can be selectively rebuilt during the hash, rather than really present. The code for the modified hashing part would hash content of actual memory for the bulk of the software image, but synthesized data in the two zones (A) where itself is and (B) where some of the genuine hashing code was supposed to be (actually modified, e.g. by at least a JMP to modified hashing code in A). At runtime, A and B are never actually hashed/checked. A contains the modified hash code and data necessary to reconstruct what's synthesized when apparently hashing A or B; that data includes a copy of the original B, and a compressed form of what A contains in the arbitrary software image made available in machine form (it is impossible to automatically detect that it is not actually functional code/data).

The above argument assumes that the arbitrary software image made available in machine form was prepared specially to make the insertion of the modified hash code easy, using zone A of software that has no real functional value and instead is a placeholder for something adversarially prepared. However, the attack might often be possible assuming only that the software image contains a zone of sufficiently compressible data or code. I'm willing to accept that the attack could not be carried if the entire software image was initially crafted by a non-attacker taking care to code densely; but that goes against modern software construction practice.

The OP is explicitly targeting integrity of the software of voting machines. An example is this one, which (with different software) is still used in France in several cities (Le Havre, Brest..). The entire software is in a socketted EPROM. The integrity of the software is "demonstrated" by the software computing and displaying a CRC of itself on the display. That's of course a complete joke against an adversarial attack (and using a hash would not help much, for the code displaying the hash can be replaced by code displaying the appropriate constant).

The method proposed by the question (where the value displayed depends on a manual entry) would seem, on the face of it, to mitigate the attack where a modified software displays the hard-coded CRC or hash of the software it mimics. However, for the reasons I explain, that's not cryptographically strong against a skilled adversary. And worse, the challenges fed for remote attestation could be used as a side channel to control the rigging of the votes.

That interesting "yes" answer achieves its goal by adding a Trusted Platform Module (a secure CPU with a private key capable of signing, a certificate, and trusted code), and most importantly assuming integrity of trusted boot code of the main CPU, the CRTM. My reasoning above assumed non-integrity of all software, only integrity of hardware.

Integrity of trusted boot code makes a qualitative difference. That boot code can verify the integrity of the rest of the code by verifying a digital signature, with the public key (or the root of a chain of certificates) in the trusted boot code. That's in wide use (e.g. in Point of Sales terminals since the 1990s) and is a reasonably effective measure against unauthorized code modification. This alone is however not achieving what the question asks: that method can't remotely attest that any software is running; it only insures that  only authorized software could run. And it remains quite vulnerable to modification/tampering, by debug mechanism allowing code injection (JTAG port, extra memory dynamically brought into the addressable space by a paging mechanism), and exploitation of software vulnerability bringing hostile code e.g. by buffer overflow (mitigation to the later are possible with Harvard architecture separating code and data, security rings, virtual machines, code proofs..).

To add attestation, the standard and working method is adding a capability to sign with a private key. A simple conceptual model is that the trusted boot code includes a Virtual Machine (e.g. JavaCard), verifies (by checking code signature as above) what code can run in that VM, and remotely attests of what it launched there together with a challenge to prevent replay (preferably by cryptographically signing or MACing, which requires a secret somewhere); it may even dynamically peek at what's in the VM and attest about it. Interpretation in a VM is not essential; principles for hardware equivalents running at native speed  are known since 1960's mainframes. The TPM-locked PC can be viewed as a refinement of that, allowing remote attestation of what is running, under hypothesis reasonable on a consumer PC, including that some code responsible of the attestation is not altered.


Diffie-Hellman key exchange - why is modulo operation necessary?

Would that not work, because the logarithm ($a=\log_gA$) is easy to
  calculate?

Yes, among other things.

We know how to efficiently calculate the logarithm over real numbers (thus this would bear no security).
We can't sample uniformly at random from an infinite range (all natural numbers), that means you can't randomly draw a natural number because every single one will have $0$ probability of being drawn. This makes key-generation hard (yes one could technically limit the length here).
We can't store, let alone transmit, such large numbers. For example assume $g=3$ and now pick a standard-size DH exponent $a$ which has 2048-bit length. $g^a$ will now have $1.5\cdot 2^{2048}$ bit length. We can't store that. We can't even count to $2^{192}$ realistically (with counting being easier than storing).

  And why does the modulo operation have to be done with a prime?

There are a few reasons (why to prefer primes):

It gives us nice mathematical properties. $\mathbb F_p$ is a field, that is every element has a multiplicative inverse, whereas $\mathbb Z_n$ is a ring where not every element has a multiplicative inverse.
It prevents backdoors. If you pick a composite value, the person who knows the factors will have a significantly easier time to compute the logarithm. Picking a prime ensures there's no doubt about anybody knowing any factors if you re-use parameters.


The first Cryptography textbook implicitly containing word regular for hash functions may be in Stinson's book Cryptography Theory and Practice, First Edition, 1995, around pages 234-237. T

  Since we are interested in a lower bound on the collision probability, we will make the assumption that $\mathbf{h^{-1}(z) \approx m/n}$ for all $\mathbf{z \in Z}$. (This is a reasonable
  assumption: if the inverse images are not approximately equal, then the probability of finding a collision will increase.)

Stinson's book is pointed out by Bellare and Kohno's article,

  Stinson, in the first edition of his book, shows that Equation (1) is true under the assumption that $h$ is regular. There is no information regarding the case where $h$ is not regular.

This term is not defined in Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing, 1996

  Of course, the latter attack can be prevented if $\text{MD}$ has additional properties besides being collision-free (e.g., if MD is “regular”).

Only mentioned as an additional requirement for the hash function.
This  definition from Hash Function Balance and its Impact on Birthday Attacks, 2004, by Bellare and Kohno

  Textbooks tell us that a birthday attack on a hash function $h$ with range size $r$ requires $r^{1/2}$ trials (hash computations) to find a collision. But this is quite misleading, being true only if $h$ is regular, meaning all points in the range have the same number of pre-images under $h$; if $h$ is not regular, fewer trials may be required.

A brief result from the Bellare and Kohno's article;

Let $C_h(q)$ be the probability that the birthday attack on a hash function $h: D \to R$ succeeds in finding a collision in $q$ trials.

With balance measurement $\mu$ and up to constant factors

$$C_h(q) = \binom{q}{2} \frac{1}{r^{\mu(h)}}.$$

A collision expected with $r^{\mu(h)/2}$ trials.

$\mu(h) = 1$ meaning that $h$ is regular and this is standard birthday collision.
$\mu(h) = 0$ meaning that $h$ is a constant function so attack has $\mathcal{O}(1)$

This, actually indicates that the values are between regular and constant function. If the balance $\mu(h) =1/2$ than a collision can be found in $r^{1/4}$ trials, less than $r^{1/2}$

Result: If a hash function is not regular, finding a collision is easier than regular hash functions.

Bold in quoted text are mine


I do not remember if we checked this explicitly, but my guess is that in the chosen-plaintext setting the biclique attack would still be faster than the exhaustive search, maybe by the factor of 2 compared with 4 in the chosen-ciphertext setting.

However, both results are pretty far from declaring AES broken in any sense. Such small gain over exhaustive search is admissible by virtually every mode of operation. For modes CBC, CTR, CFB, OFB the situation is even simpler: they claim 64-bit security only, because if the adversary is allowed to ask more than $2^{n/2}$ queries for $n$-bit blockcipher, various collision effects invalidate security proofs. Moreover, it becomes hard to state what sort of security should be provided beyond the birthday bound: should the cipher be indistinguishable from the random permutation or function, or the whole ciphertext (possibly gigabytes long) should have this property.

To summarize, the security claims of AES-CTR are not affected by biclique attacks at all, and probably will never be since the meet-in-the-middle attacks (which include bicliques) usually can not be faster than $2^{n/2}$.


Does the authenticity of messages by Alice still holds if the state of bob is compromised in Double Ratchet

if bob's device is compromised including his long term key.

  Does the ephemeral keys generated by Alice during the half Diffie–Hellman key exchange produces a new sending chain for Alice which is not yet known to bob

Double Rachet is secure against an attacker who records everything than compromise the sender or the receiver. As always said, if the receiver or sender stored previously generated keys then there is no forward secrecy, the attacker gets the keys and reads the recorded messages. Securely delete the keys.

A compromised secret key or device has more attack vectors that can be catastrophic.

The attacker can impersonate the attacked party and create new sessions.
The attackers can execute man-in-the-middle attacks constantly and maintain eavesdropping on the compromised session.

So the attacker will produce new chains that Alice and Bob are not aware of. The key and device must be replaced immediately if they are suspecting.

  if bob's device is compromised including his long term key.

  does the messages from Alice still has the non-repudiation property even if bob's state is completely compromised.

Alice will talk normally, so she cannot repudiate. The attacker has no power to forge a message that does not come from Alice. If they do, Bob can do, too and this is against the non-repudiation of the protocol.


How can I obtain the raw decimal value of an RSA key's modulus?

You've downloaded Google's (or whomever's) certificate. You have it stored in a file called GoogleCert:

$ cat GoogleCert
-----BEGIN CERTIFICATE-----
MIIIdDCCB1ygAwIBAgIIWOU4T7CaLpQwDQYJKoZIhvcNAQELBQAwVDELMAkGA1UE
BhMCVVMxHjAcBgNVBAoTFUdvb2dsZSBUcnVzdCBTZXJ2aWNlczElMCMGA1UEAxMc
...
JmztPlaPUkFUEnAL2aWCAQCHscxb9bMFDmUW/kv/UnBNBBX7PRvl5rPjPeFk9yS5
HU2vHiQa8VY=
-----END CERTIFICATE-----

Use the command openssl x509 -in FILENAME -noout -modulus argument to extract just the Modulus:

$ openssl x509 -in GoogleCert -noout -modulus
Modulus=AAC42564448507CB736A37F...9152FD0458ECF42145

Copy and paste the HEX output into BC using the ibase=16 argument to indicate the input is in Hex:

$ echo 'ibase=16;AAC42564448507CB736A37F...9152FD0458ECF42145' | bc
21557235071938158553153701887793754486919886530446620906710060142975\
...
80517225349695620402252397302295002436481842156355298655378997632358\
23941


Why is RSA encryption significantly faster than decryption?

Yes.  RSA encryption is faster than RSA decryption, assuming you choose the public exponent properly (e.g., you use $e=3$).

This is because raising something to the 3rd power (which is what you do during encryption) is much faster than raising something to the $d$th power, where $d$ is a 2048-bit number (as you do during decryption, assuming a 2048-bit modulus).

The Chinese Remainder Theorem can be used to speed up decryption, but only by a factor of up to $4\times$, which is not large enough to change the bottom-line conclusion.

You can test this for yourself by running openssl speed rsa2048 to test the speed of encryption and decryption using 2048-bit RSA.  On my machine, encryption is roughly $35\times$ faster than decryption.  Don't take this number too seriously -- the exact speedup factor will depend upon a number of factors -- but it demonstrates the bottom line, which is that in RSA, encryption is faster than decryption.


"if everybody know message after it is decrypted there is" still a point in padding,

since it would (hopefully) stop people from learning the message before it is decrypted.

It would probably be better to

sign the message with your private key, rather than encrypt the message with your private key.

RSA needs padding for signatures too, although that padding is different from RSA encryption padding.

Also, although you can probably still get away with 1024-bit RSA since it's just

for a game, but you should make it easy for you to move to longer public keys.


What is the new attack on SHA-1 "SHAttered" and how does it work?

In order to get a collision on a $n$ bit Random Oracle using the birthday paradox, one needs $\sqrt{\pi / 2} \cdot 2^{n/2}$ calls. In other words, in the case of the 160 output bits of SHA-1 the limit is in the order of $2^{160/2} = 2^{80}$.

Previous Attacks

SHA-1 (and the broken SHA-0) have been under the following attacks over the past few years:

Differential collisions in SHA-0 by Chabaud F., Joux A. have collisions in SHA-0 in $2^{61}$ calls.
Near Collision in SHA-0 by Biham E., Chen R. at CRYPTO 2004
Collision of SHA-0 and Round reduced SHA-1 by Biham E., Chen R., Joux A., Carribault P., Lemuet C., Jalby W. at EUROCRYPT 2005
Finding Collisions in the Full SHA-1 by Wang et al. at CRYPTO 2005
Practical Free-Start Collision Attacks on 76-step SHA-1 by Pierre Karpman, Thomas Peyrin and Marc Stevens at CRYPTO 2015
New Collision Attacks on SHA-1 Based on Optimal Joint Local-Collision Analysis by Stevens M. at EUROCRYPT 2013

The 4th paper presented an attack in $2^{69}$ calls showing the weaknesses of SHA-1. The 6th paper will be the ground work of the SHAttered attack.

The main idea behind these attacks relies on Differential cryptanalysis.
You have two inputs $t_0$ and $t'_0$ with a difference of $\Delta_0$. Once these two inputs have gone through the function $f$ (the compression function in the case of SHA-1) you get a difference $\Delta_1$ and so on (see following picture)...

The goal here is to find a difference in the input $\Delta_0$ such that after some iterations you get $\Delta_2 = 0$, in other words no difference.

the SHAttered Attack

Because of the Merkle–Damgård construction of SHA-1, one can choose to alter the differences between the iterations in order to improve the differences to match his needs. In the case of the SHAttered Attack, they chose an initial prefix ($P$), then later on the next blocks they introduce a difference ($M^{(1)}_1$,$M^{(2)}_1$) and remove it ($M^{(1)}_2$ and $M^{(2)}_2$). At this point they already have their collision. They just need to continue with the same following blocks ($S$), leading to a collision on the whole input.

$\mathrm{SHA-1}(P||M^{(1)}_1\mathbin\Vert M^{(1)}_2\mathbin\Vert S)=\mathrm{SHA-1}(P||M^{(2)}_1\mathbin\Vert M^{(2)}_2\mathbin\Vert S)$

The values of $M^{(1)}_1$, $M^{(2)}_1$, $M^{(1)}_2$ and $M^{(2)}_2$ are as follows:

The difficulty is thus to find the correct $M_i$ that satisfy the chosen prefix criteria $P$ and that cancel themselves nicely afterwards. The probabilities of such to occur are really small, thus the need of massive amount of calls to SHA-1 compression function ($2^{63.1}$).

In the case of the provided PDFs, they also give a nice infographic which explain where the difference is located in the PDFs:


Safe generation of $k$ points on a curve such that the mutual discrete logs are hard?

It would be more confidence-inspiring to choose a hash-to-curve method and pass consecutive integers through that.  There is a current (2019-05-16) internet-draft surveying hash-to-curve techniques with references, draft-irtf-cfrg-hash-to-curve.  The most popular method for Ed25519 is Elligator 2.  Since invertibility is not required for your application, you could also just use the hash-and-pray technique: for each $i$, find the smallest $j$ such that $H(i) + j$ is an $x$ coordinate on the curve, where $H(x)$ is (say) $\operatorname{SHAKE128-512}(x) \bmod{2^{255} - 19}$.


What's the difference between these hash functions H, H1 and H2?

The notation $H:\mathbb G_1\to\{0,1\}^n$ means that $H$ takes as input an element of $\mathbb G_1$, and produces as output an $n$-bit bistring.
The notation $H_1:\mathbb G_2\to\{0,1\}^n$ similarly means that $H_1$ takes as input an element of $\mathbb G_2$, and produces as output an $n$-bit bistring.
The notation $H_2:\{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ means that $H_2$ takes as input a pair of $n$-bit bistrings, and produces as output an $n$-bit bistring.
If you ask me, the names are not well chosen. It would be more mnemonic to use $H_1$ (resp. $H_2$, $H$) where there's $H$ (resp $H_1$, $H_2$).
But that's far from the worse there is in this paper. Things like

The ECDLP had been proved to be a hard problem [19].

are wrong (what's cited to support this falsehood actually makes ECDLP tractable on some curves). I hope studying this paper was not recommended as part of a course in cryptography. If so, I fear there's something deeply flawed in this recommendation process.

Addition per comment: I do not see that the authors explain how they build their hashes, except for a mention of SHA-1 in section VI. A reasonable implementation with $n=160$ based on SHA-1 could use
$$\begin{align}
H(g)&\underset{\text{def}}=\operatorname{SHA-1}(c_0\mathbin\|\hat g)\\
H_1(g)&\underset{\text{def}}=\operatorname{SHA-1}(c_1\mathbin\|\hat g)\\
H_2(u,v)&\underset{\text{def}}=\operatorname{SHA-1}(c_2\mathbin\|u\mathbin\|v)\end{align}$$
where $\hat g$ is a bitstring uniquely representing (as a fixed number of bits) an element $g$ of $\mathbb G_1$ or $\mathbb G_2$, and $c_0$, $c_1$, $c_2$ are public distinct 32-bit bitstrings tasked with making the three hash functions somewhat independent from the perspective of security analysys.
Note: SHA-256 or better should be used rather than SHA-1, which is obsolete and quite practically broken as a collision-resistant hash when operating on messages sizably larger than 768-bit. But as far as we know, SHA-1 remains 80-bit secure in the above constructions, because what's hashed is short.
Note: This shall not be construed as an endorsement of the article. I do not understand enough about functional requirements of a Pseudonymous Authentication-Based Conditional Privacy Protocol for VANETs to tell if they are met by the cryptography outlined; and only understand some of the crypto involved. The article does not tell enough to convince a cryptographer about the security of the implementation. In particular, I have doubt that the BLS signature based on "the Type-A curve defined in the PBC library with the default parameters" could be fast, 154-bit as suggested (the exact size is not stated), and secure to the 80-bit security level targeted.


Are formal methods used for cryptographic protocol design?

In my experience the persons doing the standardization may not know about formal methods in the first place. And even if a formal method was used, they would not know how to assess it.

Note that whatever mathematical method is applied, the security of a protocol is still dependent on how the domain was modelled. If the model is even slightly incorrect, a protocol may still be insecure. It would not be the first time - to put it mildly - that a security proof has to be reconsidered.


Unclear about the importance of Initialization Vectors

First, a definition.  An initialization vector or nonce (and these are in fact different things) are  designed for one purpose, and that is to be a non-secret input to a symmetric cipher that allows it to retain semantic security by ensuring that the resulting ciphertext is indistinguishable from random when a given key is reused.

Remember, the only thing that must remain secret in an encryption scheme according to Kerckhoffs's Principal, is the key.  However, if we don't want to generate a new secret key for every single encryption operation, we still need the same message, when encrypted twice, to result in entirely different ciphertexts, indistinguishable from random (what we call IND-CPA).  If encrypting the same message twice results in the same ciphertext, well, we can clearly tell that it was in fact our message that was encrypted the second time, and not a randomly generated value.  This is the property that the initialization vector gives us.

So, first, reusing the key as a the IV defeats the purpose of either a) being able to use the key, or b) providing IND-CPA.   In the first option, we have to generate a new secret key for every encryption operation, track them so we can decyrpt, and keep them secret all the while, as Kerckhoffs's Principal says we must.  In the second option, we begin leaking information.  In a block mode cipher such as CBC, we leak whether two messages are the same, as illustrated above, or if two different messages begin with the same plaintext.   In a streaming mode or stream cipher, the construction is broken catastrophically when a key/nonce combination is reused, allowing potentially complete recovery of the plaintext and keystream.

We resolve these issues by having a separate key and IV.  The key we keep secret, the IV we MAC and can then transmit in the clear with the ciphertext with no loss of security.

One last point.  In addition to their being a very good technical reason for the IV to be different from the key, what I think they were getting at in the comment you quoted was a more general principal that is fuzzier, but still widely held as good practice, and that is that keys should not be reused for different purposes.   You wouldn't use the same key for both encryption and authentication functions, for instance.   You might derive encryption and authentication keys from a single master key using a KDF, but you wouldn't typically want to use a single random key for both purposes.   That, I think, is what they may actually be trying to say without having a terribly solid grasp on the specifics.


Yes there are. I guess you're looking into non-interactive zero-knowledge (NIZK) proofs, since you're assuming that you have at hand a proof $\pi$. A common approach for building NIZKs in crypto is to rely on the Groth-Sahai methodology, which produces highly structured NIZKs using elliptic curves equipped with a bilinear maps. It was first observed in this paper that Groth-Sahai proofs can be randomized - i.e.,  you can randomize a statement together with its proof so that the randomized proof is indistinguishable from an honest proof computed on the randomized statement. This was used to build anonymous credentials with strong properties, and had many other applications in subsequent works.


In OTP you have $C=K\oplus{M}$. If the key is the same $C1=K\oplus M1$ and $C2=K\oplus M2$,  => $C1 \oplus C2$ = $K\oplus M1 \oplus K\oplus M2$ = $M1 \oplus M2$  If you have the same ciphertext, that means that the same message was encrypted. E.g. messages 4,6,7,11 have the same first 6 symbols.


Security issues for integrating AAA and OTP services

Usually OTP needs to send the password in clear text to your AAA server.
As the otp value is concatenated with a static password, the AAA server, which verifies the credentials, need to split the password.

E.g.: Your secret password is "secret" and your OTP generator creates "987432". Then you need to enter "secret987432".

As the client component does not know, how long the OTP value is and how long the fixed password is, the client needs to send the complete string.

It can not send a hash of this, since, the AAA server does not know, if the user entered "secret987432", which is the CURRENT valid OTP value or "secret897832", which would be the next OTP value, which - according to RFC4226 - can also be used for authentication.

So to avoid the stealing of the fixed password during authentication, you need to check if the authentication protocol is properly encrypted.


Is Diffie Hellman key exchange based on one-way function or trapdoor function?

No, the mathematical problem that is used for Diffie-Hellman is the Diffie-Hellman problem or DHP which is different from the trapdoor function that is behind RSA.

One way functions are for instance cryptographically secure hash functions.


Can you change an AES encrypted message if you control the IV?

Consider the case where you encrypt the plaintext message attack at noon!! using AES-CBC-256, with the key 7ac01f50605b8fcebd1c82ea6a6aacd6b112e8c9675b84cd77054b2f49668301 and the iv f822ee7b8c0a8ba40daa773b01d9485a:
echo -n 'attack at noon!!' | openssl aes-256-cbc -e -nopad -K 7ac01f50605b8fcebd1c82ea6a6aacd6b112e8c9675b84cd77054b2f49668301 -iv f822ee7b8c0a8ba40daa773b01d9485a | xxd -p

The plaintext message is one block in length (16 bytes), and no padding is used, so this produces one block of cipher text:
8b2f9ede941cb6f3958d809510f579a5

Naturally, if you decrypt the ciphertext above using the same key and iv, you get the original plaintext:
echo -n '8b2f9ede941cb6f3958d809510f579a5' | xxd -p -r |  openssl aes-256-cbc -d -nopad -K 7ac01f50605b8fcebd1c82ea6a6aacd6b112e8c9675b84cd77054b2f49668301 -iv f822ee7b8c0a8ba40daa773b01d9485a

produces:
attack at noon!!

Now, an attacker who knows the original plaintext (attack at noon!!), the ciphertext, and the iv wishes to modify the iv, so that upon decryption, the plaintext produced is attack at dawn!!.
To see how this is done, refer to the diagram below (copied from https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation):

Consider point labeled E.  E is the AES decryption of the first block (in the case, the only block) of ciphertext, using the key.  We don't know the key, so we can't compute E...
Or, can we?  Looking further, the first block of ciphertext is E XOR IV.  The XOR function is unique in that: if A XOR B = C, then you can re-arrange A, B, and C in any order, and the expression still holds true - i.e. A XOR C = B, and B XOR C = A.  So:
Plaintext = E XOR IV
E = Plaintext XOR IV
IV = E XOR Plaintext

So, knowing the original plaintext (attack at noon!!) and the IV (f822ee7b8c0a8ba40daa773b01d9485a), we can compute E.  To do this, we use E = Plaintext XOR IV (above).  First, use the following command to get the hex representation of the underlying ascii-decoded bytes of the plaintext:
echo -n 'attack at noon!!' | xxd -p

This produces:
61747461636b206174206e6f6f6e2121

Now, XOR the plaintext and the IV to get E like so:
python3 -c "print (hex(0x61747461636b206174206e6f6f6e2121 ^ 0xf822ee7b8c0a8ba40daa773b01d9485a))"

This produces:
0x99569a1aef61abc5798a19546eb7697b

So, E is 99569a1aef61abc5798a19546eb7697b.
Now, we can compute what the IV should be, so that when the ciphertext is decrypted by AES-CBC with our specially crafted IV, and E gets XOR'd with this IV, the plaintext produced will be our wanted plaintext 'attack at dawn!!'.  To do this, we use IV = E XOR Plaintext (above).  First, get the hex representation of the underlying ascii-decoded bytes of the wanted plaintext, like we did before:
echo -n 'attack at dawn!!' | xxd -p

this produces:
61747461636b206174206461776e2121

Now, XOR the the wanted plaintext with E to get the IV that we need, like so:
python3 -c "print (hex(0x61747461636b206174206461776e2121 ^ 0x99569a1aef61abc5798a19546eb7697b))"

This produces:
0xf822ee7b8c0a8ba40daa7d3519d9485a

Let's see if it worked.  Let's use the decryption command above to decypt the ciphertext, using iv f822ee7b8c0a8ba40daa7d3519d9485a in place of f822ee7b8c0a8ba40daa773b01d9485a:
echo -n '8b2f9ede941cb6f3958d809510f579a5' | xxd -p -r |  openssl aes-256-cbc -d -nopad -K 7ac01f50605b8fcebd1c82ea6a6aacd6b112e8c9675b84cd77054b2f49668301 -iv f822ee7b8c0a8ba40daa7d3519d9485a

Sure enough, the plaintext produced is:
attack at dawn!!

***Special thanks to Ángel for helping me work through this in the comments under the question.


Why NIST insists on post-quantum standardization procedure rather than post-quantum competition?

Is there any functional difference on how this process is conducted?

One likely difference is the intended end goal.  The intended result of the AES process was to approve exactly one proposal, and that is what they did.  In contrast, they are likely to approve at least two proposals (both for kem/public key encryption, and the signature side of things, so that is at least four approved algorithms).
There are likely several reasons for this; for one, all the AES candidates did basically the same thing; hence it wouldn't make sense to approve multiple.  In contrast there are some significantly trade-offs between the PQC algorithms; for example, Rainbow has quite small signatures (and huge public keys), while Falcon/Dilithium have (by PQ standards) moderate signatures and moderate public keys.  Which is more appropriate is likely to vary by use case.
The other reason is trust.  When the AES competition happened, there was a fairly good understanding of block ciphers (as we had been examining them for over 20 years); in contrast, we have comparatively less understanding of some of these postquantum algorithms (especially against attacks by Quantum Computers); hence it makes sense to approve several (so that if one is broken by a new discovery, we have a backup).
Now, I'm not NIST, and so these are just my observations; I do believe that I had heard this logic by some speaker from NIST in the past.


How to check whether the given curve is Elliptic or not?

For most cases, you can take this as a (simplified) definition of Elliptic Curve:
An elliptic curve over $K$ (a field) is a plane algebraic curve over $K$ defined by an equation of the form

$y^{2}=x^{3}+ax+b$    (1)

($a,b \in K$) that is non-singular (it has no cups or self-intersection).

Since the curve you give in the question is of the form $y^{2}=x^{3}+ax+b$, we just need to check the non-singularity!

This can be done by computing the discriminant

$\Delta = -16(4a^3 + 27b^2)$.

Fact: an algebraic curve defined by an equation of the form (1) is non-singular if and only if its discriminant is non-zero (this is a standard result in the theory of elliptic curves)

In our case, $\Delta = -16(4*8 + 27*9) = -16(32+243) = -16(275) = 0$ (mod 5)

So the discriminant is zero in the field $\mathbb{Z}_5$, hence the curve is singular, hence it is not an elliptic curve.

Hope it helps, feel free to ask for further details.


This is a form of polyalphabetic substitution cipher. I'm not aware of this particular method having a name.


Use case for extendable-output functions (XOF) such as SHAKE128/SHAKE256

As of now I can think of four different applications for XOFs.
Note that some change the padding depending on the requested output size and so the outputs are truly unrelated, Skein does this.

Signature message hashing. Using an XOF you don't have to rely on ad-hoc constructions for hashing the message in signature schemes to the appropriate size. For example, implementing RSA-FDH is trivial with an XOF while it is not so easy with fixed size hashes. As another example the CFRG of the IRTF adopted SHAKE-256 as the internal hash function for the Ed448 signature standard (which needs an 912-bit hash internally).

Stream ciphers. This may be a artificial but you can in fact abuse your XOF as a stream cipher if you don't want to trust the well studied AES-CTR or Salsa constructions. This was indeed proposed in the Skein specification.

Key derivation. Assume for a second that you didn't know HKDF. You trivially replace HKDF with an XOF in most scenarios as you could simply save the state after processing the master secret and then pad it with the context for each key-derivation. Or if you only need one giant block of derived bits, you'd need to call HKDF or a fixed size hash many times but your XOF only once.

Easier instantiation of random oracles. Some security proofs rely on the so-called random oracle model to prove the security of a given scheme. Normally you'd use some artificial construction around a fixed-size hash function to get the desired output size, but with XOFs you can just plug them right in without having to fear any mistakes on your side potentially breaking the proofs (most people don't know / understand in many cases, me included).

TL;DR: Native XOFs aren't necessary and can be emulated using known "ad-hoc" constructions, but they are highly convenient in random oracle based schemes, in signature message hashing and for fast and easy key derivation.


NIST implementation of the Lucas primality test

Thanks to the references provided by @fgrieu I found the relevant equation in "New
Primality Criteria and Factorizations of2^m+-1" by Brillhart-Lehmer-Selfridge.

In there, Equation (14) says:

$2V_{r+s} = V_rV_s+DU_rU_s$

Which is trivial to demonstrate, given that $D=(\alpha - \beta)^2$.


Attack RSA knowing the public key and brute forcing all possible message

If textbook RSA is used then many attacks are possible, including dictionary attacks. This is because the value that is used in modular exponentiation (called RSAEP in the standard) is just the input decoded to a number. However, plaintext RSA is susceptible to many attacks and is not considered secure; a rather obvious one is when a message with value 0 or 1 is encrypted, as the output would be 0 or 1 as well; no attacks necessary.

Normally however a secure padding method is used. The original scheme from RSA labs was PKCS#1 v1.5 padding. This padding "wraps" the message and includes many random bits that are encrypted together with the message. These bits are not know to an attacker. They can be used to check that the decryption was successful or not. The later padding method OAEP, which is provable secure, should however be used as PKCS#1 v1.5 is vulnerable to attacks on the unpadding of the message. OAEP, just like v1.5 padding, uses random bits.

PKCS#1 reads for OAEP "Generate a random octet string seed of length hLen" where hLen is the hash function used within MGF-1, often SHA-1. That means that hLen is at least 160 bits. That means that 160 bits of randomness are encrypted together with the message. It's at least 63.95 bits for PKCS#1 v1.5 padding but usually it is more (the amount of padding depends on the difference between key and message size).

So no, you cannot use dictionary attacks because the output of the RSA encryption will always be different from the given message - if a secure padding is used. However, if for some reason the random number generator fails and leaks the not-so-random bits then you could match the padding, and perform a dictionary attack.