Is there a way to generate a password from another but those 2 will have no relation?

Using the HKDF algorithm would work:

prk = HKDF-EXTRACT(salt, master_key)

Key1 = HKDF-EXPAND(prk, "info 1", digest_len)
Key2 = HKDF-EXPAND(prk, "info 2", digest_len)

This creates two keys that are generated from the master key, but given Key1, someone else wouldn't be able to generate Key2, as they don't know the master key.


How to define a FHE scheme whose plaintext space is infinite using boolean circuits?

I believe we have a more fundamental problem with we try to handle arbitrary length plaintexts.

Suppose that we have any encryption scheme $\mathbb{B}$ (not necessarily FHE, or even asymmetric) that tries to handle arbitrary length plaintexts.  Suppose also we also had a $\mathbb{B}$ encrypted ciphertext, which we can see is 1000 bits long.  We don't know the key, however, we can deduce that there are, at most $2^{1000}$ possible plaintexts that this might correspond to.

What does that deduction give us (given that we don't know the value of any of those $2^{1000}$ plaintexts?  Well, it'd be a pretty good guess that the plaintext isn't more than 1 Gigabyte long, even if the decryption process could potentially have a plaintext which is longer than the ciphertext.

Because of this, there is a limit to the amount of length hiding we can do, if we try to handle unbounded plaintexts.


Homomorphic Encryption and the Approximate GCD Problem Confusion

The reference linked states in its Notation section (page vii):

  $a\bmod p\;\;$ Denotes reducing $a$ modulo $p$ into the interval $(-p/2, p/2]$

Thus the definition of $\bmod$ used is the non-standard
$$(a\bmod p)=r\;\iff\;p\text{ divides }a-r\;\text{ and }\;-p<2r\le p$$

This can be viewed as the offset of $a$ from the nearest multiple of $p$ (with nearest selecting the lower as a tie-breaker), as suggested by a comment.

This can be programmed as r = ((a + (p-1)/2) % p) - (p-1)/2, making sure that

things are evaluated as signed integers (which in C can require some explicit casting for unsigned p);
the addition of (p-1)/2 does not cause overflow.


Average/approximate difference in value between valid consecutive $x$ coordinates in ECC?

Here's a justification for the estimate in CodesinChaos' comment.

Helmut Hasse proved in his 1936 series of papers "Zur Theorie der abstrakten elliptischen Funktionenkörper" that any elliptic curve $E$ over a finite field $\mathbb F_q$ satisfies the inequality
$$ \lvert q+1-\#E(\mathbb F_q)\rvert\leq2\sqrt q \text, $$

that is, the number of points is (very) roughly approximated by $q+1$. Since there are almost always (except when $x^3+ax+b=0$) precisely zero or two points corresponding to a given $x$ coordinate, this implies that the points on the curve assume about $(q+1)/2$ different $x$ coordinates. Therefore, the average distance between two "consecutive" (strictly speaking, this is not meaningful without a partial order on $\mathbb F_q$) valid $x$ coordinates is close to $\frac{q+1}{(q+1)/2}=2$.


Do random oracles are called even by honest users in the PAK protocol [BMK00]?

In the real-world protocol there is no simulator. There is a real-world adversary and it has access to the exact same (random) oracle as the honest parties. The simulator controls the random oracle in the ideal-model simulation only.
This is not required by the definition, but is the way that things work. Essentially, the simulator plays the role of the honest parties to the real adversary. Of course, it does this without knowing the honest parties' inputs and outputs.
This depends on what information the ideal adversary/simulator gets about the status of the honest parties. If the ideal functionality provides the status to the ideal adversary, then it knows it; otherwise, not.
The natural way to define the ideal functionality is for the parties to send their password to the ideal functionality and if they match then a random session key is provided to them both. In order to simulate a real execution in the ideal model, the simulator must therefore send the ideal functionality the passwords that the adversary (implicitly) uses.
You can define "game based definitions" not via an ideal functionality. In any case, proving the security of password protocols without any setup (like a CRS or PKI) is very difficult. Proving without a random oracle is even harder.

Overall, it seems that you could benefit from taking a step back from PAKE and looking at how ideal/real simulation proofs work. Here is an answer that I wrote that tries to give a bit of an explanation. However, you really need to read some more basic papers. (PAKE is hard place to start.)


Is it easy to crack a hashed phone number?

No, it is not a good idea to hash phone numbers. There are only a limited number of phone numbers, so it is pretty easy for an adversary to try and hash all of them. Then you can simply compare the hash of each with the stored hash. Generally you don't have to deal with all telephone numbers, only a subsection of phone numbers anyway (for a specific country or other group that is logically distinct).
You could use a slow password hash with salt and work factor, but that's only going to mean that time time required is multiplied by a large, constant value. It won't change the order of operations. If the subset is small enough it may not deter an adversary to perform all necessary calculations.
In this case you will probably need to encrypt the phone numbers instead. Or use a keyed hash such as HMAC. For both options you need to perform key management on the secret key though; it's not as easy as just hashing the number.


Why is an Encrypt-and-MAC scheme with deterministic MAC not IND-CPA secure?

I'm a little bit confused by your notation (what's $1^n$ supposed to mean? based on context, it looks like a key or a passphrase, but I've never seen that notation before), but the exercise itself seems to just amount to proving that an Encrypt-and-MAC scheme, using a deterministic MAC of the plaintext which is sent in plain, cannot be IND-CPA secure.

To prove that, keep in mind that there's nothing in the IND-CPA definition saying that the adversary cannot use the encryption oracle on the challenge messages.  Since the MAC is deterministic and sent in plain, the adversary can just compare the MAC parts of two encrypted messages to determine (with very high probability) whether they encode the same plaintext.


Is non-adaptive CPA strictly weaker than standard CPA security?

Edit. Except for CPA1 (defined by the OP), "CPA" below refers to multi-challenge CPA, where the adversary always submits two messages and receive the encryption of either the first or the second messages. It's equivalent to the usual one-challenge multi-query CPA.

CPA1 is equivalent to CPA. Consider real-or-random CPA (RRCPA), where the adversary adaptively chooses messages and receive either encryptions of the chosen messages or encryptions of random messages. It is routine to see that CPA is tightly equivalent to RRCPA. Lastly, RRCPA reduces to CPA1 via a standard hybrid argument, as the encryption of random messages can be queried before the challenge. The proof is not tight, though.

In more detail, let $\mathcal{A}$ be an adversary against RRCPA, we construct $\mathcal{B}$ against CPA1. Let $Q$ be a polynomial that upper-bounds the number of challenges $\mathcal{A}$ makes. $\mathcal{B}$ does the following:

Sample $i\gets[Q]$ and launch $\mathcal{A}$.
For the first ${(i-1)}$ challenges $m_1,\dots,m_{i-1}$ that $\mathcal{A}$ makes, query the encryption oracle to obtain the correct ciphertexts $c_1,\dots,c_{i-1}$ and use them as the response to $\mathcal{A}$.
Sample ${Q-(i-1)}$ random messages $m_i',\dots,m_Q'$ and query the encryption oracle to get the ciphertexts $c_{i+1},\dots,c_Q$ (without $c_i$).
When $\mathcal{A}$ makes the $i$th challenge $m_i$, submit $m_i,m_i'$ to the CPA1 challenger and gets back a ciphertext $c_i$. Use it to respond to $\mathcal{A}$.
For the other challenges from $\mathcal{A}$, use $c_{i+1},\dots,c_Q$ as the responses.

Let $H_i$ be the hybrid of RRCPA such that the first $i$ challenges are real and the other are random, and $G_b$ the CPA1 experiments.
Clearly, $\mathcal{A}$ is in $H_{i-1+b}$ if $\mathcal{B}$ is in $G_b$ and chooses $i$ at the beginning.
Averaging over $i$ shows that the advantage of $\mathcal{B}$ is $1/Q$ that of $\mathcal{A}$.
This finishes the reduction.


Is quantum randomness different to conventional randomness?

Statistically, yes, random is random (read: entropy).  It's also worth stating that you can really only approximate how random something is based on samples.  This means that you can't measure randomness explicitly, but you can make approximations based on expected outputs compared to conditional probabilities, etc.

Quantum computing does have random properties which are a fundamental part of quantum mechanics, but a strict requirement of any quantum gate is that they are invertible.  This means that for any quantum gate, and any quantum algorithm, you must be able to reverse any transformation (page 18).  This is achieved through the use of error-correction, as well as the design of algorithms used in quantum computing.

There is a subtle difference between the randomness associated with quantum computing, and the randomness generated by quantum properties.  I've submitted an answer to the question you linked, and the reason I made it clear that you don't need a quantum computer to generate randomness using quantum mechanics is because it's a different use of quantum mechanics.

Quantum randomness can be generated by some cameras already built into several models of smart phones.  This is possible through measurement on the few photon level.  Essentially you use a camera to measure a few photons, and then translate that into a seed for a PRNG.  This works because when light is measured as a photon, the distribution follows the double-slit experiment for individual particles.  If you were to measure light as a wave, the distribution is fundamentally different.

The main upshot is that randomness is randomness.  For cryptographic purposes, this obviously isn't enough of an answer.  We need ways to measure randomness, and so we use tools to approximate how random an output is.  This isn't measuring randomness itself, but the approximation helps give information on whether we should classify something as an RNG or PRNG.

So while there's a difference between calling rand in C++, or /dev/urandom in Unix systems, in terms of a PRNG generated classically compared to quantum randomness the difference may potentially be less pronounced.  Even if there is a sharp distinction between a classical PRNG and quantum randomness, you're right that for the foreseeable future both would most likely rely on classical randomness extractors.


extract ciphertext from encrypted SMIME file

the following command do what I want :

openssl smime -in msg -pk7out -out msg.pk7
openssl asn1parse -in msg.pk7


Faster alternatives to RSA trapdoor permutation

encrypt with the private key, and decrypt with the public key

That statement, and the very name privateEncrypt, is incompatible with standard terminology: "public" means known to all and opposes to "private"; and "encrypt" implies transforming some information $X$ into $Y$ in a way such that if $Y$ becomes public, $X$ does not.
Per standard terminology we sign with total message recovery, and recover the message. The term "total message recovery" designates a signature scheme where all the data is conveyed in the signature itself. This is how RSA signature was introduced, and the term is used in the ISO/IEC 9796 series of standards.

RSA in pure mode is extremely slow

Whatever the name and the variants, RSASign is indeed rather slow, and usually size-expanding. This can be mitigated, but some slowness will remain.
On the other hand, RSARecover is relatively fast, and Integer Factorization (based) Crypto (the IFC family, which best known member is RSA) is by far the fastest asymmetric crypto around for the task. In the application, if information retrieval quantitatively dominates, that might be an advantage.

Are there any other similar cryptographic functions we can use for this case, which are superior to the RSA scheme in speed and size?

Outside of systems closely related to RSA in that they belong to IFC, none that I have met since I started watching public key crypto¹.
Let's see how we can mitigate the issues:

RSASign can be made faster by

Using a right-sized public modulus (and correspondingly splitting the information into blocks²). Currently the accepted minimum for signature is $n=2048$-bit public modulus, and all things being equal the signature cost per byte grows only slightly slower than $n^2$.
Using the Chinese Remainder Theorem method. Every speed-optimized implementation of RSA signature does that, because it reduces computational cost by a factor typically over three. Some implementations also use it to spread most of the workload on several CPU cores, further reducing encryption time. Implementations of RSA encryption can not use that method, because it requires the private key.
Using a public modulus product of $k>2$ primes. That's known as multiprime RSA. All things being equal, execution time is roughly halved when we go to 3 primes, divided by more than three with 4 primes. If high security assurance is not paramount, it would be reasonable to consider $(n,k)=(2048,4)$.
Using highly optimized implementation. Shay Gueron and Vlad Krasnov's Speed Records for Multi-prime RSA Using AVX2 Architectures (in CIT 2016) report $(1.9,\,1.0,\,0.6)$ million Skylake CPU cycles/signature for $n=2048$, $k=(2,\,3,\,4)$, translating to $(0.4,\,0.7,\,1.3)$MByte/s/core @3GHz (neglecting time and size overhead due to padding). And then dedicated hardware is a possibility.

Size overhead depends on padding:

If we want to use something standardized and cut no corner, we can use ISO/IEC 9796-2 scheme 2 and a random nonce as wide as the hash size. The size overhead is $3h/2+16$ bits out of $n$, that is 206 bytes stored in a 256-byte cryptogram with SHA-256 and $n=2048$ (+24.3% overhead). Even if the data actually stored was entirely constant, it's unlikely two stored blocks would get identical until there are $2^{64}$, that is >3ZiB effective data.
If we accept something custom, a deterministic transformation (which allows to store a single copy of identical data blocks), and dropping cryptographic signing, the size overhead can be one bit per block (just apply a reversible transformation to the data followed by textbook RSA signature, that is textbook RSA encryption), or even zero (apply textbook RSA only to values lower than the public modulus after the reversible transformation, and generate the public/private key pair so that the high-order 64 bits of the public modulus are all-one).

RSARecover can be made faster by

Using a low public exponent, such as $e=3$. This allows the exponentiation to use one modular squaring and one modular multiplication, rather than sixteen and one for the most common $e=65537$. Except for possible regulatory requirements, $e=3$ is fine. There's a saving by a factor of roughly 8, and now RSARecover typically is hundreds of times faster than RSASign (when $k=2$). We are talking some gigabit/s on a standard PC.
Using $e=2$, which allows a further saving by some factor like two. The name changes from RSA to Rabin signature, there are a few minor complications, but that remains fully academic and covered in ISO/IEC 9796-2.

¹ That was in 1980 during one of these strikes France is renewed for. My math (Spé) teacher dropped the official program and showed her class RSA, based on Martin Gardner's article.
² As pointed in comment, if we only do that splitting, we loose overall message integrity assurance (an adversary can swap signed blocks). I don't see that such assurance is indispensable in the context. But if we require it, we can prepend a fixed-width block number to a block's payload, at the expense of increased size overhead. A note suggests "Using CBC rather than ECB" but that does not seem to work unless the data signed is somewhat redundant.


How to make Fernet encryption produce the same ciphertext for the same data

It sounds like what you want is a deterministic authenticated cipher, or DAE, deterministic authenticated encryption, which has the property that an adversary can always tell when you have repeated messages, of course.

As far as I can tell, Fernet does not support any DAE.  Popular choices for DAE include SIV-type schemes like AES-SIV.  But you should have a good reason for using DAE first!  Most applications don't need it.


Security concern about reducing hash value using modulo operation

Let's assume that $h(x)$ returns a value between 0 and $k$ (exclusive). If $h$ is a good hash, this distribution will be uniform.

Computing $h(x) \mod n$ will introduce a bias if $k$ is not a multiple of $n$. This bias is significant if $k$ is only slightly smaller than $n$ and decreases as $k/n$ grows. How large $k/n$ needs to be depends on what level of bias is acceptable to you.

The DSA algorithm needs to generate an unbiased number. NIST recommends (FIPS 186-4 in appendix B.2.1) that you should use at least 64 extra bits, i.e. that $k/n > 2^{64}$. This is a reasonable since it means that the bias only becomes detectable if the attacker sees around $2^{64}$ samples. I doubt that you'll generate that much data.

So if you take a cryptographic hash of at least 128 bits, interpret it as a big integer and take it modulo a number smaller than $2^{64}$ the resulting bias will be negligible.

If your application is less sensitive to bias, it might be acceptable to reduce a 64 bit number modulo $n$. This avoids the need for a big integer library and is the approach I took for my random string generator.

Another approach to avoiding bias is rejecting values between $\geq k - k \mod n$. But this means that you need to consume a potentially unlimited amount of random values, so it's probably not the best fit for your application.


Can I construct a zero-knowledge proof that I solved a Project Euler problem?

Verifiable to someone who already has the correct answer

Verifiable to whom?  Someone else with the correct answer?  Then you may be able to get away with a salted bcrypt hash; e.g., you can easily say make a cryptographically strong one-way hash of an answer:

>>> import bcrypt #using py-bcrypt python module
>>> hashed_answer = bcrypt.hashpw('[secret answer to problem 283]', bcrypt.gensalt(log_rounds=16))
$2a$16$fPitqoBxyVJbxGsWCecweu2Wfrz8KhgnargfA9F//c0ZJ6E4ONwHK
# the above hash was generated using the actual answer to problem 283

Then if you have the answer you can check that I also have the answer with:

>>> hashed_answer == bcrypt.hashpw('[secret answer to problem 283]', hashed_answer)
True

You could also use an online javascript bcrypt calculator, where you type the answer as the password, use my hash as the salt $2a$16$fPitqoBxyVJbxGsWCecweu2Wfrz8KhgnargfA9F//c0ZJ6E4ONwHK, and then press run and check that the hash with your answer equals my hash.

You should make sure that the answer isn't brute-forceable by using a suitably strong number of rounds.  (In this case where the answer is a base-10 number between 16-20 digits long and it takes my cpu about 4 seconds to generate a hash to brute force the answer would take a single cpu about a billion years to brute-force).

Granted people who don't have the answer to 283 cannot verify that you have an answer.

Also without solving your five person birthday problem; by the pigeonhole principle its known that the answer is less than (365)*4+1 ~ 1461; so you must use a very strong hash or add more information; e.g., one that takes days to calculate to make bruteforcing impractical.

Verifiable to someone who does not know the answer

Now if you want to have someone who doesn't know the answer check that you know an answer, you'll have to appeal to a trusted authority.  This could be projecteuler.net where a list of users who have solved any individual problem is available.  Users could authenticate their answer is correct with project euler (either via checking a hashed answer or directly submitting the plaintext answer to the server) and then project euler could let the world know.

As for identifying that minopret on project euler to their real life identity, project euler could decide to do this in a variety of ways.  One scheme would have people type in an email address to a form and then you see the problems that that user has solved (you don't want to just list email addresses to mitigate potential spam).  So if you were applying to a job and wanted to demonstrate your project euler problem solving skills, you tell your employer the email you use on PE and they could check that you have control of your email address and then see the number of answers you have done correctly.

Aside: I solved your 5-birthday problem (was at work so couldn't solve earlier).  As its a small integer, it probably wouldn't be that difficult to brute force even with an unreasonably large hash, so I would suggest requiring a less brute-forceable answer.  Something like first find the least number of people (N) where the probablity of having at least one set of 5 (or more) people with the same birthday is greater than 0.95 and then give the sum of that number + the probability rounded to six decimal digits.  For example, if this was the standard birthday problem (two people with the same birthday to more than 0.95) the answer would be 47 + 0.954774 = 47.954774.  Then my bcrypt hashed answer to the at least 5 birthday problem at greater than 95% confidence would be '$2a$20$ejlHCtR/G.19k9TCTPtsOOkZm8J9kbvwm6zrcJ0q9NNwcun1eOpoS' (with an ~ minute long hash), which you could check with:

'$2a$20$ejlHCtR/G.19k9TCTPtsOOkZm8J9kbvwm6zrcJ0q9NNwcun1eOpoS'==bcrypt.hashpw('____.95____', '$2a$20$ejlHCtR/G.19k9TCTPtsOOkZm8J9kbvwm6zrcJ0q9NNwcun1eOpoS')

where you replace '____.95____' with the actual number (no leading zeros/spaces).


If we presume that the two encryption methods are secure by themselves, then having double encryption will not introduce any weaknesses. Sure, the security of the encryption may be smaller than key size of the keys combined, but if you use two different keys then the security should not be smaller than the key strength of the smallest key used.

Of course, if the same symmetric key (and IV) are used then you could get into trouble as for some operations the encryption and decryption are identical. This is, for instance, the case for stream ciphers and counter mode encryption. However, if the same symmetric key is used for two different purposes then your key management is the issue rather than the methods of encryption. I presume though that key reuse is not performed as the SAN admin should not possess the TDE decryption key, according to the info in your question.

In short, as long as you don't presume that performing additional encryption makes the initial encryption stronger, then you should be OK. The double encryption problem as you state is mainly concerned about the fact that the key strength may not double even if you encrypt with two separate keys. But as far as I see, doubling the key strength is not your goal in the first place.


Security of Diffie-Hellman when one party has a flawed RNG (compared to TOFU)

There are a few things missing from this question.

First of all, TOFU (trust-on-first-use) is not a scheme and cannot therefore be compared with DH. TOFU is more a property of a protocol than anything else.

Second, you say you would use "some kind of authentication". This is what TOFU "solves", establishing trust without which it is impossible to authenticate. You cannot just skip over that part of the protocol if you want to compare schemes.

Third, I don't see any  comparison between active attacks and passive attacks. If an attacker can create the private key then passive (eavesdropping) attacks would be possible. It is not clear if passive attacks are possible for TOFU as it is not a protocol or scheme in itself. That said, I think it is tricky to think of a scheme where a broken RNG isn't an issue in itself.

Finally, for your own scheme you say that you "generate random nonces" but it is unclear how these nonces are shared or what they would add if they would be shared publicly.


Why should I use an Initialization Vector (IV) when I have unique keys?

Caveat: as very rightly pointed in that other answer, using a fixed/no IV does make some attacks less difficult. I wish the following answer would have been less affirmative. I have accordingly made adjustments in italic.

There's no imperious need for an IV when unique keys are used. Given that a 256-bit key cipher is used, what's proposed is safe.

When each key is used only to encipher a single message, it is reasonably safe (from a confidentiality standpoint) to use null IV for all messages. That's customary, for all common modes requiring an IV. It avoids the need to generate an IV, and transmit it, and (in the case of CBC) perform a XOR of the first block with it.

Why? Intuitively: random (or otherwise appropriate) IVs are primarily here to make it unlikely that the same input/output pairs (at the block cipher level, and using the same key) ever occurs during the encryption of two distinct messages, even when one bears some relation to the other (including but far from limited to: starting with the same first block). When there is a single message, that need disappears. More formally, the basic (non-quantitative) proof of security of CBC (and other secure modes) holds without IV when there is a single message per key.

On the other hand, by not using a random IV, in some setups, one gives the adversary the same known plaintext block enciphered with different keys (in CBC, that would be the case if the first block of each plaintext is a known constant); this reduces the number of trial encryptions for exhaustive key search by a factor (at worse) equal to the number $n$ of keys. This is bad, but there are mitigating factors:

The attack only find one of the $n$ keys, and the corresponding plaintext; when theses are independent (e.g. different photos stored enciphered under different keys), the expected number of trial encryptions to revover a certain plaintext is the same as for random IV.
The attack requires searching the result of each trial encryption of the known plaintext among $n$ values. The investment and operating cost for the non-trivial devices that store the ciphertexts blocks and search among them at high rate grows with $n$ (at least the memory capacity is proportional to $n$).

Note: The single message per key setup leaves the total message length per key limit unchanged for CBC, PCBC, CFB: that's $2^{(b+1-k)/2}$ blocks for less than $2^{-k}$ odds of collision (implying some level of insecurity) using a $b$-bit block cipher. That limit is dramatically raised for OFB and CTR in the single message per key setup.


With wrong IV at receiver side, the CFB in better than OFB?

Yes, it is correct. Just follow the bits in the decryption pictures on the Wikipedia page about modes of operation. Modes of operation don't have to have a meaning compared to other modes of operation. I don't see CFB or OFB used too much anymore. OFB with partial feedback has been shown to be less secure, so that shouldn't be used anymore.

Currently the cryptographic community doesn't seem to care too much about error propagation anymore. Instead, everybody tries to make sure that an authentication tag over the IV and ciphertext is present. If that is the case then errors can be detected and the message can be discarded. One of the reasons is that it is often possible to alter the ciphertext in transport protocols (e.g. when open WiFi hotspots are used), and few protocols handle partially correct data that well.

So you are much better off looking at authenticated modes such as GCM and EAX modes of operation.


Max size for exponent and modulus in RSA and for y, p, q, g in DSS

For DSA/DSS the key sizes are restricted by FIPS 186-4, so nothing will ever exceed 4096-bit.

For RSA, anecdotally the largest size anyone supports is 16k-bit, so a Modulus value expressed in 2049 bytes (2048 plus one padding byte).


What is the smallest last value of sequence of integers from 1, where there is a collision in md5?

MD5 has a 128-bit output, so it's expected that the first collision is around $2^{64}$. This is because of the Birthday-Problem in probability theory.

So you should be safe to take orders up to $$2^{64} = 18,446,744,073,709,551,616$$

But that shouldn't be a problem for you, because even though this number might not seem like a large number it actually is huge:

An Example:

If every human ($ \approx 7,000,000,000$ people) would place an order every second, then it would take $${2^{64} \over 7,000,000,000 * 3600 * 24 * 365} \approx 83.5$$ years.

So you can be extremely sure that you won't have a collision of hashed order-numbers.


Possible to check if $a \in \mathrm{QR}_n$?

It is possible to check $a \in \mathrm{QR}_p \text{ iff } a^{(p-1)/2} \equiv 1\ (\bmod\ p)$ if $p$ is a prime.

Yes, you have already written down the check, which is known as Euler's criterion.

  $n$ is a large RSA modulus. Is it also possible to check if $a \in \mathrm{QR}_n$ if the factorization of $n$ is unknown?

You can use the Jacobi symbol if the factorization is unknown to find out if $a\in \mathrm{QNR}_n$, i.e., if the Jacobi symbol is $-1$.

But if the Jacobi symbol yields $+1$, then you can either have a quadratic residue or a pseudosquare, i.e., a quadratic non-residue yielding Jacobi symbol $+1$.

Distinguishing pseudosquares from quadratic residues modulo an RSA modulus if the factorization is unknown is known as the quadratic residuosity problem which is believed to be a hard problem and is the basis for some cryptographic constructions such as the Goldwasser-Micali encryption scheme.

For generic algorithms this problem can be shown to be equivalent to factoring.


Selective and existential unforgability of signature schemes

1) In the selective unforgeability game (often also denoted universal unforgeability), the adversary is given the public key and a target message for which it needs to produce a forgery (instead of giving the adversary only the public key and letting the adversary choose the target message).

2) No, any scheme that is EUF-CMA is also SUF-CMA (this is easy to show; build an EUF-CMA adversary from any SUF-CMA one by simply running the SUF one on an arbitrarily chosen message).


How to calculate a multiple-character checksum for authentication using a tabula recta?

I just realized that you could use a 676x676 table with 2-character entries.  But hopefully there is an easier way.


Without Mix Columns, every byte of the ciphertext would not depend on every byte of the plaintext, but only on the one byte at the same position. This would fully break AES, because we don't have an avalanche effect on the whole text anymore.

Without the Row shifting, every column of plaintext would only affect the same column of the ciphertext. This would break AES, too.

The question "Consequences of AES without any one of its operations" has some similarities with your question.


Are there any implications on security if the AES-CMAC algorithm is modified in this way?

There is no security implications by modifying $\text{AES-CMAC}$ by replacing the $\text{AES}$ block cipher component with $\text{AES}^{-1}$.  Both are equally strong block ciphers; if $\text{AES}^{-1}\text{-CMAC}$ were found to have a weakness, that would imply that $\text{AES}^{-1}$ could be distinguished from a random permutation, which would imply that $AES$ could be distinguished from a random permutation, which could imply that $\text{AES-CMAC}$ might not be as strong as we hoped.

BTW: CMAC assumes that the device has a secret key; if someone else learned that secret key, they could generate their own images (which would validate just as well).  Do you have such an unlearnable secret key?


Need an introduction to SPKI (or "SPKI for dummies")

Short version: SPKI links not only names, but authorizations to keys. Also, it uses a better syntax (S-expressions) than X.509 certificates.

Long version:

What problem does it solve?

Both the traditional CA-based public-key infrastructure (PKI) and PGP's web of trust (and other similar systems) do mainly one thing: Linking names to public keys.

The idea behind SPKI is detailed in RFC 2692. It explains that, while this might be sufficient in the 1970's, when the relevant communities were small and one usually knew the person identified by a name before starting to use the key for communicating, it is not sufficient anymore for the Internet of the late 1990's (and even less later).

One reason is that names alone are not a globally unique identifier. (While my name seems to be quite unique in the WWW today, there are people which are less fortunate.)

More important, though, is what we are actually using the keys for: To access some resource (or to provide it).

Thus, we actually need certificates like these (examples from the RFC):

  I need a certificate to give me permission to write electronic
    checks.
  My bank would need a certificate, proving to others that it is
    a bank capable of cashing electronic checks and permitted to
    give permission to people to write electronic checks.

E.g. we need a certificate linking authorizations to keys. (I.e. a certificate that says the holder of the private key belonging to the public key X has the right Y - for example, "access this SSH server".)

SPKI does this. RFC 2693 - Theory of SPKI details the theory. The actual specification (i.e. the data formats) seem to have never reached the RFC state (there are some Internet drafts which expired in 1998).

What rights (authorizations) there are possible is left to the application (i.e. whoever actually has control over the resource). Its owner indicates an access control list, i.e. which keys are (with which authorizations) the roots of any certificate graph leading to the ones which actually have access.

Authorizations can be transferred between keys (if the delegate-bit is set on the first key) by issuing a certificate.

Any key holder can issue any certificate to any other key (or even to ones own key), i.e. we have a web of certificates between keys. But whoever evaluates the certificates will decide which certificates are acceptable for which use (depending on which other key holder signed these keys).

The traditional "name-key" linking certificates are still supported, this way the conventional PGP Web of Trust or the X.509 CA hierarchy can be a part of this infrastructure, and their certificates can be transformed into the same internal representation like SPKI certificates.

Syntax

To represent the keys, names and authorizations used in the certificates, SPKI uses S-expressions. (You might know these from Lisp - nested lists written in parenthesis, containing byte strings.) Here is an example of a name:

  (name (hash sha1 |TLCgPLFlGTzgUbcaYLW8kGTEnUk=|) jim therese)

For transmission and signing these are converted into a canonical form (length-prefixed literal strings).

These S-expressions are easier to parse than X.509 certificates.

Certificate revocation

A problem identified in the PKI was that is is not always totally deterministic whether a certificate would is revoked or not, depending on whether the evaluating client got the right CRL or not.

SPKI defines a way that makes this deterministic:

certificates contain references to CRLs which can revoke them
certificates contain the key that must be used to sign the CRLs (which must not necessarily be the same key that issued the certificate)
CRLs must have a validity date span (and these must be non-overlapping)


Inversion Free Direct Conversion between Twisted Edwards (X,Y,Z) and Montgomery (X,Z)

The conversion formula from twisted Edwards to Montgomery form is:

$$x_{mont} = \frac{X_{mont}}{Z_{mont}}= \frac{1+y_{ed}}{1-y_{ed}} = \frac{1+\frac{Y_{ed}}{Z_{ed}}}{1-\frac{Y_{ed}}{Z_{ed}}} = \frac{Z_{ed}+Y_{ed}}{Z_{ed}-Y_{ed}}$$

If you want the affine $x_{mont}$, you need to compute the inversion. But if you just need $X_{mont}$ and $Z_{mont}$ you can skip the inversion, since the nominator is X and the denominator Z.

$$X_{mont} = Z_{ed}+Y_{ed}$$
$$Z_{mont} = Z_{ed}-Y_{ed}$$

Some additional notes:

If you use $Z \neq 1$ as input for the Montgomery ladder, this will increase the cost of this scalar multiplication by more than the cost of an initial inversion (about 10% of the ladder cost).
If you really need to minimize the cost of inversions, you might want to use batch inversions, which can compute the inverse of multiple values, available at the same time, with a cost only slightly higher than a single inversion.
At the end of a scalar multiplication you need to compute an inversion, no matter which form you use, since you want an affine output. In that case you can convert between forms for free, since you can merge the inversions into a single one.
When using the cheap X,Z Montgomery ladder and convert back to twisted Edwards, you get $Y$ and $Z$. You can recover $|X|$ from that using the curve equation (essentially a point decompression, cost similar to a field inversion), but you don't know the sign of $X$.
Variable base-point twisted Edwards isn't much more expensive than Montgomery if you can afford the memory for the lookup table.


Can AES decryption be used as encryption?

First, I'll assume we're talking about encrypting/decrypting exactly 128 bits of data, i.e. the block size of AES. Otherwise, you'll need to specify a mode of operation — and if your data's length isn't a multiple of the block size, well, that'll be more difficult to deal with. So, I'll assume we're working with a single block. (If you are using a mode of operation, the below doesn't apply; see the other answer(s) for more details.)

AES models a theoretical construction called a pseudorandom permutation (PRP). Essentially, this means that if we set up a game where we give a polynomial-time-limited adversary access to either (1) an oracle computing a truly-random permutation or (2) an oracle computing the pseudorandom permutation (with a randomly chosen key), the adversary cannot determine which they were given access to with any non-negligible advantage. (They can always guess one or the other, so they have a 50% chance of guessing right; what the PRP security requirement states is that they can't get any non-negligible chance over that 50%.)

There is a stronger notion of a PRP called a strong pseudorandom permutation. In the strong PRP game, the adversary is given access not just to an oracle computing the permutation in question: they're also given access to the inverse of the permutation. In terms of block ciphers, this means that instead of getting access to just an encryption oracle, they would also get access to a decryption oracle.

As far as we know, AES is indeed a strong PRP, so for single blocks, swapping the encryption and decryption functions should be fine. You could then use this in other block cipher modes of operation, for instance.


Well,

You're working in the multiplicative group.
There is a theorem (which is proven by group axioms), that the inverse element is unique ($d$ is inverse to $e$).
When you say $d = 160 \cdot k + 23$ for every $k$ from $Z$, you actually should mean that in the context mod $160$ then your $d \cdot k$ for any $k$ is actually the same element.

I think the mindtrick here is that:

You claim: $d = 160 \cdot k + 23$ for every $k$ in Z; oh, there is a lot of such elements!
NO. You're in the multiplicative group. You can write this element different ways. But it is still the same element.

You do not work with "numbers". You work with an element of multiplicative group. Which can be represented many ways (see your claim about $k$). But it's the same element. In the context of 'multiplicative group mod $160$, elements $23$ and $183$ are the same elements.

You can easily prove that $23 \bmod 160 = 183 \bmod 160$. So $183$ equals $23$ in group mod $160$. That means you can write on sheet of paper $183$ or $23$ or whatever $160 \cdot k + 23$ you like, and you will be talking about the same element, which is unique.

The key is therefore also unique - your key is an element of a multiplicative group, which can be written in many ways ($160 \cdot k + 23$, where $k$ is in $Z$)


Using AES-GCM (or AEAD ciphers in general) as a pure MAC without encryption

does it bring any benefits?

Yes, it could. It is likely that e.g. GCM is sped up more than e.g. HMAC. GMAC - the underlying MAC - is using faster operations than HMAC as well, and GMAC is unlikely to be present as MAC in most runtimes. Besides that, it would also require a 128 bit block cipher, so you'd basically have everything you need for an AEAD cipher again.

  does it have any obvious disadvantages?

It could wrong-foot casual readers of the protocol or code. Suddenly they are presented with a cipher rather than a MAC, and that might lead to incorrect conclusions.

It may also well be that there is an additional overhead to take care of verifying a nonce and ciphertext. Although that's a constant overhead that is not related to message size, it may still be significant for small messages.

  does it have any security implications?

Depends on the MAC used and the MAC that it is compared against (and configuration, usage scenario etc.).

EAX mode is an AEAD cipher that uses CMAC for all MAC calculations. It is very likely to be as secure as using CMAC directly.

GMAC security on the other hand is more dependent on the size of the authentication tag compared to e.g. HMAC. It has a substantially lower limits for message count, message size, total message size compared to an algorithm such as HMAC configured with a SHA-2 hash.

Furthermore, a MAC as GMAC or CMAC is limited to 128 bits while e.g. HMAC can output 256 bits or 512 bits. Not that you're likely to ever need that amount of security for a MAC, but it can weigh in none-the-less.

Key reuse for two ciphers can negate all security and even lead to leaking the MAC key, something that is less likely an issue for a cipher + HMAC.


Key renewal when the sequence counter is only 32-bit

The standard rule is simple: Re-key whenever the sequence counter would (likely enough) repeat. For incrementing sequence counters this should be the case when they overflow.
If you're using AES-GCM and you were to pick the (96-bit) nonces randomly, re-keying after $2^{32}$ messages would be recommended. However given that you appear to use an actual counter and feed it into GCM's nonce input re-keying on wrap-around is good enough - which incidentally for 32-bit counters would also happen around $2^{32}$ messages.
If you used a 64-bit counter, the previous thought would extend somewhat and a re-key would be required at last every $2^{64}$ messages. However for reasons of the security proof you should really re-key after hitting $\sigma+q=2^{48}$ with $q$ being the number of nonces encrypted and $\sigma$ being 1/16th of the total number of bytes encrypted while not encrypting more than 64GiB per nonce-key pair.


Building a stream-cipher out of a hash function?

As I understand the construction (and it isn't well written), it looks weak; it is likely to leak information given real plaintexts.

The reason that I say it isn't well written is that it's not stated what you use to exclusive-or the plaintext bytes to generate the ciphertext-bytes; is it the hash you generated in step 2, or is it the "most recent hash" (the one in step 2 for the first iteration, or the one is step 4 for the next -- and step 5 really should be "goto step 3").

Assuming that you meant the latter, well, this appears to be 'Plaintext Feedback Mode':

In step 3, "the original bytes are buffered in $X'$"; that is, $X'$ is set to a segment of plaintext bytes.
In step 4, you construct the $H_1 = hash(S | X' )$, where $S$ is a secret key (constant for a specific stream), and $X'$ are plaintext bytes you stored in step 3.
In step 3, you compute $Ciphertext = Plaintext \oplus Trim(H_1)$. where $Trim$ is the first $X$ bits of $H_1$

The problem here is that real plaintext often have repeats; it is not unusual to see occurances of the exact same 16 characters repeated -- this is precisely why ECB mode is considered insecure.  However, when this happens for your construction, then $X'$ will be repeated, and so will $H_1$; the 16 bytes immediately following that will have the exact same exclusive-or (and this can be detected and exploited).

The obvious fix would be to change this into Ciphertext Feedback Mode; all you would need to do is set $X'$ to the ciphertext bytes, not the original plaintext bytes.

This still isn't a great encryption method (it's slow, and needs an integrity check to be secure); however if all you have is a hash function, it could be made to work.


Practical multivariate quadratic FHE – how does it compare to other FHEs?

I've spoken to the CEO a couple times. They've contracted some prominent French cryptographers to vet their cryptosystem, but no security analysis or whitepaper has been released.

Their KFHE scheme is different than previous schemes because it uses a different hardness assumption that leads to better performance and smaller keys. Previous FHE schemes used hardness assumptions based on ideal lattices, but their scheme uses a different assumption based on the hardness of solving a system of quadratic equations in many variables. Whether their construction truly is a practical general-purpose FHE scheme is not clear, since perf numbers for general circuits are not available (as far as I know).

Schemes based on solving systems of multivariate quadratic equations have some nice properties, including the aforementioned performance benefits as well as conjectured resistance to quantum attacks, but have proven extremely difficult to get right. Many schemes based on these assumptions have been severely broken. However, there exist cryptosystems from this family that are widely believed to be secure.

The homomorphic properties of their scheme are used to build a kind of multi-user searchable encryption in their main product, Kodex. A user allows other users to search on their documents by homomorphically sharing document search keys. I don't know all the details, but my guess is this specific 'share' operation can be done efficiently because they avoid evaluating a circuit and just do stuff directly.

As with all shiny new things in cryptography, caution is called for. Editorializing a bit, I see little reason to believe this is snake oil. [Indeed, if they were only looking for a rubber stamp from Faugere and Perret it seems like something would have been made public already.] However, perfectly honest and forthright people have built many, many broken cryptosystems, so I recommend taking any claims with a moderately-sized grain of salt until given reason to do otherwise.


Discrete logarithm can be hard in Paillier group. One case for example is when $p$ and $q$ are safe primes, i.e. $p=2p'+1$ and $q=2q'+1$ where $p',q'$ are themselves prime.

You can find more information about the critieria in this paper (and from its references): On the Portability of Generalized Schnorr Proofs, by Camenisch et al, Eurocrypt 2009


Prime numbers of the form $(2^k)p+1$, for a given prime $p$

There is numerical evidence that for the vast majority of primes $p$, there exists $k$ making $q=2^k\,p+1$ prime. See first exceptions in A137715.

The only practical way I see to find which $(p,k)$ make $q=2^k\,p+1$ prime in the question's context is testing $q$ for primality using a fast test. As noted in the other answer, sieving for small primes can be shared across multiple $k$.

An overly crude approximation of the probability that $q=2^k\,p+1$ is prime is that probability for an integer of same magnitude divisible by neither $2$ nor prime $p$, that is for $p>2$ and by the Prime Number Theorem roughly $\displaystyle\frac{2-2/p}{\ln(q)}$, which we can approximate as $\displaystyle\frac2{\ln(p)+k\ln(2)}$ for our large $p$. A numerical experiment shows that's in the right ballpark, but sizably too high.

A better analysis is that for random large prime $p$, and a small prime $r>2$, the quantity $p\bmod r$ is about uniformly distributed on $[1,r)$, thus $2^k\,p\bmod r$ also is, thus $q=2^k\,p+1$ is divisible by $r$ with probability $1/(r-1)$, rather than $1/r$ for a random integer. It thus contributes to reducing the probability to be prime by a factor $\frac{r-2}{r-1}$ rather than $\frac{r-1}r$. We can correct for that effect, yielding
$$\begin{align}
\Pr(2^k\,p+1\text{ is prime})&\approx\frac2{\ln(p)+k\ln(2)}\ \prod_{r\in\Bbb P,\ 2<r<\sqrt p}\frac{r\,(r-2)}{(r-1)^2}\\
&\approx\frac{2\,C_2}{\ln(p)+k\ln(2)}\ \text{ with }C_2=0.66016\ldots
\end{align}$$
since the product quickly converges to the twin prime constant $C_2$ (see A005597). That improved approximation is excellent for large $p$ as in the question.

We move to estimating the probability to find a prime $2^k\,p+1$ for a given $p$ and $k\in[k_0,k_1]$ with $k_0$ and $k_1$ close and commensurate with $\log_2(p)$.

As a crude approximation we can pretend that the probabilities to get a prime for one $k$ are independent of $k$, and approximate the probability that there is one prime $2^k\,p+1$ for $k\in[k_0,k_1]$ as the easily computed
$$1-\prod_{k=k_0}^{k_1}\left(1-\frac{2\,C_2}{\ln(p)+k\ln(2)}\right)$$

For $p\approx 2^{256}$, $k\in[248,264]$ that gives a probability $0.061403\ldots$, meaning we'd need to test about one in $16.286\ldots$ primes $p$ to find a suitable one¹.

This approximation could likely be improved by taking into account that the probabilities for $2^k\,p+1$ to be divisible by a small prime $r$ for a given $p$ are strongly dependent on $k$, since $2^k\bmod r$ is a cyclic function of $k$, and worse of period $(r-1)/s$ often with $s\ge2$ (e.g. for $r=7$).

¹ What I got experimentally is close: $\frac{3395526}{208621}=16.27\ldots$ and $\frac{2116707}{130242}=16.25\ldots$ (scanning primes $p$ starting from $\left\lceil\frac7{22}\,\pi\,2^{256}\right\rceil$ and $\left\lceil\frac{113}{355}\,\pi\,2^{256}\right\rceil$ ).


Would hashing a password twice prevent naive attacks?

We don't approach our security through obscurity, we live in a world that Kerckhoffs's Principles rules! We assume that everything is known by the attackers except the key/password is secret. Your modification only hardens the search a little; just one more hash!
Password hashing has gone a longs way and in modern password hashing, we want them

memory-hard so that massive GPU/ASIC searches are almost prohibited.
Non-Parallelizable so that the attacker cannot parallel even a single search due to the requirement of multiple threads for a single password hashing.
Many Iterations so that the attacker must need huge time for the calculation of a single password hash.

All of the above parameters can be adjustable ( depend on the password hashing algorithm) so that the system designers can fit them into their system, too. For example, having a huge iteration that takes longer than 1 second is not good from the user's perspective. 250K or 1M may be good depending on the server.
Don't fall into Schneier's Law on Security

Any person can invent a security system so clever that she or he can't think of how to break it.

Instead of designing your own, first understand the standard ones like Scrypt, PBKDF2, and the winner of the 2015's Password Hashing Competition; Argon2.


Is it Possible to Generate a Duplicate DH Session Key from 2 Pairs of DH Keys?

If you're doing Diffie–Hellman in a group $G$ written multiplicatively with identity element $e$, say $G = (\mathbb Z/p\mathbb Z)^\times$ for some standard large safe prime $p$ and $e = 1$, then Eve/Mallory can simply supply $e$ as their public key to both Alice and Bob.  Then the shared secret group element is $e^a = e = e^b$.

There is a way for Alice and Bob to thwart this, by simply checking whether the peer's public key is the identity element.  But it's usually pointless because Alice and Bob will normally authenticate the entire transcript of the session—this thwarts the attack anyway because they will authenticate $g^a$ and $g^b$ as their public keys, not $e$.


What is the meaning of "transcipher" (if such term exists)

It is a command of the german health card.
See here for the RSA version. There exists also  an ECC version for the generation 2 card. The specification is also on the www.gematik.de web site but its a bit tricky to find it.


ECC public keys are not random numbers.

They are generated through a scalar multiplication of a random scalar with a known/public point on the curve, called Generator.

The entropy lies entirely in the random scalar. Two public keys will collide if the random scalars collide.

When you say "256bit ECDSA  public key" you probably mean that your elliptic curve curve is defined over a finite field whose size is approximatively $2^{256}$. This would explain why you are mentioning a public key of 64 bytes in your question.

Now, in cryptographic secure elliptic curves, that size is closely related to the size of order of the generator, which is actually the size of your random scalar.

Therefore, without knowing the exact curve you are using I can't exactly answer the question. But approximatively the expected probability is: $\frac1{2^{256}}$

This has nothing to do with the encoding, so xoring the key over itself doesn't really make sense to me, or I didn't understand it.


1) Fill remaining of last block with nulls.

2) No, you can use same key for more messages, but not the same as encryption key.

3) Usually this is done binary, like you did. If you are going to use CBC MAC with variable length messages, you must do this.

I recommend you to use XCBC or CMAC instead (CBC MAC variants for variable length messages).


What are the roles of the simulator in simulation based proofs

In general, the role of the simulator in simulation-based proofs is to show that the real protocol behaves like some idealized one. Actually, simulation goes back to the original definition of semantic security for encryption and is also the way zero knowledge is defined. In these settings, the aim of the simulator is to show that nothing is revealed (in encryption, nothing beyond the length of the plaintext; in zero knowledge, nothing beyond the validity of the claim). For concreteness, consider zero knowledge for a moment. In this setting, we construct a simulator who outputs a view of the verifier that is indistinguishable from its view in a real proof execution. Now, if the verifier can learn something from the proof itself, then we can run it also on the view generated by the simulator (or it itself can run the simulator on itself) and it will learn the same thing (up to computational indistinguishability). However, the simulator does not know the witness and it only knows the public statement being proved. Thus, this proves that the only thing that the verifier can learn is what can be learned from the public statement and a single bit that the statement is in the language.

When we consider the more general setting of secure computation, the adversary is allowed to learn the inputs and outputs of all corrupted parties. Thus, the role of the simulator here is to simulate the view of all corrupted parties, given their inputs and outputs. The problem that arises first is that the corrupted parties may change their inputs and so this is not something which is well defined. Thus, we consider an IDEAL MODEL with a trusted third party who receives the parties inputs and provides their outputs. The simulator works in this ideal model, and the requirement is that the output distribution of the honest parties and the simulator in an ideal execution is computationally indistinguishable from the output of the honest parties and adversary in a real execution. Once again, this shows that anything that a real adversary can do, can also be achieved in the ideal model. However, trivially, the only thing the simulator can do in the ideal model is to chose the corrupted parties' inputs. Observe that the simulator (who we also call an ideal-model adversary) actually has two types of interaction:

The simulator externally interacts with the trusted party, sending it the corrupted parties' inputs and receiving back their outputs. This is real interaction with an external party.
The simulator internally interacts with the real adversary and generates a view that is indistinguishable from its view in a real execution. This is not required by definition per se, but is really the only way to work. Note also that this is not real interaction, but the simulator runs the real adversary internally. It is necessary to do this in order to make sure that the output distribution is like in a real execution. Thus, the inputs used by the corrupted parties are effectively extracted by the simulator, and other events (like if a corrupted party aborts) are also detected. In the standard definition of secure computation, the simulator runs the adversary internally and so it can rewind it and do other tricks. The input extraction is necessary since the simulator needs to send the corrupted parties' inputs to the ideal trusted party (as in the previous item). Thus, it needs to be able to extract the effective input used by the real adversary. This shows that protocols that are secure under this definition have the property that all inputs are fully defined!

When it comes to universal composability, things become more complex since there is another entity called the environment. This is an external entity and the real and ideal adversaries interact with it (as real external interaction). The aim of the environment is to try to distinguish if it is interacting with a real adversary running a real protocol with honest parties, or if it is interacting with an ideal adversary/simulator and a trusted party computing the ideal functionality. In this case, we have the following interaction:

The ideal adversary interacts with the environment and hands it messages that it expects to see from the real adversary; this is real external interaction. In general, if the simulator generates a view for the real adversary that is indistinguishable, then whatever the internally simulated real adversary wants to send to the environment is just forwarded by the simulator to the environment (and whatever is sent back is forwarded to the internally simulated real adversary).
External interaction with the trusted party, as above
Internal interaction with the real adversary, as above. Note that a real adversary can forward every message it receives immediately to the environment and can get back some response (and in fact, it could be the environment who decides on all actions by the real adversary). This actually prevents the simulator from rewinding the real adversary since essentially it is the external environment who runs the adversary, and this is external interaction with the simulator and so cannot be rewound.

I know that this is all very complicated, but with some considerable effort, it makes sense in the end...


Password-Managers: what is the IND-CDBA attack logic?

Intuitively, IND-CDBA means an attacker cannot tell which of two databases contains a record he picked.

In other words even if you know the passwords in a database. And even if there are only two possible databases to pick from. An attacker still cannot figure out which one is the right one.

This is the formal definition from the paper:

Indistinguishability of databases game $\text{IND-CDBA}_{\text{Adv}_r, \mathcal{PM}}(\kappa)$:

  A challenger $\text{Ch}$ running $\mathcal{PM}$ interacts with
  $\text{Adv}_r$ as follows:

  $\text{Ch}$ runs $\text{mp} \leftarrow \text{Setup}(1^\kappa)$
  $\text{Adv}_r$ outputs two record-sets $\text{RS}_0, \text{RS}_1$
  $\text{Ch}$ selects a bit $b$ uniformly at random and returns the database $\text{DB}_b \leftarrow \text{Create}(mp, \text{RS}_b)$ to
  $\text{Adv}_r$
  $\text{Adv}_r$ eventually outputs bit $b'$ and wins if $b = b'$

This is similar to the familiar IND-CPA definition where you pick two messages and then you get an encryption of one of them and you have to guess which one it was.

Of course what this tells you in the end, is that you cannot learn any information about the passwords in a password file if this game is hard to win.


Apart from the obvious security vulnerability from using a simple XOR operation to convert between plaintext and ciphertext you also run into the massive security-flaw of each identical plaintext generates identical ciphertext.

In any given message, if a constant cipher operation is used along with a constant key, the resultant ciphertext will be same for every plaintext irrespective of the position of the plaintext within the message. This property causes patterns in the original plaintext to be revealed in the ciphertext.

Take for instance AES-ECB where even though a strong block cipher (AES) is used, a cipher operation that generates identical ciphertext for identical plaintext exposes the "pattern" of the message.

For a visual demonstration of this problem consider these images:

(Image courtesy of Wikipedia)
The first image shows the original message (a bitmap of the linux logo). The second image shows a encrypted version the same logo using AES-ECB. Notice how the pengiun can still be distinguished even after encryption.

This is due to the fact that every white sector in the image is passed through the cipher operation and generates an identical ciphertext causing the areas with differing colour to produce differing ciphertext in a manner that exposes the patterns of the original image.

To summarize, not only are you using an extremely insecure cipher operation of XOR (Information of why it is insecure is cluttered all over the web), using a cipher that generates ciphertext that is identical when the plaintext is identical is a security flaw in itself. Given that you are reusing the keystream for messages longer than the key, you definitely fall for both these vulnerabilities.


Can a block cipher be used to encrypt wireless communications?

Yes, you can encrypt wireless communication using a block cipher in a specific mode of operation to provide confidentiality. Transport modes also require integrity and authentication to protect against active attacks such as man-in-the-middle attacks.

CBC is however not a block cipher, and neither is CBC-MAC. CBC is a block cipher mode of operation used to provide confidentiality while CBC-MAC is a message authentication code used to provide integrity and authenticity. These constructs use a block cipher such as AES to provide this kind of functionality.

AES (and DES, 3DES, blowfish, Serpent, threefish etc. etc.) are block ciphers. They need to be used with a mode of operation such as CBC to provide confidentiality of messages; they cannot provide such functionality without a mode of operation. A mode of operation also requires an IV or nonce if the key is ever reused. In transport protocols the keys are usually kept for the duration of a session.

WPA2 may use the CCMP which combines AES in CTR (counter) mode for encryption and AES in CBC-MAC mode for integrity and authentication of messages.

Note that the protection of messages is just part of the protocol. Entity authentication and session key establishment require additional cryptographic primitives (a cryptographic primitive is an algorithm such as AES or RSA that is used within a larger scheme).


At a glance, I see no obvious weaknesses.  Obviously, the security proof of HMAC won't apply to this construction, but that doesn't necessarily make it insecure — it just means that we can't prove its security (given appropriate assumptions on the underlying hash function), or at least that we'll need different methods to do so.  Certainly, none of the (practical) attacks in section 6 of the original HMAC paper seem to apply.

Ps. Why do you say that the performance is worse than HMAC?  Both involve two calls to the hash function, one for arbitrarily long (but in this case, poribably fairly short) input and one for only fixed-length input.  Indeed, in some cases (keys longer than one hash input block) this scheme could be faster than HMAC.


Understanding the signature and hashing algorithms in TLS connection debug output

Although you don't say so, this appears to be a server-side log; your 'application' is accepting a connection from something else which is the client.

Yes, the client sends the list of ciphersuites it supports and is willing to use in ClientHello; this is usually more than one (often 10 to 20 and sometimes over 50) but it can be one as in your example. However offering only suite(s) using DHE-DSS requires the server to have a DSS (aka DSA) certificate, which is rare on the public Internet, although it may be more common in intranets (especially in the US government). See rfc 5246 section 7.4.1.2 which is not materially changed in this area from earlier versions. Each ciphersuite that uses certificate authentication (not anonymous or pure PSK,SRP,Kerberos) defines the type of publickey in the server (EE) certificate, and thus the 'raw' signature algorithm (except for plain-RSA which doesn't sign at all) but not the associated hash.

In TLS1.2 only, the client MAY include the signature_algorithms extension indicating what types of signatures it supports verifying. If used, this constrains both the signature done by the server on ServerKeyExchange if ephemeral (and DHE-DSS is), and the signatures on the certificates in the server's chain (except the root/anchor if present, since verify it is meaningless). If not used in TLS1.2, the server assumes the signature type implied by the ciphersuite, and SHA1; see section 7.1.4.1.
Also if used, the rare static (EC)DH ciphersuites which formerly constrained the second (CA) certificate key type no longer do so; see section 7.4.2.

Earlier versions of TLS did not have signature_algorithms; the server's signature on ServerKX always used a nonstandard combination of SHA1+MD5 for RSA and SHA1 for DSA and ECDSA, and the certificate signatures were not specifically constrained but prior to 2015 in practice almost always used SHA1 or MD5. MD5 is now considered broken for certificate signatures and prohibited by nearly all reliers (browsers and clients). The standard for DSA, FIPS 186, did not even allow it to use any hash other than SHA1 until 2009, and it took some time after that for most implementations to follow suit.

For completeness, if client authentication is used in TLS 1.2, the client signature in CertVerify if ephemeral, and certificate signatures, are constrained by a similar field supported_signature_algorithms (required, not extension) in CertificateRequest, and also by the certificate (and key) chosen which is constrained by the certificate_types field; see section 7.4.4. In earlier versions only certificate_types was present, and the CertVerify signature used the default hashes like ServerKX while the certificate signatures in practice used SHA1 or MD5.

All versions of TLS (back to 1.0) also allow the client to send a supported_curves extension identifying which elliptic curves it supports. If present and an ECDH[E] ciphersuite is negotiated (which can only occur if the client offers it/them) the server must use an ECDH key (point) on a curve on that list; if present and ECDHE-ECDSA keyexchange is negotiated it must use a certificate for (and thus sign ServerKX with) a key on a curve in that list; if present and any ECDSA-signed certificate(s) are used they must use curve(s) on that list. In practice the supported_curves list is often the two formerly-NSA-SuiteB curves, P256 and P384, sometimes extended to add P521.

Aren't you glad you asked :-?


What is the use of a nonce in public-key encryption if it's meant to be shared?

Thing is, this got me thinking - a nonce, in my book is a protection against forgery, but here I am giving it away.

The primary purpose of nonces is not protection against forgery, but rather, to ensure that encrypting the same plaintext many times with the same key does not produce the same ciphertext (which risks the possibility that an eavesdropper might learn something from frequency analysis).  For a very simplistic example, imagine encrypting the plaintexts YES and NO over and over and they always encrypted to XUW and EG.

There are protocols that secondarily exploit nonces in some fashion to avoid replay or reordering attacks (a kind of forgery). For example, when encrypting a large volume of data, one strategy is to break it into smaller sequential chunks and encrypt each one separately with the same key but a nonce that encodes:

The chunk number
A flag indicating for each chunk whether it's the last one

...so that when you decrypt the file, you verify as you go that no chunks have been reordered and that it hasn't been truncated.  But that's an optional thing an application may (wisely) choose to use chunks for, not a basic requisite like the ciphertext diversification.

I must say that I find the documentation that you link rather confusing in its treatment of nonces, because:

For ciphers popular today (and used by the Libsodium C library this PHP package is seemingly based on), encrypting two textually different plaintexts with the same key and nonce can result in a catastrophic security loss;
The linked page don't seem to sufficiently warn of the danger inherent to nonce reuse;
It also doesn't explicitly specify over what scope the library expects nonces to be unique.

Compare what the Paragonie docs say:

  Each message sent requires a nonce (a unique large number represented as a binary string that should only be used once).

...with its counterpart in the documentation of Libsodium library:

  The nonce doesn't have to be confidential, but it should be used with just one invocation of crypto_box_easy() for a particular pair of public and secret keys.

  One easy way to generate a nonce is to use randombytes_buf(), considering the size of the nonces the risk of any random collisions is negligible. For some applications, if you wish to use nonces to detect missing messages or to ignore replayed messages, it is also acceptable to use a simple incrementing counter as a nonce. A better alternative is to use the crypto_secretstream() API.

  When doing so you must ensure that the same value can never be re-used (for example you may have multiple threads or even hosts generating messages using the same key pairs).

Much, much better, and the recommendation to use random nonces is safe, but the alternative suggested of using a simple incrementing counter is a bit scary, it's much too easy to implement that wrong e.g. across multiple executions of the same program.  They suggest the use of their newer crypto_secretstream() API instead, but that uses shared-key encryption, not public key, leaving the user the highly non-obvious task of figuring out how to wire those together.

Caveat emptor. Cryptography is a minefield.


Is the result of HMAC-sha256 distinguishable from random noise?

If the keys and messages are known, yes, you can distinguish which were used - because you can test them all. If not, then this is "sligtly harder" (= not really possible with big enough values). Anything of the further answer will assume that the attacker doesn't know the keys or the messages.

The definition of HMAC looks like this: $HMAC(K, m) = H(K \oplus opad || H((K \oplus ipad) || m))$ with $k$ as the key and $m$ as the message. $opad$ and $ipad$ are constant, different values while $H()$ is the used hash function - in your case SHA-256. We can see that the end result is the output of a hash function. If there's nothing special happening with the key or the message inside the function, than all security features about the hash should also hold for HMAC. Finding the original message (while having the output of the hash function) should be hard - that's called preimage resistance. As long as the keys and messages were long enough, it shouldn't be possible (with non-ignorable probability) to find the orignal message in a reasonable time. Good hash functions should also be not distinguishable from truly random output, so this should also be no problem.

Even if you have every message HMAC-hashed with every key it is still not possible to say which HMACs were calculated with the same key / with the same message. The attacker will only see $1\,000\,000$ random looking bit strings ($1000$ keys times $1000$ messages) and have no clue what to do with them.

As soon as there are patterns in the keys or messages, it will be easier to attack the hashes. $80$ bit of entropy (from message and key together) should be enough to ward of any brute force attack. No hash is secure if the messages are small enough.

The document Keying hash functions for message authentication has more informations and the security proofs for HMAC. You can read there why it should be not really possible to find the used messages and key in your scheme - if they are big enough.


Assuming you mean EK1(m) || EK2(H(m)) or EK(m || H(m)), it is not an approved MAC scheme in any standards and may have issues. Instead, you should probably use an HMAC, which involves taking the message and the key and hashing them together. An HMAC is defined by RFC 2104 as HMACK(m) = H((K ⊕ opad) || H((K ⊕ ipad) || m)) where opad and ipad are constants. An HMAC is a keyed hash function, which means the digest depends on both the message and the key.


Hiding the metadata of a one time pad message by encrypting the next key

Basically that's a one time pad variant where each day a cryptogram is sent, consisting of one between

on days before the actual message is sent, a new random pad replacing the previous random pad (of same size as the original), encrypted by XOR with the current random pad;
on a certain day, the message to be sent (padded to the pad size) encrypted by XOR with the current random pad;
random (of the pad size) on subsequent days.

That allows to send a single message. As is, the receiver has to know in advance or figure out on which day the message was sent, but the later is easy for practical messages.

That works; assuming all random bits generated are perfectly independent and unbiased, it insures the same unconditional security as the one pad, and meets the stated security objective of concealing on which day the information is sent. The quality of the generator is paramount: notice for example that a mere distinguishing attack allows to find on which day the actual message is sent.

Form a practical standpoint, the proposed system has a serious operational drawback compared to sending random on every day the message is not sent: if the cryptogram from any day before the actual message is sent gets lost (or is garbled), the message can not be deciphered (or is garbled).

I do not see any advantage, under the hypothesis that all random bits generated are perfectly independent and unbiased.


Can the encryption exponent e be greater than ϕ(N)?

From Euler's Theorem, it turns out that, for $\gcd{(a, n)} = 1$, we have:

$$\large a^e \equiv a^{e ~ \mathrm{mod} ~ \varphi{(n)}} \pmod{n}$$

So, really, having $e > \varphi{(n)}$ doesn't do anything - you may as well use the reduced exponent:

$$e ~ \mathrm{mod} ~ \varphi{(n)}$$

You can absolutely use $e = n$ if you want to, it does not leak information about the private key. It's just slow. I mean use $e = n$ directly, of course - do not reduce it modulo $\varphi{(n)}$ to make it faster, since all you would get is a reduced public exponent of $p + q - 1$, and a free ticket to instant factorization of $n$.


Yes, a nonce is a number not used more than once. In its purest sense there should be no other requirements than this, i.e. randomness or unpredictability should not be necessary.

However, in certain settings stronger requirements are put on the nonces; like for instance in the CBC-mode of operation for block ciphers the IV (nonce) needs to be unpredictable (a requirement, when not followed, actually have led to real-life problems in the SSL/TLS-protocol:  Why is CBC with predictable IV considered insecure against chosen-plaintext attack?).

See also: What is the main difference between a key, an IV and a nonce? for a more comprehensive discussion of the properties of nonces and IV's.


Are PBKDF2 derived keys related if only the number of iterations is changed?

Leave the iterations the same, they should be determined by the CPU time.

Instead provide a different random salt to PBKDF2 on each encryption, you can just concatenate the salt to the encrypted data, it does not need to be secret.

Of course for CBC you also need a new random IV for each encryption, it too can be concatenate to the encrypted.

You should also MAC the encrypted data so that you can determine ion the decryption succeeds, that is the correct key is used.


I see no way. Typed keys are typed to prevent them from being used for another task than being the key to the designated algorithm.

What you maybe could do is use the key to derive another, and use it as an HMAC key. But I do not immediately see how we could avoid that the HMAC key could leak of the PKCS#11 device.
Note: this comment sketches an option. But I can't remember of a key derivation mechanism in a PKCS#11 device that allows to derive a key remaining internal but where the new key is for a completely unrelated algorithm (even as a proprietary extension). Also, if the intended algorithm is not fed to the derivation, that could be susceptible to attack by using the same key for a variety of algorithms. For example DES to get 56 bits out of the first 64, then two-keys 3DES for 112 out of 128, then AES-128 for 128 out of 128, and so on.

If compatibility with standard HMAC is not needed, then an option is to compute an AES-based MAC of the SHA-512 of the message, which is possible with the key in the PKCS#11 device, and can likely be much faster since the SHA-512 of the message can be computed externally.


Does the output of a cipher have to be no longer than the input?

a cipher isnt good unless its the same length as the original?

This is completely false. In fact, with most modern block cipher modes of operation, you will get ciphertext lengths that are longer than the original input. In fact, a ciphertext length longer than the input is a requirement for integrity protections (which is a must-have these days).

  so is my cypher useless?

This we cannot judge given the information you've posted. Ciphertext to plaintext length ratio is meaningless when it comes to determining the utility of a cipher. If you want to know if your cipher is useful, you need to 1) publish the full details of the algorithm, 2) describe its benefits when compared to existing ciphers (what new capabilities does your cipher give me that I don't already have with AES), 3) get a bunch of really smart cryptographers to work on breaking it for years.


This might be a bit off-topic, but I can not yet add a comment:

Note that you can also use the SBox object, included in recent Sage versions (from >= 8.2, I think):

sage: from sage.crypto.sboxes import AES
sage: AES
...

This offers you methods for cryptanalysis etc.


Why does Learning With Errors require a bunch of samples?

The number of rows in matrix $\textbf{A}$ shows the number of LWE samples and $m=1$ means the adversary has access only to one sample. This would be a naive adversary model and would not be suitable for assessing the true hardness of the Problem.
To consider a more powerful adversary model, a (seemingly) stronger definition is to assume that the adversary has access to arbitrary $m$ independent samples.

In the case of R-LWE, a single sample ($m=1$) takes the place of $n$ (correlated) LWE samples.
Even if we assume that the adversary has only one sample, then just as in LWE, finding the secret seems (intuitively) to be harder.


Does a cofactor of an elliptic curve have to be an integer?

The implications are that someone screwed up some calculation.

By Lagrange's theorem, the co-factor must be an integer.


The MAC algorithms used in TLS (and the older SSL) cipher suites have historically been HMAC, with the hash function used in the HMAC specified in the cipher suite.

HMAC is very widely used and described so I won't repeat the full description of it here, but it essentially hashes all the data in messages being sent to and from the webserver, combining the resulting hash with a key (which is negotiated during the TLS connection) into a short message authentication code that is sent alongside the message - the receiving end then repeats the process to ensure that the message has not been altered in transit.

Newer cipher suites used in later versions of TLS (e.g. TLS 1.2) include AEAD encryption algorithms, which you can think of as encryption with a built-in MAC, and .

e.g. viewing this question over https in Firefox 34, the cipher suite being used is TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256, meaning that the MAC algorithm being used is the built in MAC provided by the GCM AEAD encryption mode.

If the cipher suite had been TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256, then the MAC algorithm would be 'HMAC with SHA-256`


DES- If LSB is removed, are the key B and C the same?

The ASCII letters B and C are represented by the bytes 0x42 and 0x43, which indeed are equivalent in a DES key since they differ by the low-order bit only. However the tool used accepts keys in hexadecimal, and the byte 0xBB and 0xCC are not equivalent key bytes for DES.


Are TLS connections in china mostly encrypted with AES or with SM4?

I think as of June 2020, it's still AES, as SM4 isn't registered in IANA formally backed by an RFC yet, and most browsers used by netizens in China are based on Chromium (some users use FireFox, and some government websites still requires IE!).


Double Encrypting with two different keys

I don't think it's a bad idea - neither does Bruce Schneier.  In his book Applied Cryptography, there is a section called "Cascading Multiple Block Algorithms". He basically states that provided that two distinct algorithms and two independent keys are used, then the result should be at least as difficult to break as the strongest algorithm.

If Alice and Bob do not trust each other’s algorithms, they can use a cascade. If these are stream algorithms, the order doesn’t matter. If they are block algorithms, Alice can first use Algorithm A and then use Algorithm B. Bob, who trusts Algorithm B more, can use Algorithm B followed by Algorithm A. They might even add a good stream cipher between the two algorithms; it can’t hurt and could very well increase security.
Remember that the keys for each algorithm in the cascade must be independent. If Algorithm A has a 64-bit key and Algorithm B has a 128-bit key, then the resultant cascade must have a 192-bit key. If you don’t use independent keys, then the pessimists are much more likely to be right.


A byte $b$ in AES represents a polyonmial of degree at most $7$ where the coefficients are the bits of $b$. An example is the byte written in hexadecimal f3 represents $x^7 + x^6 + x^5 + x^4 + x + 1$ (with big endian order).
There are two operations with these polynomials: the addition and the multiplication. Given the polynomials $f(x) = a_7 x^7 + \cdots + a_1 x + a_0$ and $g(x) = b_7x^7 + \cdots + b_1 x + b_0$, then the addition is
$$
f(x) + g(x) = (a_7 \oplus b_7) x^7 + \cdots + (a_1 \oplus b_1) x + (a_0 \oplus b_0),
$$
using a xor between the coefficients of each polynomial, so the resulting polynomial is also of degree at most $7$, with binary coefficients.
Concerning the multiplication it is necessary to add a reduction in case the degree of the polynomial is greater than $7$. Example:
$$
f(x) \cdot x = a_7 x^8 + \cdots + a_1 x^2 + a_0 x.
$$
In particular for AES, it is a modular reduction with the polynomial $h(x) = x^8 + x^4 + x^3 + x + 1$. It means that in all the calculcations, we have
$$
x^8 = x^4 + x^3 + x + 1,
$$
so the previous calculation becomes
$$
\begin{array}{rcl}
f(x) \cdot x & = & a_7(x^4 + x^3 + x + 1) + a_6 x^7 + \cdots + a_1 x^2 + x \\
 & = & a_6 x^7 + a_5 x^6 + a_4 x^5 + (a_7 \oplus a_3) x^4 + (a_7 \oplus a_2) x^3 \\
& & + a_1 x^2 + (a_7 \oplus a_0) x + a_7
\end{array}
$$
Why in particular this polynomial $h(x)$ is because it has degree $8$ and cannot be written as a product of two (or more) non-trivial polynomials (similar as prime numbers that cannot be written as the product of two or more integers greater than $1$).
Now, all that is said above is enough to understand the m2 and m3 boxes that can be encountered in some implementations. The m2 box is only the multiplication by $x$ of all polynomials. For polynomials of degree at most $6$, it means only a bitwise shift left, but for polynomials of degree $7$, a reduction is necessary.
$$
\begin{array}{ccc}
\hline
\text{hex} & \text{polynomial} &  \text{times } x & \text{hex}\\
\hline
\texttt{00} & 0 & 0 \cdot x = 0 & \texttt{00}\\
\texttt{01} & 1 & 1 \cdot x = x & \texttt{02}\\
\vdots \\
\texttt{7F} & x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 & x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x & \texttt{FE} \\
\texttt{80} & x^7 & x^7 \cdot x = x^4 + x^3 + x + 1 & \texttt{1b} \\
\vdots \\
\hline
\end{array}
$$
The m3 box is the multiplication by $x + 1$ and is easily obtained with an addition of the polynonmial $f$ with the result of the m2 box since:
$$
\begin{align}
f(x) \cdot (x + 1) & = f(x) \cdot x + f(x) \cdot 1 \\
& = f(x) \cdot x + f(x)
\end{align}
$$
More information on the wikipedia page of finite fields for a more general description finite fields.


Does a playlist of songs or movies mixed together contain enough random enough for OTP key material?

The bits are not independent from each other, at least within an individual song, so the pad is not truly random, thus this is not a one-time-pad. Perhaps a hash-based approach would fix this, but...

... there are a limited number of songs available, a simple attack would then be to enumerate every song (in the same format you describe) and try to decrypt a portion of the ciphertext (e.g. try bits 0 to 10, then try bits 1 to 11, etc... until you get something meaningful). Therefore the ciphertext can be broken by brute force, it is then not a one-time-pad by definition.

You'll notice your initial permutation had no effect on the efficiency of this attack. But even if it did, you must use some source of randomness to shuffle your song list, right? If you used a PRNG, someone could break that, and deduce the permutation you used. That's another dangerous "moving part". And if you had a true randomness source, then why not use it to create the pad in the first place?

Also, presumably you don't want to destroy your music after you've made it into a "one-time-pad", so your pad would also exist in its more explicit form on your hard drive -> big security risk (it considerably simplifies the attack above, as we now know exactly which songs to try to decrypt the ciphertext with).

Bits are bits, and entropy is entropy. It doesn't matter whether the data represents music or TV shows - those are human concepts whereas theoretical cryptography is intrinsically an abstract science.


I sent a mail to the Keccak team asking about this, and I got a response from one of the authors (Joan Daemen to be specific).

According to him, we actually can instantiate Sponge functions and Duplex objects with a "transformation" in addition to a permutation, the latter of which is what we commonly do. As long as the underlaying (fixed-width) function is indistinguishable (computationally) from a random one.

So the real reason we don't usualy use a "transformation", is that - It's not usually efficient.

Quote from the mail response.

  The reason that the sponge construction is mostly instantiated with
  permutations (Keccak, Xoodyak, Spongent, etc.) is that we - as a
  cryptographic community - have a method to build efficient permutations
  that seem to give rise to secure sponge functions but not to build
  efficient transformations that do the same and the invertibility of the
  permutation does not hurt as far as the indifferentiability and
  indinguishability bounds are concerned. ...

This is true, the round functions in Feistel-network block ciphers such as DES and SM4 aren't optimal efficiency-wise, especially when compared to constructs such as ARX (add-rotate-xor such as that in ChaCha20), and bitwise-and-shift operations (such as those in Gimli, Keccak, NORX).

To conclude:

  ... We actually build a permutation
  by iterating a simple round function that does mixing, nonlinearity and
  shuffling. Sponges have been built with a transformation that is not a
  permutation, like Gluon, but that was no great success in my opinion.


What is the difference between "wrapping" a key and encrypting?

I get nausea every time I look at the WebCrypto API documentation, so if all you get is confusion, consider yourself lucky.

From what I can tell by reading the W3C Web Cryptography API recommendation of 2017, in particular the §19 Algorithm Overview table, the only difference is that the AES-KW algorithm of RFC 3394 supports wrapKey/unwrapKey but not encrypt/decrypt.

The intent appears to be that you use wrapKey/unwrapKey when you know the plaintext is itself a short uniform random octet string, but encrypt/decrypt if it has any other structure to its distribution; then if you attempt to use encrypt/decrypt with AES-KW, the API will noisily fail because you might be trying to use it with structured data, which AES-KW is unfit to conceal.

For all other documented encryption schemes, public-key or secret-key, wrapKey/unwrapKey just defers to encrypt/decrypt.  So there's no idea of KEM at all, which simultaneously generates a key and encapsulates it for you.  One can hope that they will introduce a KEM API in the next version of the specification, since with NIST PQCRYPTO it appears the world is finally, nearly two decades after Shoup introduced the concept, converging on it as the basic way to do public-key encryption.


Key derivation using known parameters of playfair

There are two issues to be aware of.
Firstly if the message and cipher text are short, or lack variation in the usage of letters, there may not be enough information to recover a complete Playfair square,
Secondly, rotating all the rows or all the columns of a Playfair square gives an alternative square that encrypts in the same manner. Thus squares come in families of 25. If the “key” is a word or phrase, it is usually straightforward to recover the key used by the system. If the key is a “random” arrangement of 25 letters, then the precise key cannot be distinguished from the other 24 without more information.
If you're asking about the process for recovering the square given matched plain and cipher, this can be done manually and is relatively straightforward. Consider a common letter such as "E" and select all digraphs involving this letter. There are only 5 letters that can replace our chosen letter: the four with which it shares a row and the one directly beneath it. Suppose then we find that we find "E" can be encoded only as one of "ADFLX", now choose a common one of these an examine digraphs. For example we might find that "A" can only be encoded as "BEFLX", we can now conclude that one row contains the letters "AEFLX" and that "D" and "B" lie directly below "A" and "E" respectively. Now consider the letters apart from "ADFLX" that appear in digraphs with "E", within those digraphs these letters can only be encoded as either a letter that lies in the same column as "E", or a letter directly to the right. The ones encrypted to the right will share a column with "E" and "E" will be encoded to the same letter for each of these. These rules should allow you to reconstruct rows and columns of the square. The order of the rows and columns can only be inferred from encryptions of digraphs that share a row/column.


Maarten appears to make it look like it's an impossible (or, at least, an exceedingly difficult task) to recover the two plaintexts.

Indeed, if you literally know nothing about the plaintexts, it can be difficult.  However, you typically have a reason you are interested in the messages, and hence often have a clue as to what language they might be.  If the language is 'random bits', or something else which is high entropy, it can be a difficult or impossible task.  However real plaintexts often don't fall into that category.  You mentioned that they might be json files; lets go with that.

One common trick that is useful in many languages is crib dragging; you pick an n-gram that is common in the language (for json, the 4-gram consisting of the characters ", :, space and " is one possibility), and xor in that in various places in the xor'ed plaintexts.  If one plaintext consists of that 4-gram in that spot, the result of the xor will be the contents of the other plaintext in that location.  Hence, if the result of the xor is a plausible plaintext, you might have successfully decoded both messages there (and can possibly extend the decode, if the other plaintext has obvious previous/next characters).

By using several such cribs, and by expanding revealed plaintexts when possible, my experience (with ASCII-encoded English) has found it to be a doable process -- I don't have any specific experience with json, however I would expect it to be doable as well.

I don't personally know of any tooling that would help you (I built my own tooling on the fly when I did it); however I wouldn't be surprised if something exists.  However, I would expect any such tooling would require some hand-holding (as people are more likely to judge correctly whether things are plausible or not).


Length extension attacks, Merkle–Damgård constructions, and HMACs

Your quote is wrong:

  The wikipedia page for Length Extension Attacks says "Note that since HMAC doesn't use [Merkle–Damgård constructions], HMAC hashes are not prone to length extension attacks."

The part that you've paraphrased in square brackets is a misreading of the original, which reads (my boldface):

  When a Merkle–Damgård based hash is misused as a message authentication code with construction $H(\mathrm{secret} ‖ \mathrm{message})$, and message and the length of secret is known, a length extension attack allows anyone to include extra information at the end of the message and produce a valid hash without knowing the secret. Note that since HMAC doesn't use this construction, HMAC hashes are not prone to length extension attacks.

The antecedent of "this construction" in the final sentence isn't the Merkle–Damgård construction, but rather the secret prefix MAC construction.


Update non-member witness in RSA accumulator

Recall that for a set of elements $X=\{x_1,\cdots,x_n\}\subseteq\mathcal{X}$

the value of the accumulator is $c=g^u\bmod{N}$, where $u:=\Pi_i x_i$; and
the witness of non-membership for an element $x\not\in X$ is the pair $(a,d=g^{-b})\in\mathbb{Z}\times\mathbb{Z}_N^*$, where $a$ and $b$ are integers satisfying Bézout's identity $$au+bx=1,\tag{0}$$
which is verified by checking whether $$c^a=d^xg\bmod{N}.\tag{1}$$

We are considering the case where an element $\hat{x}\neq x\in\mathcal{X}$ has been added to $X$, i.e., the new set is $\hat{X}:=X\cup\{\hat{x}\}$, and this has resulted in the accumulator value
$$\hat{c}:=g^{\hat{u}}=(g^u)^{\hat{x}}=c^\hat{x}\bmod{N},$$
where $\hat{u}:=u\cdot \hat{x}$. We would like to update the witness of non-membership for $x$ to $(\hat{a},\hat{d}=g^{-\hat{b}})$, where $\hat{a}$ and $\hat{b}$ are integers satisfying Bézout identity
$$\hat{a}\hat{u}+\hat{b}x=1.\tag{2}$$
This could be done from scratch, but it is desirable to derive it efficiently from the previous witness $(a,d)$ and accumulator value $c$. I did not quite understand how it is done in the paper, but another way to accomplish the same would be as follows:

Find integers $\hat{a}_0$ and $r_0$ satisfying Bézout's identity
$$
    \hat{a}_0\hat{x}+r_0x=1.\tag{3}
  $$
Note that this is possible since $x$ and $\hat{x}$ are co-primes.
Set $\hat{a}=\hat{a}_0a$ and $\hat{d}=dc^r\bmod{N}$, where $r=r_0a\in\mathbb{Z}$ .

Let's see why Step 2 works. Our goal is to go from (3) to (2) and we do this using (0): let's multiply $(3)$ on the left by $au$ and on the right by $1-bx$ yielding
$$\begin{align}
    \hat{a}_0\hat{x}(au)+r_0x(au)=1(1-bx)
   &\Leftrightarrow \hat{a}_0a(\hat{x}u)+(r_0au+b)x=1\\
   &\Leftrightarrow (\hat{a}_0a)\hat{u}+(r_0au+b)x=1\\
   &\Leftrightarrow \hat{a}\hat{u}+\hat{b}x=1,
    \end{align}
$$
where we set $\hat{a}=\hat{a}_0a$ and $\hat{b}=r_0au+b$. Now, observe that although we can compute $\hat{a}$ we cannot compute $\hat{b}$ (since we don't know $u$). However, what we need is $g^{-\hat{b}}$ and it is possible to compute this from $c$ and $d$ as
$$g^{-\hat{b}}=g^{-r_0au-b}=(g^u)^{-r_0a}g^{-b}=c^{-r_0a}d\bmod{N}.$$


why people don't use the same generators?

You can use the same $g$. However, if the discrete log of $h$ relative to $g$ is known, then Pedersen is no longer binding. Thus, you cannot use an $h$ if there is any possibility of someone else knowing that discrete log.


Is a random oracle controled by the challenger?

As @xagawa mentioned in his comment, it depends on what you mean by "controled".

In the case of using a programmable random oracle, yes, the reduction (in particular the simulation of the challenger of the real game) decides about what to return as answer to an oracle query. Thereby, the reduction has to guarantee that the "programmed" answers are consistent (identical answers to identical queries) and that the distribution of the answers are uniformly random to the adversary.

Such reductions are the ones typically used for reductionists proofs in the ROM, as it nicely allows the reduction to embed a problem instance into the adversaries queries to make the reduction work.

Typically, the random oracle is also observable, i.e., besides the programmability, the reduction "sees" all oracle queries and thus knows how much queries the adversary has made to the random oracle.

There are also works investigating non-observable reductions, where the random oracle is external to the adversary and the reduction. But they still can provide some means of programmability as the reduction can decide on the turing-machine that is used for the external oracle. In the linked paper you find some results for non-observable but programmable random oracles and also some examples for reductions in the ROM that also work if the observability is removed.

There is also the possibiltiy to have reductions in the ROM which are non-programmable and non-observable, but this enormously reduces the power that the ROM provides you in reductionists proofs.