Poor man's SSL - is this method as safe as SSL/TLS?

TLS not only provides privacy, but also authentication:

You can be sure you know who you speak to (at least the client knows if the server was using a certificate). (You provide this by the "HTTPS key exchange" you are doing at the start.)
You can be sure that you speak to the same entity at the other side throughout the whole live of your connection (even if you don't know who this is, e.g. as a server with non-authenticated client).
You can be sure that you get exactly what the other side sent, not something modified by someone between both sides.

AES (or any other block cipher) in a streaming mode (like CBC, CFB, OFB, CTR, ...) doesn't provide this guarantee. Because of this, there are various attacks at these modes which also endanger your privacy.

So make sure you are either

using a mode of operation which also includes authentication (look for "AEAD") or
using a normal privacy mode together with an external MAC (like HMAC) - and transfer the MAC key together with the encryption key during your key exchange).


Generating keys with HKDF from Diffie Hellman agreement

You don't need a salt (it defaults to a zero length salt) if you generated the session keys using Diffie-Hellman. You should however use a different info (octet) string for each key in the expand part of the function.

The idea is that the salt makes sure that the derived keys are different if the input keying material (IKM) repeats. If no salt is used within the key derivation then the session keys would be identical each time the key derivation function is performed. Diffie-Hellman however should never generate identical input keying material (see note).

The info strings should be static for each key, e.g. an ASCII encoding of "enc" for an encryption key would be a good idea.

Here's a link to the RFC for HKDF. Here's a link to Hugo Krawczyk's paper describing HKDF at length.

Note: at least one of the parties in the DH key agreement should generate sufficiently random ephemeral key material. If the random number generator (RNG) is broken then you may get identical input key material. It is not possible to generate a random salt if your RNG is broken though. In other words, you need a good RNG whatever you do.


Validate per round rather than cycle-walking in FPE

I don't think this would break correctness, but it's possible you might actually slow your algorithm down on average. You'd need a more rigorous combinatorial analysis of the expected number of repeated rounds vs. the expected number of full cycle walks. That really depends on the specific algorithm; are you using FFX?

You'd also need to show that doing this doesn't alter the distribution of ciphertexts in a way that breaks SPRP security. It's possible that it doesn't, but proving it seems nontrivial to me.


In a group, where there is by definition only one operation, exponentiation means repeated application of the group operation, whatever that is. That is, if the group operation is noted $\circ$, $g$ is a group element, and $x$ is a positive integer, $g^x$ is short for $\underbrace{g\circ g\circ\dots\circ g}_\text{$x$ terms}$.

In elliptic curve groups, the operation is the point addition with which you are hopefully familiar.


Understanding forking lemma and oracle replay attack

We use the fact that forger $\mathcal{F}$ is nothing else but a Turing machine with some random tape. And since $\mathcal{F}$ is in our possession, we can choose the tape.
Therefore, we can rerun $\mathcal{F}$ with the same tape, and behavior of $\mathcal{F}$ will be just the same (until the point where the oracle will return different value and desired "forking" occurs).


How can recovered 5-letters plain text help me to recover reused OTP key

Assume that $P_1$ contains " the ". In that case you can get the key stream by XOR'ing " the " with $C_1$, lets call this key stream $K^1$. If this key stream is correct then $P_3^1$ should make sense, where $P_3^1 = K^1 \oplus C_3$. If $P_3^1$ doesn't make sense then you can create $K^2$ and $P_3^2$ from $C_2$ in using an identical calculation and check that.

Of course, as you've got 10 ciphertext you might as well check against $C_3$ to $C_{10}$. They all should make sense if you've got the right key stream at the location you are testing. Beware though that some professors find it funny to introduce single "mistakes" in the plaintext, forcing you to perform statistics (or "by eye" verification) instead.


Finding the basis of the transpose of a q-ary lattice

If $n<m$ then for almost all matrices $A$ the columns of $A^T$ will be linearly independent and in that case $\Lambda(A^T)$ is the lattice generated by the basis  $qI$ (which is the shortest possible basis for this lattice).


Can I truncate a CSPRNG psuedorandom number?

The idea for the security notion of Cryptographically Secure Random Number Generators (CSPRNGs) is that at the very least they are as good as Pseudo-Random Generators (PRG) which is why I'm applying their security notion of Indistinguishability.

This says that the probability that somebody can distinguish a PRG from a truly random sequence is better than guessing is negligible.

Now what you want to is to truncate the output of a CSPRNG (that is, you straight-up discard certain bits from the output). Now assume the result was insecure. As this truncated part would also be output by the actual CSPRNG, you could then "just" use this sub-part of the output and use the weakness we assumed to distinguish the CSPRNG's output from random. Now we assumed this to be impossible, so it can't be that such a weakness as assumed above exists and thus it must be secure.

A similar argument applies if you apply a public bijection on the output or a part of it.


How does a receiver treat X.509 self-certificate with unknown the Signature Algorithm ID?

In the latest X.509 RFC you can read:

  The signatureAlgorithm field contains the identifier for the
     cryptographic algorithm used by the CA to sign this certificate.
     [RFC3279], [RFC4055], and [RFC4491] list supported signature
     algorithms, but other signature algorithms MAY also be supported.

However from RFC 3279, section 2:

  Conforming CAs and applications MUST, at a minimum, support digital
     signatures and public keys for one of the specified algorithms.  When
     using any of the algorithms identified in this specification,
     conforming CAs and applications MUST support them as described.

But more importantly, when verifying a certificate chain, there is no need to perform the validation certificate when validating the certificate chain. This certificate needs to be trusted beforehand.

So if you receive the certificate by the appropriate "out-of-band" procedure, you could validate the certificate at that time. Afterwards you only need to validate the dynamic values such as the end date of the certificate and - possibly - the status of the certificate - if it has been revoked or not.

That means that for devices with limited capacity you can validate and verify the certificate beforehand, put it in the device using a trusted path to the device / storage and then "just" check the date in the field.

This can be read in section 6.1 of the X.509 RFC:

  When the trust anchor is provided in the form of a self-signed
     certificate, this self-signed certificate is not included as part of
     the prospective certification path.  Information about trust anchors
     is provided as inputs to the certification path validation algorithm
     (Section 6.1.1).

Great, so that solves the problem, right? Not really. The public key of the certificate is commonly also used to encrypt or to verify the signatures send in the application - the reason the certificate exists in the first place. So now you've got your trusted "chain" of one certificate you're stuck with a public key that you cannot use, because it is identical to the one performing the signature verification over the certificate itself.

It would of course be possible that the receiver can encrypt or perform key agreement using the public key while the signature verification algorithm isn't available.

This issue is specific to self signed certificates because the public key is generally only used for a single purpose, while it must at least sign and possibly perform another kind of operation as well.

Notes:

Protocols may put additional requirements on which algorithms are supported, e.g. although TLS doesn't explicitly require RSA signatures / encryption, many websites would not work without it.
"a certificate" has a different meaning than "a certification". The latter means having a product certified against e.g. FIPS or Common Criteria. So "certification" is normally used in the more analog, paper-y sense.
"just" is put within quotation marks because getting the time from a trusted time source may be very tricky on restricted devices.


let's say I take key length of 16 bytes. Does it mean that according to wiki I must pad the key with zeros from right up to 512 bits? (block length of SHA1)

Yes.

  opad must be a 512 bit value, like: 0x5c5c5c…5c5c....5c (512 bits)?

Yes.

  ipad similarly: 0x363636…3636 (512 bits long)

Yes.

  what to do with m if its length is not 512 bits?

This should not be relevant for the HMAC implementation itself, since the hash function is the cryptographic primitive responsible for effectively processing the message (of arbitrary length).

  what is the recommended length of actual key? and recommendation for key generation?

Before using it, HMAC will pad the provided key material with 0's until it reaches the block size. The size (and the quality!) of this key material depends on how much security your implementation is targeting. Note that RFC2104 "strongly discourages" the usage of keys of shorter length than the hash output (see comment from otus), which for SHA-1 would be 160 bits. As SEJPM mentioned in his comment to the question, the key can be either generated at random or pre-shared/derived from a common secret (see Diffie-Hellman).

  is it bad idea to implement HMAC myself, if I have implementation of SHA1?

It might be a good exercise if you want to get familiar with cryptography implementation details. However if you need an HMAC implementation in the scope of a project for example, you may prefer to use an extensively tested and validated implementation (e.g., open source cryptography libraries).


Why this isn't second preimage resistance?

Using the hash function;
$$h(M) = \operatorname{AES-Enc}\big(M[0\ldots n], M[(n+1)\ldots 2n]\big) \oplus M[0\ldots n]$$
One can find many pre-images with the given hash value $h$

take arbitrary $M[0\ldots n]$
calculate $x = M[0\ldots n] \oplus h$
Decrypt AES with the key $M[0\ldots n]$ and the ciphertext is $x$
$$m =\operatorname{AES-Dec}\big(M[0\ldots n],x\big)$$

let $M[(n+1)\ldots 2n] = m$ then we are done, found a pre-image. Now if the founded pre-image is different than the provided $M$ with the $h = h(M)$, then this is a second pre-image for the hash function. If not, one can look for others to find a secondary image for this hash function. Therefore, this is neither a pre-image resistant nor second pre-image resistant hash function.
We just used the property of AES that is a permutation under a key and the key is free to the attacker.


Which multiplicatively homomorphic encryption scheme supports encryption of 0?

Gentry's recent work highlights both FHE and SHE with and without bootstrapping easily found on Google Scholar. The open source code on Github is getting closer to reducing the associated complexity. IMB and Microsoft have a myriad of code and papers on the subject.

Having said that what you are proposing has never been done before, but here is one helpful papers that may assist you depending on your commitment:

http://eprint.iacr.org/2011/607.pdf

It does not solve your issue but it does present some helpful side points that may assist you if you read it enough.


Estimate Security level of the Rabin Signature

With proper choice of key and padding, the most efficient purely cryptographic known attack on Rabin signature and RSA (encryption and signature) is the same: factoring the public modulus. Therefore, size recommendations for the public modulus are the same. If 3072-bit RSA achieves 128-bit security by some criteria, Rabin does.

Beware that there can be implementation attacks specific to Rabin and its Jacobi computation, that do not apply to RSA. Also, Rabin signature is unforgiving to some poor padding (especially deterministic): it can degenerate into a total break (factorization of the public modulus), when it remains an existential forgery in RSA signature.


In AES key schedule, firstly a round key x-ored with the plaintext before the first round. The used keys are $k_0, k_1, k_2, \text{ and},k_3$ where each has 32-bit. The next key used in the round key is calculated as follows;

\begin{align}
k_4 &= k_0 \oplus f_1(k_3) \\
k_5 &= k_4 \oplus k_1 \\
k_6 &= k_5 \oplus k_2 \\
k_7 &= k_6 \oplus k_3 \\
\end{align}

As you can see, with the first non-linear $f_1$, we have an avalanche effect that will affect the rest. There can be some cases that this kind of key produces bad keys that causes attack less than 64-bit security, but;

What is 64-bit security in today standards. Many super machines can reach $2^{64}$ very easily; Titan, summit. Also, the collaborative power of bitcoin miners reached $2^{92}$ SHA-256 hashes per year in 06 August 2019.

Also, if you look at some recent specially designed DES attack machines they reached to find DES key in 25 seconds in 2017, i.e. 56-bit reached 25 seconds.

In, short, even there can be attacks needs to be searched better than the brute force, that is only for enthusiastically as long as there is a hidden aim in your question. The luck of having such a key from good key gen is negligible.


Obtain Information about hash algorithm from ECDSA public key

For the public key there is no hash defined. The hash is a configuration option for the signature generation algorithm but it would work for any EC key.

And your information about the key is, for that reason, also incorrect. SHA-1 is maybe mentioned by a tool, but the OID you gave can be written out in long-form (ASN.1 notation) as:

{iso(1) member-body(2) us(840) ansi-x962(10045) fieldType(1) prime-field(1)}

... there is no SHA-1 in there.

So basically the signature generation is dependent on the application you used to produce the signature.

If it is configurable then the hash algorithm should be included with the signature - not with the key. It would of course be advisable to validate that the signature and hash algorithm are within a pre-configured range if they are configurable: you do not want to verify MD-5 / SHA-1 based signatures anymore.

Note that ECDSA directly use the hash without padding (possibly even using fewer bits than is in the hash). No hash algorithm indication is (or can be) used within the signature format itself. The padding of RSA signatures generally contain a hash identifier that can be viewed modular exponentiation with the RSA public key.


Which assumption is stronger (p-BDHI) and DL?

p-BDHI is clearly at least stronger than DL: if you can break the DL problem, you can recover $s$, and then compute $e(P,P)^{1/s}$ (if you are in a group where inversion can be computed efficiently, which I think is always the case in known pairing groups).

On the other end, it is not clear that breaking p-BDHI could allow breaking the discrete logarithm problem, as, intuitively, breaking it only involve computing a group element and does not directly give a way to recover an exponent (this is informal as it could still be that p-BDHI allows too break the discrete logarithm problem, it does just seem far from obvious).


Can gnupg master key decrypt something encrypted with subkey?

No, the master private key cannot decrypt anything encrypted by a subordinate public key. Otherwise, it would mean that the master keypair is the same as the subordinate keypair.


What are the standard procedures in cryptanalysis to analyze unknown ciphertext?

Unfortunately Crypto.SE probably has very few lawyers, law enforcement officers, public policy experts, etc. Furthermore, Legal.SE doesn't exist yet. To further complicate the situation (at least in the US) the answer will probably vary from state to state.

So, I'm going to do the best I can, but you are probably best off either calling police or a lawyer in your jurisdiction.

Here is the deal, it is hard to prove a negative. Thus, I don't feel sufficiently knowledgeable to say no such protocol/procedure exists. That said, I don't know of one. I did find this flowchart for collecting digital evidence if you are in the US. Step one seems to imply that some knowledge of local/agency policies must be followed. But this deals more with evidence collection and not analysis.

My guess is that (at least in US), once you have the relevant network traffic and logs, your job is done. This is especially true if you have any motive/interest in seeing the offending party get in trouble.

So, assuming evidence is collected properly (since that is beyond the scope of your question) my guess is that the prosecuting attorney will hire an expert witness to examine the evidence and give testimony at a trial. They would probably also call you up to testify as to the collection procedures, etc.

Some added thoughts
The answer probably also depends on the exact protocols/software used. For example, if after an expert analyzes the ciphertext, they can determine that PGP or some other piece of software was used in which a long-term secret is used for encryption, a judge could order the defendant to disclose the encryption password or long-term secrets. At this point, no additional cryptanalysis would be needed. This would become more difficult if say TLS is used as the client often has no long-term secrets. I suppose a judge could force the party owning the server to reveal long-term secrets so decryption could take place (assuming the initial handshake was captured). If TLS, or whatever protocol used, is used in such a way that ephemeral keys are used, then even this would not work.


Secret key and Decryption oracle in the revised Fujisaki-Okamoto transformation

As you say, CCA proofs are actually reductions to underlying problems. In all CCA proofs that I can think of at the moment, the underlying problem is a weaker security notion for an "embedded" encryption scheme - e.g. Cramer-Shoup and friends use IND-CPA of ElGamal and Fujisaki-Okamoto uses OWE of the contained scheme.

The general proof strategy is to take a public key from your challenger and pass this to the adversary. This lets you use the challenger to process the two challenge messages to get the challenge ciphertext - since the only bit of information that your adversary gives you is which of the two challenge messages he thinks was encrypted, I'd guess that all CCA proofs will somehow have to "embed" the hard problem they're reducing to in the challenge ciphertext. After all, the reduction could compute everything else by itself.

This strategy of getting the public key from the challenger means you don't know the matching secret key, so the interesting bit of the proof is then how you handle decryption queries without it. This is certainly general to all CCA proofs that I can think of at the moment.


I want to make this clear: You're defining $E_K(m):\{0,1\}^{2n}\times \{0,1\}^n\rightarrow \{0,1\}^{2n}$ as $E_K(m):=G(K)\oplus m$. This construction is well-known in the literature. It can't be CPA secure because it is a deterministic algorithm. However as discussed in Katz' and Lindell's book Introduction to Modern Cryptography it is secure against passive eavesdroppers only observing a single messages.

As for your questions:

  What exactly is the attacker sending the plaintext into?

He sends the plaintext into the encryption function and gets the ciphertext in return. He doesn't learn $K$ at any point but learns encryptions using $K$. The process of acquiring the ciphertext to a given plain text is called "querying the encryption oracle for X"

  Does the attacker know what type of pseudorandom generator it is?

Yes, the attacker may know which primitive is used to instantiate the PRG and in a good system usually does. But this won't help him breaking the scheme as the security fully relies on the key(s) as per Kerckhoff's principles.

  But since the attacker doesn't even have the original cipher-text or
  the original key, what use is it for the attacker to keep on sending
  his own plain-texts and get back his own cipher-texts?

The usual CPA scenario indeed hands a challenge cipher text over to the adversary which he has to decrypt. (It's a little different but being able to decrypt always counts as a break).

Here's a quick outline on how to break the scheme:

Suppose you want to decrypt a cipher text $c$. You query your encryption oracle for a random message $r$. You'll get $c'=G(K)\oplus r$ in return. You are now able to compute $G(K)=r\oplus c'$. As $c=G(K)\oplus m$, you can obtain $m$ as $m=G(K)\oplus c=r\oplus c' \oplus c$.


Can I make fixed-length ciphertext with AES-256-GCM?

Can I make a fixed-length encryption output?

Sure you can - on encryption, you can first pad out the plaintext to a fixed length (and then perform the GCM encryption).  On decryption, you perform the GCM decryption, and then depad.

Obviously, the padding will need to contain a 'amount of padding I added' field (so that the depadding operation can remove the correct amount) - there are several obvious ways to accomplish that.  Someone looking at the ciphertext cannot determine anything about the contents, including the pad length.

Because GCM does integrity checking (that is, if someone modifies the ciphertext, GCM will detect it), you don't have to worry about padding oracle attacks.


Can I use NaCl's scalar multiplication functions for Diffie Hellman Key Agreement?

Yes.

The DH function is $$\operatorname{X25519}(n, p) := x\bigl([\operatorname{clamp}(n)] x^{-1}(\operatorname{decode}(p))\bigr)$$ with scalar multiplication $[\alpha]P$ on the curve $y^2 = x^3 + 486662 x^2 + x$ over the prime field $\operatorname F_{2^{255} - 19}$, where $n$ is 32-byte string representing a private key, and $p$ is a 32-byte string representing a public key.

Here $\operatorname{decode}(p)$ maps a 32-byte string into an element of $\mathbb F_{2^{255} - 19}$, and $\operatorname{clamp}(n)$ maps a uniform random 32-byte string into a uniform random integer in $\{2^{254}, 2^{254} + 8, 2^{254} + 16, \dots, 2^{255} - 8\}$—that is, an integer multiple of 8 between $2^{254}$ and $2^{255} - 1$.

As a DH function, this has the property that $\operatorname{X25519}(n, \operatorname{X25519}(m, \underline 9)) = \operatorname{X25519}(m, \operatorname{X25519}(n, \underline 9))$, where $\underline 9$ is the encoding of the standard base point, whose $x$ coordinate is 9, which means that both parties will arrive at the same shared secret.

The security contract requires that that you must hash the shared secret: use $H(\operatorname{X25519}(n, p))$.  Specifically, the security conjecture is that even if you reveal $\operatorname{X25519}(n, \underline 9)$ and $p \mapsto H(\operatorname{X25519}(n, p))$ for any $p$ of an attacker's choice, then the attacker must spend ${\sim}2^{128}$ bit operations to find any shared secret.  The security contract also requires that you never use $n$ for any purpose except the two crypto_scalarmult functions:

crypto_scalarmult_base(p, n) sets $p$ to the public key $\operatorname{X25519}(n, \underline 9)$.  You may publish $p$.
crypto_scalarmult(q, n, p) sets $q$ to the unhashed shared secret $\operatorname{X25519}(n, p)$, the secret shared between the private key $n$ and the public key $p$.  You must hash $q$ before using it.


Expectation Value of the Index of Coincidence

Expected Index of Coincidence usually refers to a language's expected index of coincidence (1.73 for English, or 0.067 if you're not normalising).

The formula in question is usually used to determine the length of the key ($t$) given the (measured) $IC$ of received cipher-text. $IC$ is the probability that two randomly-selected letters from the cipher text are identical.

Let $X=\{ x_1,x_2,x_3,...x_L\}$ be the cipher-text.  If we think the the poly-alphabetic cipher has period $t$, then we would expect each of the following:

\begin{eqnarray}
& X_1 =\{x_1, x_{t+1},x_{2t+1},...\}\\
 & X_2 =\{x_2, x_{t+2},x_{2t+2},...\}\\
& \vdots \\
 &X_t =\{x_t, x_{2t},x_{3t},...\}
\end{eqnarray}

to exhibit the same index as the plaintext ($\kappa_p$). So we can reconstruct $IC(X)$ as follows. Pick two letters at random, we want the probability that they match.

The probability that they are in the same $X_i$ is:

$$
\frac{tC(\frac{L}{t},2)}{C(L,2)} = \frac{L*(\frac{L}{t}-1)}{L(L-1)}
$$

The probability they are in different $X_i$s is:
$$
\frac{C(t,2)*\frac{L}{t}*\frac{L}{t}}{C(L,2)} = \frac{t(t-1)*\frac{L}{t}*\frac{L}{t}}{L(L-1)}
$$

If they are in the same $X_i$ then they are both enciphered using the same alphabet: so the probability is $\kappa_p$
If they are in different $X_i$s then they are enciphered using different alphabets, so we can assume they are randomly distributed: so the probability is $\kappa_r$

So the probability of two random letters matching is approximately

\begin{eqnarray}
IC(X) & \approx \frac{L*(\frac{L}{t}-1)}{L(L-1)}\kappa_p + \frac{t(t-1)*\frac{L}{t}*\frac{L}{t}}{L(L-1)}\kappa_r\\
     & = \frac{(L-t)}{t(L-1)}\kappa_p + \frac{(t-1)*L}{t(L-1)}\kappa_r
\end{eqnarray}


Messages of different lengths and one-time computationally-secret

This is already explained well, at a conceptual level, at a different question: Why is a non fixed-length encryption scheme worse than a fixed-length one?

To turn it into a formal proof, write down an adversary $A$ that breaks the security of $\Pi$.  You may want to first work out the attack at a conceptual level to make sure you are clear on how to attack $\Pi$; then review the definition of what it means for an adversary to break $\Pi$; then turn your conceptual attack into a fully specified algorithm $A$, and check that it does indeed break $\Pi$.


Exponential cipher theory misunderstanding

Exponential cipher is a symmetric-key algorithm, not public-key one. So you don't have any public and private keys. You only have one secret key and it's used for encryption of messages between people that know the key.

The security of exponential cipher is not in the computiation of $d$ from $e$, which is easily computable by EEA as you said. The security of this cipher lies at the principle of discrete logarithm problem, as well as Diffie-Hellman key exchange does.

The principle:

You have prime modulus $m = 2633$, secret key $e = 29$, where $\gcd(e,\ m-1) = 1$ so $e$ has inverse $\textrm{mod}\ m-1$ and you can compute your key $d$ for deciphering:

$d = |e^{-1}|_{m-1} = |29^{-1}|_{2632} = 2269$

The only thing you have to keep secret is the key $e$.

The encryption pattern is ($c$ for ciphertext block, $p$ for plaintext block) :

$c = |p^e|_m$.

So you can encrypt "TH" (T=19, H=07) as $c = |1907^{29}|_{2633} = 2199$.

To decrypt:

$p = |c^d|_m = |2199^{2269}|_{2633} = 1907$ = "TH"

Discrete logarithm problem:

Consider a possible attacker who has modulus $m = 2633$, block of ciphertext $c = 2199$ and corresponding block of plaintext $p = 1907$. What does he know:

$c = |p^e|_m$

$2199 = |1907^e|_{2633}$

which means $e =|\log_{1907}{2199}|_{2633}$

The discrete logarithm problem says that it's not possible to compute the key $e$ from this equality in reasonable time (for higher numbers of course).


Difference between XORing the IV and just pre-pending it to the plaintext before encryption with AES-CBC

If I got you right, you propose to encrypt IV and then run the same CBC-mode encryption using the encrypted IV; it just gives an adversary one more ciphertext block.


How are state wiretaps obtaining plaintext from encrypted transmissions?

Many reasons, including:

federal law requiring companies (e.g. telephone) to surrender encryption keys
interception before encryption (it's pretty easy to eavesdrop on keyboard input purely via electromagnetic radiation even several meters away)
MITM on an insecure channel (quite effective)
outright broken encryption algorithms
social engineering to recover key
Van Eck phreaking
weak keys
if all else fails, save the ciphertext for until you can subpoena the suspect and retrieve the key (but I guess this doesn't count)

etc... when you are being heavily monitored, purely cryptographic measures become too intangible and no longer suffice. You need to employ physical means to remain in a secure position.


Is there a client-side program to cryptography a HTML page and decode if correct password is writen?

If you put the text content of the webpage encrypted into HTML5 local storage, IndexedDB or embedded as a hex/base64 string in the web page, then you you could try something like TripleSec which would take your password, run a PBKDF and decrypt the content.

Or you can use one of the many JavaScript libraries CryptoJS, SJCL etc and do it yourself manually.

You should run the code as a local .html file on the filesystem or in a browser extension. Don't make the mistake of running the JavaScript code served up from the server because your security would only be as strong as the HTTP/HTTPS connection and vulnerable to MITM. Even HTTPS is not secure against some attackers.


Differential Privacy: What is the 'game' between data holder and adversary?

What differential privacy guarantees is that the query output communicates at most $\varepsilon$ bits of information about any individual (row). I now comment on each setting outlined in your question:

Independently repeated queries constitute several distinct releases. There is a straight-forward composition theorem (See e.g. Sect 3.5) that follows directly from the definition of differential privacy. It states that aggregate privacy-loss is at most the sum of the individual privacy-losses of the constituent releases. So, in this case, the results of $k$ repeated queries of an $\varepsilon$-differentially private mechanism taken together constitute a $(k\cdot\varepsilon)$-differentially private release. If the adversary is supplying the queries, a typical mitigation strategy is to enforce query limits. You may also need to worry about collusion.
This is a non-issue. Again, from the definition of $\varepsilon$-differential privacy, one can argue that after observing the contents of the release, an adversary's posterior remains point-wise close to their prior. Specifically, for any candidate "true" database, the ratio of the posterior to the prior lives in the range of $[e^{-\varepsilon}, e^\varepsilon]$. Thus, when $\varepsilon$ is small, this remains close to 1 and the adversary can only negligibly improve upon their initial guess.
This is valid and does not contradict the definition of differential-privacy which, even in this case, ensures that even if the adversary possesses a lot of knowledge of the database, say even all up to a single row, they remain unable to conclude about its presence or absence with certainty.

Just to make sure I answer the question as asked, one formulation as a game is the following: Fix a privacy mechanism, $\mathcal{A}$. An attacker chooses a pair of databases $D_1$, and $D_2$ that differ only by insertion (or deletion) of a single record, gives these to a 3rd party which randomly evaluates either $\mathcal{A}(D_1)$ or $\mathcal{A}(D_2)$ and returns the result to the attacker, without indicating which database was used as input. The attacker knows the exact contents of $D_1$, $D_2$, and is given a full specification of the privacy mechanism $\mathcal{A}$, so that the attacker can independently evaluate $\mathcal{A}$ over $D_1$, $D_2$, or any input of their choosing. The goal of the attacker is to guess whether the provided evaluation is $\mathcal{A}(D_1)$ or $\mathcal{A}(D_2)$.

A good mechanism is one where the attackers success over random guessing is remains small. Intuitively, if the attacker is unable determine the input database from the result even with knowing the complete contents of $D_1$, $D_2$, and being permitted full knowledge of and experimentation with $\mathcal{A}$, it must be that the result carries little information about the row in which the databases differ.


Secure hash function into $\mathbb{Z}_q$

You can define $ h' $ as $ h'(m) := h(m) \mod q $.

As long as $ 2^k $ is larger than $ q $ by e.g. 128 bits, the resulting function $ h' $ is (almost) equally distributed in $ \mathbb Z_q $.

For a suitable hashfunction $ h $ you might pick a SHA-3 with variable output size, like SHAKE256.


The capacity of the sponge construction refers to the section of the state that is not revealed to the adversary.

By effectively zeroing/truncating one side of the output of a permutation, it becomes difficult to apply the inverse permutation to the output and recover the original input: In order do so and end up back at the correct input, you would first need to recover the capacity bits that were not revealed. By ensuring that the capacity is large enough, it becomes computationally infeasible to guess what the capacity bits were and by extension computationally infeasible to recover the initial input to the function. This is a technique to make an invertible permutation into a one-way function.

The rate refers to the bits that are directly input/output into the permutation. A larger rate provides higher performance: Consider the extreme where the rate is only 1 bit - it would require $n$ invocations of the permutation to digest $n$ bits of data, which would be quite slow.

Conclusion

The capacity influences the security of the construction, while the rate influences the performance; Increasing one will decrease the other, as the size of the state is otherwise fixed.


Is there a way to optimize a linear scan while preserving anonymity?

Your problem has a contradiction: since there is no agreement between two parties anything that Bob should learn about $A$ is also possible to learn for a third party. So, there should be a kind of trapdoor for Bob to be able to learn something about $A$ which is not possible to learn without knowing that trapdoor.

Your problem can be defined as a kind of secure set intersection protocol. One of the most significant works on the set intersection and the usage of it for pattern matching is done by Carmit Hazay and Yehuda Lindell.

However, in their work Alice is the one going to learn the result, not Bob. However you can use the idea of using a key as a trapdoor and by using an OT protocol have alice to learn $PRF(A,k)$ and send it to Bob whom is able to locally generate $PRF(B_i,k)$ and find the result.


Why are computations (isogeny) in SIDH done in an extended prime field?

I am an inventor of SIDH. The computations take place in $\operatorname{GF}(p^2)$ just because all supersingular elliptic curves are defined over $\operatorname{GF}(p^2)$, up to isomorphism. It's just the way the mathematics works out. For general mathematical background, see any standard reference, such as Silverman "The Arithmetic of Elliptic Curves."


Which one of the Block Cipher modes is the best?

Personally I like the modes that support integrity checking and authentication, e.g. GCM, as they only require one key, and are not vulnerable to changes in the cipher text. One particular important problem area is padding oracle attacks, which are much more common than people seem to admit.

Note that GCM/AES is - just like CTR - a block cipher in stream cipher mode; Basically GCM consists of a GMAC and CTR combination.

GCM is supported by XML encryption v1.1 (XML encryption by itself is very vulnerable to padding oracle attacks). There is also http://tools.ietf.org/html/rfc5288 which describes the use in TLS and http://tools.ietf.org/html/rfc5084 which describes the use in CMS.

GCM seems to have some support, e.g. Java 8 introduces GCM in the standard Java Runtime. For Java 7 and below it is required to use an external provider such as Bouncy Castle.


Line by line encrypted logging stored with iv/salt/iterations. How safe is it?

Is it safe to store all of that information at the same place?

All the information (salt, pbkdf2, iterations, iv, GCM tag, encrypted payload) is listed can be considered as public information. We already consider that an attacker has the knowledge of all of these but the encryption key by the Kerckhoffs's principle.

  A log file will typically contain hundreds/thousands of such entries. Does the encryption get significantly weaker as entry count increases?

The IV is generated randomly. If the random generator is weak then it might cause an IV reuse and this is a big security issue under the same key for AES-GCM due to the underlying CTR mode and that can reveal the plaintext by crib-dragging and even more it can cause forgeries.

The IV can be generated with a counter or LFSR as recommended by NIST 800-38d  8.2 IV Constructions so that it will never repeat. A better idea is half counter/LFSR half random.

$$\text{nonce} = \text{random} \mathbin\| \text{LFSR}$$
This can prevent a system failure issue that the last stage of the counter/LFSR is not stored then it can cause a nonce repetition. Although one may repeat the counter/LFSR stage, the new random will prevent the IV reuse issue.

AES-GCM has IND-CCA2, it is not getting weaker especially with a 256-bit key size. However, it might be a good idea to change the key over a period of time. This can be done using a master key and derive keys form using HKDF or using different salts for PBKDF2.

  The timestamp has to be stored in cleartext, for practical reasons. However, I would like to validate that it hasn't been tampered with. What's the best approach for this?

The Authenticated Encryption (AE) is also known as Authenticated Encryption with Associated Data (AEAD). You can provide the timestamp as associated data and the AES-GCM will use it in the integrity part. That is designed for such purposes. This can be formalized as

$$(C,T) \leftarrow \operatorname{AES-GCM-}\mathcal{E}^{N,A}_K (M)$$ where

$\mathcal{E}$ stands for encryption, $K$ stands for key, $N$ stands for the nonce, $A$ stands for the associated data. C is the ciphertext and T is the authentication tag. Similarly the decryption;

$$(M | \perp) \leftarrow \operatorname{AES-GCM-}\mathcal{D}^{N,A}_K (C)$$ where $\mathcal{D}$ is the decryption and $\perp$ is the tag mismatch halt.

update per comment

  What if the attacker had one line of that log file, and the corresponding cleartext payload. For example, knowing that line #1 of the example above says "Initial log entry". Does that compromise the key?

AES is primitive and it is supposed to be a pseudorandom permutation. It can achieve IND-CPA or IND-CCA or authenticated encryption using by using the appropriate mode of operation together with AES.

We assumed that one has solved the IV reuse, then in CTR encryption of AES-GCM, we have;

$$C_i = P_i \oplus \operatorname{AES}(k, \text{nonce}\mathbin\|\text{counter}_i) $$ and that means the attacker will know the plaintext and ciphertext blocks. This is actually the Known Plaintext Attack (KPA) and AES has believed to be secure about this. You can also read here the possible attacks on AES-128 and AES-256 far from it.


Can the HMAC of a pre-hash be considered equivalent to an HMAC of the message?

TLDR: Such pre-hashing is weaker, and slower on a standard computer.

Most serious security problem: in order to break the MAC with pre-hasing, it is enough to find two different messages with the same SHA-256 hash, and that's an offline attack (it requires a single query to a MAC oracle/device knowing the key). Such breaking of SHA-256's collision resistance could become possible¹ due to some combination of cryptanalytical and technological progress, like that happened for SHA-1. Absent cryptanalytical breakthrough and discounting quantum computers useful for cryptanalysis, that costs $\approx2^{129}$ compression functions (using distributed Pollard's rho with distinguished points). Contrast with the best known attacks against HMAC, which require a much less realistic $\approx2^{128}$ online queries (performing $\approx2^{129}$ compression functions), or a whopping $>2^{256}$ offline compression functions (for 256-bit key).

For just that reason, HMAC-MD5 remains practically secure when MD5 collision is totally broken (collision with chosen prefix is easy), and HMAC-SHA-1 remains practically secure when SHA-1 collision is very broken (collision is easy, collision with chosen prefix is feasible).

Another explanation of these facts: we have argument that HMAC is secure for weaker properties of the hash's compression functions than required for argument of collision-resistance of the hash: Mihir Bellare, New Proofs for NMAC and HMAC: Security Without Collision-Resistance, originally in proceedings of Crypto 2006, republished in Journal of Cryptology, 2015.

  Pre-hashing is preferred due to the reduction in HMAC validation time on large messages as only the 32byte pre-hash would need to be run through HMAC validation (vs. the entire 1kB message).

No, the opposite, pre-hashing is slower on a standard computer. For a 1024-byte $m$ an $k$ at most 512-bit, $\operatorname{HMAC-SHA-256}(k,M)$ first hashes 512+8192 bits (18 blocks after padding), then 512+256 bits (2 blocks). Whereas $\operatorname{HMAC-SHA-256}(k,\operatorname{SHA-256}(M))$ first hashes 8192 bytes (17 blocks), then 512+256 bytes (2 blocks), then 512+256 bytes (2 blocks). That 2 blocks more, and one more each of hash initialization and finalization. Optimizations for repeated use of the key apply equally to both variants.

The one situation when pre-hashing would result in a speedup is when HMAC itself is implemented in a relatively slow secure device (like a Smart Card or HSM) in order to keep the key protected. In that case, pre-hashing is reasonable, and using SHA-256 for that is not unreasonable. But if performance matters, SHA-512/256 or SHA-384 is probably as better choice for the pre-hash: these hashes are faster on modern CPUs, the secure device won't make more SHA-256 compression functions, and (for SHA-384 pre-hasing, which arguably is more secure than either SHA-256 or SHA-512/256) performance overhead of transmitting 128 extra bytes to the security device is low.

¹ I'm not saying that's likely in next two decades; rather, the contrary.


AES confused about how ShiftRows() step works

The entire AES algorithm uses column-major order. So the first four elements are actually the first column, and not the first row.


Secret-suffix MD5 as secure PRF (not MAC)

The collision resistance of MD5 is fully broken, for 2 rounds, or even just 1 round. If follows that we can exhibit distinct 1024-bit or even 512-bit  $x_0$, $x_1$ such that for any $k$, $\operatorname{MD5}(x_0||k)=\operatorname{MD5}(x_1||k)$.

This allows to make a near-perfect distinguisher between the PRF (family) parametrized by $k$: $x\to\operatorname{MD5}(x||k)$, and a random oracle; thus breaking that PRF.


Questions about using PRF to construct PRG

We don't directly answer homework questions, but will give hints.
An attacker is assumed to have control over all non-secret inputs. The key is secret, the block is not. This answer has a good definition of a PRG: in simple terms a PRG is a function that takes a fixed-length secret input seed bitstring, and outputs a longer bitstring which cannot be distinguished from a random bitstring with non-negligible probability.

A. $G(x)=F_{x}(0...0)$, where x is a 128-bit input key.

Does the attacker control any of the inputs? Can the attacker distinguish the output from that of a random function with non-negligible probability (ie, are there any observable patterns in the output)? Is the output longer than the input?
The only input variable is a secret key. No extra patterns get added to the output. How long is the output?

B. $G(x)=F_{x}(0...0)||F_{x}(0...0)$, where x is a 128-bit input key.

Same questions.
The only input variable is a secret key. The output repeats some sequence twice. How long is the output?

C. $G(x)=F_{x}(0...0)||F_{x}(1...1)$, where x is a 128-bit input key.

Same questions.
The only input variable is a secret key. Does the output have any extra patterns? How long is the output?

D. $G(x)=F_{0...0}(x)||F_{1...1}(x)$, where x is a 256-bit input data block.

Same questions.
The only input variable is a public data block. Does the output have any extra patterns? How long is the output?
There's a missing option that continues the pattern: E. $G(x)=F_{0...0}(x)||F_{0...0}(x)$, where x is a public 256-bit data block.
If you can answer the A-D, E should be trivial.


Why are HOTP and TOTP implementations all using 6 digits and not more?

It is for user experience reasons, as you surmise, but the security is not compromised as much as you may think.

Most implementations use 6 digit HOTP/TOTP schemes and design their implementation of the scheme to give them a security level they are comfortable with.

For HOTP, the key parameter that allows 6 digits to be secure enough is the throttling behavior. When combined with a sensible look-ahead window size $s$, the probability of a brute force attack succeeding is low enough as the account or client will be unable to attempt a large number of guesses.

The throttling argument for TOTP is the same, as it is based on HOTP. The security calculation differs but the same principles apply.

The converse of course is that inappropriate selection of look-ahead/behind or throttling behavior does indeed open up a 6 digit decimal OTP to brute force attacks with high probability of success.


What is the procedure to proceed towards breaking a cipher text when the process of encryption is not known?

Cryptanalysis is not a standardised process with recipes to decrypt encoded messages...it has a lot to do with circumstances such as the amount (length) of ciphertext available, in what context it was retrieved (is it likely to be part of an authentication protocol, or human communication) and so forth. It often involves creativity, and lots of trial-error and patience since it is obviously a task that is difficult by design.

If there is absolutely no context information, the analyst has little choices but to closely examine the ciphertext for any kind of patterns/structure, and identify anomalies to work on. This could include things like

Frequency of characters
Appearances of combinations (which might originate from the same plaintext words)
Ciphertext structure (especially if several messages have been received): do there appear to be checksums, is the length fixed,
etc.

Note that the above is by no means exhaustive nor very helpful for solid encryption schemes. It is just to address your question and point out why it can not be answered - there simply is no standard procedure.

More importantly, most encryption nowadays does not rely on secrecy of the algorithm. Cryptographic schemes can and should be publicly known, so that the public can point out and correct potential weaknesses, which increases resource asymmetry between the "defenders" (developers) and adversaries, and thus makes attacks less likely. This ultimately leads to more public trust and acceptance of the method.

So it is no problem at all when a cryptanalyst knows that you used RSA etc. to encrypt your message, it is still infeasible to "break" the ciphertext, as you put it.


ECB is weak because a given 128 bit input block maps to the same encrypted output block. The only thing you can do is look for matches between blocks of the encrypted flag and outputs in the known plaintext ciphertext pairs file.
Essentially for each 128 bit chunk of ASCII text in the flag E(plaintext)=ciphertext. The known plaintext ciphertext pair file is essentially a big table of E(plaintext)=ciphertext for a bunch of plaintext ciphertext pairs. If you find one of the encrypted flag blocks in that file:
8cb78d34edfec9db1fa4a044f14c06cd
5d9aa8a4fece263c439c5fa62dd1feda
df757d79fa6a28069ddcba4ca624c969
4559483254896625392f70bf7df4dd66

You have the decryption for that block. Just ctrl-f for these values and assemble the decrypted chunks to find the unencrypted flag. They have to be there for the CTF to be solveable.


SHA-512 - How difficult is it to find a hash digest beginning with at least twelve zeros?

First, we need to model SHA-512 as uniform random.
Start hashing random values.
In hex we have 4-bits

We would expect about 1 in $2^4$ values to have a hash-value with 0x0 at the beginning.
We would expect about 1 in $2^8$ values to have a hash-value with 0x00 at the beginning.
We would expect about 1 in $2^{12}$ values to have a hash-value with 0x000 at the beginning.
We would expect about 1 in $2^{16}$ values to have a hash-value with 0x0000 at the beginning.
...
We would expect about 1 in $2^{48}$ values to have a hash-value with 12 hex zeroes at the beginning.

So we can say that we expect $\dfrac{2^{512}}{2^{4\cdot k}}$ values will have leading $k$ hex zeroes.

Little experiments
For random inputs the SHA-512 hashes with leading zeroes in hex;

random sample
none
1
2
3
4
5
6
7
8

1M
937670
58485
3604
225
16
0

10M
9375898
584890
36824
2231
149
8
0

100M
93752595
5856572
366283
23019
1446
75
9
1
0

1B
937501048
58591757
3663483
228262
14501
881
66
2
0

$1B \approx 2^{30.89}$ and to see 12 leading zeroes, the experiment must go to $2^{48}$ and that needs still $2^{18}$ more time. It is quite doable with a single CPU, though parallel processing is possible, too. Note that this is a Python experiment and took ~22 minutes for 1B.
For a CPU this may be hard to achieve since SHA-512, although a fast hash function, is still not a simple function to evaluate. If you have a GPU like GTX 1080 then you may reach $2^{48}$ SHA-512 hashing around 36 hours and if you have GTX 3080 then you may need 18 hours.


Are there any practical differences between running a PRNG on a subset of bits from an RNG compared to running the RNG?

In 99% of cryptography there is no practical difference between your cases as long as $ |seed| = \frac{n}{2} \ge 128$.  Computational indistinguishability means that the streams from both cases will appear properly random. Our current knowledge is insufficient to invert a good well seeded CSPRNG (your PRNG). Information theory suggests that inversion can't be ruled out, but we can't do it as yet. Perhaps tomorrow or the day after. See P=NP and Kolmogorov/algorithmic complexity.

The missing 1%.  For the truly dedicated who use one time pads (OTPs), there is a huge difference between the cases.  Information theory dictates that case 1 can create a OTP.  Case 2 specifically requires $ |bits| < \frac{n}{2} $.  Otherwise the output is theoretically invertible. In this case though, the above theorem implies that the output from PRNG need only to not introduce bias.  It need not be cryptographically secure, nor even a dedicated PRNG. A simple random matrix will do.  But it begs the question of why bother if you already have a functional TRNG running at a similar rate?

Consequently, your RNG is more random than your  PRNG from a certain perspective.  It's the same differentiator that separates /dev/random from /dev/urandom in blocking *nixes.


Mathematically speaking, we cannot. There is no proof that elliptic curves are actually "secure". But the same apply to about all other cryptographic algorithms, so we have to make do with the next best thing: since we cannot prove that any curve is "secure", we'll use curves that we do not know how to break (and not for lack of trying).

That last part is very important: we gain some level of trust in the robustness of a curve through that curve being exposed to the fierceness of many cryptographers for a long time. If a curve was thus specified and used and attacked for years, and none of them succeeded at even making a dent in it, then we begin to say that the curve is "probably strong"; or, similarly, that if that curve has weaknesses, then these weaknesses are not obvious. This is about the best we can achieve.

An important consequence is that only fully specified, standardised curves that have been analysed for years can claim to be "secure" in that sense. So, in practice, use one of the standard curves. Which means one of the three most common NIST curves (P-256, P-384 and P-521; see FIPS 186-4), or one of the two "newer" (but nifty) curves Curve25519 and Curve448 (see RFC 7748).

That being said, we can list a few basic criteria that "secure" curves must fulfill. Matching all these criteria does not guarantee security in any way, but if any of them is not matched, then cryptographers will laugh and mock it.

The curve order (number of points on the curve) must be a large enough prime integer, or a multiple of a large enough prime integer. "Large enough" means here that the equivalent of discrete logarithm for elliptic curve can be solved in time $O(2^n)$ for a prime of size $2n$ bits. Since we want at least "100-bit security", that prime integer should have at least 200 bits in length (cryptographers are suckers for powers of 2, so traditionally we aim for "128-bit security"). Implementation in many contexts is made easier if the curve order is prime, and not only a multiple of a big prime, so if a curve order is not exactly prime, it better have a good reason for that.
The curve should not be anomalous or singular or supersingular. These are special curves with additional mathematical property, which may thus lead to easier attacks. Note: for some specific contexts (pairing-based cryptography), we have to use special curves, and the possible weaknesses must be compensated for with, basically, use of bigger curves (hence slower).
The embedding degree of the curve must be large enough to discourage attacks that leverage the same mathematics as pairings (e.g. MOV attack). If the curve is defined in a finite field of size $q$, and the curve order is (a multiple of) the big prime $r$, then the embedding degree is the smallest integer $k \gt 1$ such that $r$ divides $q^k-1$ (this is the Balasubramanian-Koblitz theorem). The MOV and FR attack turn discrete logarithm on the curve (work factor $O(2^{r/2})$) into multiplicative discrete logarithm in a finite field of size $q^k$, where subexpoential algorithms are known.

In general, unless you use a special curve (e.g. supersingular) or deploy some extensive mathematical juggling aiming at generating a curve with a small embedding degree, a "random" curve will have an extremely high embedding degree ($k$ will have about the same size as $r$). One widespread ECC standard (ANSI X9.62) mandates that, when generating a curve (assuming you want to do that, but, as explained above, this is probably a bad idea), you should verify that $k$ is greater than $100$ (i.e. you check that $r$ does not divide $q^k-1$ for all $k$ from $2$ to $100$).
Since a curve is defined with an equation over a specific field and with a couple of extra parameters, there is room for inserting arbitrary values. Cryptographers don't like arbitrary values. If somewhat "magic" constants must appear, they prefer these values to be nothing up my sleeve numbers. We don't know how we could somehow "rig" a curve with special parameters, in a way which cannot be detected (e.g. with a low embedding degree), but in all generality we prefer it when such rigging cannot happen because values are not arbitrarily chosen.
Implementing elliptic curve securely is hard. For instance, the "new" curves Curve25519 and Curve448 are easier to implement securely for several reasons, the two main being:

These curves are derivative from Montgomery curves and thus admit an efficient point multiplication algorithm that is "naturally" constant-time (it won't leak secret values through varying execution time or memory access pattern).
Each of these curves is actually two curves, where any patterns of bits will be interpreted as a point on one of the curves or on the other. This avoids the need to perform point validation and make tricky decisions about the handling of invalid input data.

Thus, a "secure curve" must be such that it makes it easy, or at least not impossibly hard", to implement computations in a secure way. On that criterion, the NIST curves (P-256...) are "less secure" than Curve25519 and Curve448. Note, though, that even when a curve is easier to implement securely, that does not mean that it is easy in absolute terms. For about the same reason that you should not invent your own curves, you should not either make your own implementations. And if you use an implementation which was done with great care and was reviewed by many competent people, then the difference between curves in that respect is mostly nullified.

It shall be noted that while we want to avoid "special structure" in curves, one specific special structure is especially alluring in terms of performance: choosing a base field that promotes efficient computations. For instance, Curve25519 is defined in the field of integers modulo $q = 2^{255}-19$. This value being very close to a power of $2$, this makes computations much faster. This is the point where cryptographers tend to throw away caution for the sake of good benchmarks. We do not know how a special base field structure could be leveraged to break discrete logarithm faster; but we declared anathema on random parameters with no better justification, so it is kinda weird that we allow special fields and not arbitrary curve equation parameters. My gut feeling (which is thus scientifically unsubstantiated) is that if the standard curves ever get into cryptanalytic trouble, this will be due to special base field structure. But it won't prevent me from sleeping at night.

If any of the above seemed obscure, then go read this book.


There's no way to reduce the J-K flip-flop to a boolean function, much less a 2-input boolean function. The J-K flip-flop is a 3-input block with a clock input in addition to inputs $J$ and $K$. Its output(s) is/are not a boolean function of these inputs, because past output(s) matters to future output(s).

If we want to model a J-K flip-flop using boolean functions, we can do this in several ways, including two identical 3-input functions $Q(I,B,C)=(I\cdot B\cdot C)|\bar B$, where $I$ is $J$ for one function and $K$ for the other, $B$ is the output of the other function, and $C$ is the clock, as per this schematic:

Knowing the initial state $Q$, and the inputs $J$, $K$, $C$, this allows predicting future $Q$, except for some inputs where $C$ changes near-simultaneously with either $J$ or $K$.

The article considers a J-K flip-flop with single output, sharing its clock input (made implicit) with the sources feeding its other two explicit inputs $J$ and $K$. The model given is:

a gated D latch with single output (as used for individual bits in a Linear Feedback Shift Register);
and a (boolean) feedback function, which 3 inputs are $J$, $K$, and the output.

The state (noted $R_n$ in the article) of the output $Q$ of the J-K flip-flop at a certain clock period $n$ is
$$R_{n+1}=((J\oplus \bar K)\cdot R_n)\oplus J$$
(as can be deduced from any proper model of the J-K flip-flop, including the above model as two boolean functions). And thus, in a modern exposition, anything using the J-K flip-flop in this clock configuration can be readily expressed in the framework of Non-Linear Feedback Shift Registers.

In the shared clock configuration of the article, the J-K flip-flop's feedback function given above is a 3-input, 1-output boolean function $F(J,K,R)=((J\oplus \bar K)\cdot R)\oplus J$, where the additional input $R$ is the previous output. The truth table for $F$ can be condensed from the normal $2^3$ entries to
$$\begin{align*}
J&K&F\\
0&0&R&\text{ unchanged}\\
0&1&0&\text{ clear}\\
1&0&1&\text{ set}\\
1&1&\bar R&\text{ toggle}\\
\end{align*}$$

This function $F$ is balanced (that is, half of the $2^3$ outputs are 1), and $F(J,K,R)\oplus R$ is also balanced. $F$ is non-linear w.r.t. each of its inputs (that is, the XOR of the output with any input is not a function of the other inputs).

$F$ is not correlation-immune: the output is biased towards $J$, and towards $\bar K$. This indeed allows an attack in the context of combining LFSRs, but replacing $F$ with any 3-input boolean function can't improve this; enumerating the 256 such functions, we would find some issue with the output (ordered from worst to least):

severely biased (that's why we want $F$ balanced);
severely correlated to the previous output (that's why we want $F(J,K,R)\oplus R$ balanced);
equal within polarity and a clock delay to one of the two inputs, which (being a LFSR) is efficiently predictable using the Berlekampf-Massey algorithm;
equal within polarity and a clock delay to the XOR of the two inputs, which is efficiently predictable by the same method, because the XOR of the outputs of any two LFSRs is identical to the output of another LFSR of size at most equal to the sum of the sizes of the two LFSRs;
just as correlated with the inputs as in the J-K flipflop case.

Note: I'm not familiar with the definition of bent and semi-bent functions, and won't attempt to classify where $F$ belongs, but that should be trivial from the definition of bent and semi-bent, whatever that is.

Note: The J-K flip-flop seems to be one of the simplest two-inputs combiner with memory worth consideration in the framework studied by Frederik Armknecht and Matthias Krause in Algebraic Attacks on Combiners with Memory (Crypto 2003).


In textbook RSA with low public exponent, how big does a random message needs to be?

Related messages. If you have (the encryptions of) a pair of messages that differ by a known fixed difference, then the Franklin-Reiter related message attack can be used to recover both messages.  The running time of the attack is something like $O(e^2 n^2)$.  This does not apply if the messages are independent and there are no known relationships between them.

Coppersmith's theorem. Coppersmith's theorem might be relevant.  Roughly speaking, it says that if you have a monic polynomial $f(x)$ of degree e, then you can find all solutions to $f(x)=0 \pmod N$ satisfying $0 \le x < X=N^{1/e}$ in polynomial time, using a lattice technique.  By defining $f(x)=x^e-C$, this can be used to recover $M$ if it is known that $M<N^{1/e}$.  Therefore, it looks like this does not improve upon the trivial $e^{\textrm{th}}$ root extraction root method.  I don't know if the attack can be improved by continuing to use his lattice methods even for a larger value of $X$.

Square-root attack. There is also a meet-in-the-middle style attack whose running time is $O(2^{m/2})$.  If $e=3$ it will be dominated by other attacks, but it may be more relevant for larger values of $e$.  The meet-in-the-middle attack is described by Boneh et al. (see below); basically, we hope that $M$ can be written as $M=M_1 M_2$ where $M_1,M_2 \le 2^{m/2}$, and we try to find $M_1,M_2$.  To find them, we build a table of $C/M_1^e \bmod N$ for all candidate $M_1$ values, then for each candidate at $M_2$, we look up $M_2^e$ to see if it is present in the table.

This is described in Section 5 of the following paper:

Textbook ElGamal and RSA Encryption are Insecure, Dan Boneh, Antoine Joux, Phong Q. Nguyen, ASIACRYPT 2000.

Published work. A good summary of the above attacks can be found in this paper:

Twenty years of attacks on the RSA cryptosystem, Dan Boneh, Notices of the AMS, vol 46 no 2, pp.203-213, 1999.


Enabling Oblivious Access Control via Function Encryption

Potential Solution?

Using Functional encryption, a trusted authority with a master secret key ($msk$) and public key ($pk$) would generate a "functional decryption" key ($sk$) from a participant's policy ($k$). Each participants would be provided the $pk$ and relative $sk$, where $sk$ is bound to the participant's public identity via a signed document.

For a client and server session between two participants, the client would first use $pk$ to encrypt its own intended API request ($x$) to generate the ciphertext ($c$). After securely connecting and receiving the server signed document, the client would verify the server's ownership of $sk$. Next the client would check the server is authorized to receive the API by using the server's $sk$ to calculate a policy function of the request $c$ encrypts. If the function returns True, then the server is authorized to receive the API request, otherwise False is returned. If True, the client then transmits $x$ and its own $sk$ document for the server to verify similarly, checking the client is authorized to send the API request before fulfillment.

Extension?

To prevent recipients of a participant's $sk$ from probing what additional API permissions where provisioned within, e.g. by brute force enumeration of API requests, perhaps either the encryption or decryption algorithms could altered require a third argument ($sk'$). While also generated from $k$, $sk'$ is instead kept secret to the owner, while additionally remaining a non-substitutable argument for (public) $sk$ and vice versa. The result being that a return of True could only occur if the policies in $sk$ and $sk'$ coincide such that the permissions for the intended client and server for the API request $x$ are all permissible, otherwise False is returned.

This would prevent a malicious actor from gaining any more knowledge about the permissions of other participant's, aside from what could already be inferred from authorized exchanges using the identity and $sk'$ from the participant it has already compromised. Perhaps a another approach could necessitate some sub key or token from the other participant that would authorize the policy "background" check upon the received $sk$ for only the permission relevant for the API in question. However this would require the client to divulge the API request to the server to receive such a token before even vetting the server, itself a circumvention of access control that would perhaps negate the advanage.

In lieu of three argument function encryption algorithms unfeasible, perhaps a similar effect could be achieved by necessitating a cascaded calculating of function upon $c$ and then $c'$ using $sk$ and $sk'$ once in either of the two stages? E.g.

$$
(pk,msk) \leftarrow Setup(1^{\lambda}) \\
sk \leftarrow Keygen(msk, k) \\
{sk}' \leftarrow Keygen(msk, {k}') \\
c \leftarrow Enc(pk,x) \\
{c}' \leftarrow Dec({sk}',c) \\
F(({k}',k),x) \leftarrow Dec({sk}',{c}')
$$


Where is the key in white-box AES cryptography?

In whitebox cryptography the attacker is supposed to have access to every detail of the computation and the goal of this implementation is to protect the key, to -usually- avoid it is used on a classical no-whitebox implementation on a different platform.

The goal is that an attacker having access to the whole computation and intermediate values cannot achieve a bigger knowledge of the encryption key as he would have a black-box access (only input/output for all input of his choice).

The perfect way to create a whitebox implementation would be to tabulate the AES: for a given key, one takes all the possible input blocks, compute the encryption on a trusted machine and put the output on a table. In this scenario an attacker would have access only to the input/output and the computation has been done elsewhere. But, of course, this table would be ${HUGE}$ (e.g.: for the AES: $2^{128} \times 128$ bits, I don't even know how to write this quantity, but could be approximated by $2^{92}$ Terabytes). So, a typical solution is to use several lookup tables (noted as LUT) in a networked way. This allows to build an implementation in a less of a Megabyte (700k), even if this size is quite a lot in respect to a standard, no-whitebox implementation. Resume of white-box applied in AES algorithm (slides 18 - 24).

So you are not going to see the key in a whitebox implementation, the key is cut, smashed, embedded in all the tables used to compute a single encryption.

That also means that the key is not loaded somewhere during the computation but has to be embedded before shipping the implementation, and that when one needs do change/update the key, he has to ship another implementation (or on other set of tables).


Help me understand how to do a crypto assignment about AES/CBC

For the CBC mode the encryption and decryption equations are as follows;

CBC encryption;

\begin{align}
C_1 &= E_k(P_1 \oplus IV)\\
C_i &= E_k(P_i \oplus C_{i-1}),\;\; 1 < i < nb,
\end{align}

CBC decryption;

\begin{align}
P_1 =& D_k(C_1) \oplus IV\\
P_i =& D_k(C_i) \oplus C_{i-1},\;\; 1 < i < nb,
\end{align}

But I'm not 100% sure what "D" actually is (yes, decrypt... but is it xoring? Something else?).

The $D$ is for Encryption and $E$ is for encryption, and $nb$ is the number of blocks.

If my understanding is correct (the decryption of the current layer being just xoring c[i] with the key), then it could be an implementation problem?

The key is given to AES to produce the encryption and decryptions, we don't x-or with the key, that is OTP or Vigenere.

I'm also a bit unsure about xoring the key with the blocks. I know that IV is supposed to be the same length as the blocks (16) but the key is 32 bits. Do I pad or repeat the blocks so they are 32 bits? Do I use the first 16 bits of the key?

AES has 128-bit block size regardless of the key sized those are 128,192, and 256. Therefore AES can support 128 bit IV/nonces. 128 is 16-bytes and 256 is 32-bytes.
A message to be encrypted with CBC mode needs proper padding like PKCS#7 padding and the padding is performed on the last block. The padding is the missing bytes are filled with the count of the missing bytes, if the last block is full then a new block is needed that is filled with 10. And remember CBC mode is applicable to the padding oracle attack due to improper uses of the padding error and lack of encrypt-then-mac.
The key size must be given to you, and the key size cannot be detected except in the side-channel attacks where if one can see that encryption is 40% slower than AES-128 then it must be AES-128.


Is AES-GCM suitable for per chunk encryption?

The limit is on a per-key:nonce basis. As long as the key or nonce are changed between messages before the limit, there will not be any problems. Different users are using different TLS sessions (which uses 96-bit nonces), which means different keys and nonces. From Wikipedia's page on GCM:

  GCM has been proven secure in the concrete security model. It is secure when it is used with a block cipher that is indistinguishable from a random permutation; however, security depends on choosing a unique initialization vector for every encryption performed with the same key (see stream cipher attack). For any given key and initialization vector combination, GCM is limited to encrypting 239−256 bits of plain text (64 GiB). NIST Special Publication 800-38D includes guidelines for initialization vector selection.

If TLS is not the protocol in use, then it depends on a few factors such as the size of the nonce (bigger is better) and whether or not it is random or sequential (sequential is better). In general, a competent cryptographer will not select insecure parameters. If you are trying to design your own encryption utility, you should be using an easy to use and foolproof library, such as libsodium.


Could this alternative hash based MAC construction be as, or even more secure than an HMAC?

Security

The level of security is likely to depend on the cryptographic primitives - the actual hash function and cipher - used. It is very likely that you can construct a function that is insecure, e.g. where the cipher is used for both the hash function an encryption. So you need to prove that the hash function and the encryption primitive are not influencing the security, even though they are using the same key. It is much easier to use a single PRF or PRP and prove that secure. Using one function also greatly simplifies implementations.

Implementation issues

An implementation issue is that intermediate hash states are often not defined or clear. SHA-1 and SHA-2 do have "logical" intermediate states after a block is hashed as the hash output is basically (part of the) final state. The final state for these hash functions does not significantly differ from the intermediate state. This is not obvious for other hash functions. This is for instance the case for Keccak - the winner of the SHA-3 contest - as well as most other SHA-3 candidates. Using an intermediate hash state should therefore be avoided.

Expected properties

I'll iterate over the expected properties in order:

  It may be faster than an HMAC in practice, especially for shorter messages (modern hardware accelerated encryption is up to 5x-10x the speed of hashing).

Usually performance is less of an issue for shorter messages. I would argue that it is only faster for shorter messages; the effect on larger messages will be negligible. Even then, it would require the cipher implementation to be cached (and in the case of e.g. Java, optimized) in addition to the hash function.

  Encrypting the hash state in stage (2) is a psuedo-random permutation, rather than just a PRF and so may have stronger security guarantees (this is the job of the more math-oriented people [i.e. you guys/girls] to try to analyze though).

A hash function especially within HMAC already provides very good security guarantees. It remains to be seen if using a PRP would have any advantages; I would expect it to be less secure.

  A practical advantage of HMAC, though, is that it could work with arbitrary “secrets”, that are not necessarily psuedo-random, but this construction would only work if the “secret” is an actual key associated with some cipher (though the “secret” could be hashed of course, to yield a key) - this may not be a significant limitation in practice though, as in most cases it is used with an actual key.

One of the more annoying aspects of CBC based MAC's is the non-variable key size. This is for instance rather annoying when using the MAC as building block for a key derivation function (KDF). So this is - in my opinion - a significant limitation.

CPU hash acceleration

Note that there are also CPU level optimizations for hash functions. Well known ones live in the Intel SHA extensions, the VIA padlock security suite, the Sun Ultra-Sparks...


An attack an encrypted classified data in a theoretical situation

Well, given that (for whatever reason) they cannot try to overcome you with either rubber hoses or large bags of money, the next best options they would have are:

A brute force search on the password (you didn't state this, but I assume that the encrypted data is protected by a password which is the only unknown input to the KDF); if we're talking about a major TLA who is willing to throw all their resources at it, I'd expect them to be able to check all (circa) 12 character passwords (and many longer ones that don't look like line noise).
Do a black bag job on your home/work, and see if they can recover the plaintext (or a clue for the password)

Now, XTS does have weaknesses (if you update a disk block and modify only some of the 16 byte AES blocks, the attacker can see which blocks you updated); that weakness wouldn't apply here.  None of the other components are amenable to cryptanalysis.


Can you tell me how to create a cipher please? just a little simple one

I was in your shoes about a year ago. The biggest help to me was Kahn Academy's crypto lessons (https://www.khanacademy.org/computing/computer-science/cryptography). The best thing it did for me was to define what many of the terms were without going too deep into the math.
To directly answer your question, the most basic cipher is letter substitution: A = D, B = E... So to create the cipher, add three letters to each plaintext letter. To get the plaintext back, subtract the same number from each letter. Tada! You have a cipher text!


Asymmetric code signing also tied to a device

This is sometimes called a hierarchical signature scheme or a blinded signature scheme.  Examples of the idea are being considered or adopted in Tor for next-generation onion services, in Bitcoin BIP32 for cheap many-address single-private-key wallets, and possibly by the IETF for standardization.  There was a good summary discussion with references on the CFRG mailing list a few months ago.  But the idea is not currently standardized, and implementations aren't littering the roads like implementations of ordinary signature schemes are.

$\newcommand{\Z}{\mathbb{Z}}$The basic idea of an elliptic-curve signature scheme using an order-$\ell$ group of $k$-rational points of an elliptic curve $E$ is that a private key is a secret scalar $a \in \Z/\ell\Z$, a public key is the curve point $A = [a]P$ where $P$ is a standard $k$-rational order-$\ell$ base point, and a signature is some point and scalar that satisfies some verification equation involving $A$.

Typical examples in this design space are ECDSA, for an archaic slow error-prone one, and EdDSA, for a modern fast safe one.  They can both be adapted to hierarchical/blinded schemes.

The basic idea of an elliptic-curve hierarchical/blinded signature scheme is to ‘tweak’ the public key and private key in the same way by another scalar $t \in \Z/\ell\Z$.  The derived private key is the scalar $a_t \equiv t a \pmod \ell$, and the derived public key is the curve point $A_t = [t]A = [t a]P = [a_t]P$.  The signature verification equation is the same as in the underlying signature scheme.  Anyone who knows the tweak and the original public key can verify signatures using the derived public key; anyone who doesn't know the tweak can't tell a derived public key from any other curve point.

A devil lurks in the details like Sean Spicer in the bushes: you may need to pay attention to cofactors, malleability of signatures and public keys, etc.—that's why some people want the IETF to standardize a hierarchical signature scheme for the internet, so that individual application developers need not learn the hard way about covfefe or other similar pitfalls of novel developments in public-key cryptography.


The use of the term "sound" in cryptography

Look up the words sound/complete from logic. Complete roughly means that a method can solve every instance. Sound roughly means that the answer it gives is correct.

For example, assume that we have a program that's supposed to tell when an element belongs to a set. A sound program will only answer "yes" when the element actually belongs to the set. An unsound program might sometimes answer "yes" even though the element doesn't belong to the set. For some instances unsoundness might be OK, if it happens very rarely. An example is a primality tester, which might falsely claim with a very small probability that a composite number is prime.

This applies similarly to any decision procedure for example a program that has to declare whether $X$ is secure in some model $Y$.


What is the importance of Modular arithmetic in cryptography?

A few reasons:

As mentioned, modular arithmetic allows groups. See @mikeazo's answer.
Cryptography requires hard problems. Some problems become hard with modular arithmetic. For example, logarithms are easy to compute over all integers (and reals), but can become hard to compute when you introduce a modular reduction. Similarly with finding roots.
Cryptography is implemented digitally. It is nice if values can't be of arbitrary size. If you work with modular arithmetic, you have guarantees about the largest value you will see and can allocate the correct amount of space to hold values.


Forward-secure static-ephemeral ECDH key agreement protocol

The protocol seems secure. Some comments below.

  Bob computes the DH shared secret X using his private key and Alice's static public key, and then K(X), the result of applying an appropriate key derivation function (KDF) to the combination of A, B, and X.

The DH secret X already depends on both key-pairs. Including the public keys in key derivation does not seem to add security.

(Also, in practice Bob should calculate X after sending the ephemeral key to Alice, while waiting for reply, so it is not part of the critical path.)

  Both Alice and Bob compute the DH shared secret Y using their ephemeral keys (e, E) and (b, B), and K(Y), the result of applying the KDF to the combination of E, K(X), and Y.  The values X, K(X), and Y are discarded.

Again, the inclusion of anything but Y in key derivation seems unnecessary.

  [...] When the session is finished, the ephemeral keys (b, B), (e, E), and K(Y) are discarded.

The ephemeral key-pairs (b, B) and (e, E) can be discarded already  in step 8 after Y is calculated. Unless you use them for something else, in which case you need to look at how that might interact with the protocol.


How can we verify if a function is indeed a one way function?

First we need to precisely define what this function is. You don't give enough details, so I'm going to go with this.

  The function $f$ takes as input a string of even length $n = 2m$. It interprets each half as an unsigned $m$-bit integer, computes their sum, and outputs it as an unsigned $m+1$-bit integer.

So the function is defined only on inputs of even length; however this is not a problem because if we need a function defined on all inputs, we can just drop the last bit when the input length is odd.

The one-wayness game is as follows, on security parameter $n = 2m$:

A string $x$ of length $n$ is chosen uniformly.
$y = f(x)$ is computed.
The adversary is invoked with input $(y,1^n)$, and outputs a string $x'$.

The adversary wins if $f(x') = y$. In order to show that $f$ is not one-way, we must show that there is an adversary $A$ and a polynomial $p$ such that for infinitely many $n$, $A$ wins with probability at least $1/p(n)$. We will construct an adversary $A$ which wins with probability $1$ for all $n$.

Since $y = f(x)$ for a uniformly chosen $x$ of length $n$, it is the sum of two uniform integers in $\{0,\dots,2^m-1\}$. Thus $y$ will be an integer in $\{0,\dots,2^{m+1}-2\}$. $y$ will not be uniformly distributed (think of how the sum of two dice is more likely to be 7 than 12), but this is not a problem because our $A$ will win with probability $1$ for all values of $y$.

$A$ works as follows. If $y$ is even, it outputs $x' = (y/2,y/2)$, and otherwise it outputs $x' = ((y+1)/2,(y-1)/2)$. In both cases, it zero-pads each half so that it is of length $m$. It is clear than in each case we have $f(x') = y$, so the adversary always wins.


Client and server using same SSL certificate - any issues?

If all the components share the same certificate, then they share the same private key. This raises the two following points:

When a secret is shared by more than two people, can it still be considered really secret ? Secrecy dilutes fairly fast. If all components share the same secret value, then breakage of any single component reveals the private keys and endangers the whole system. Similarly, every single client or server has the power to impersonate every other client or server in the system.
If client and server share the same secret value, why would you use certificates at all ? Certificates make sense when every entity has its one private key which never travels around. If client and server contain the same secret sequence of bits, then they could use pre-shared key cipher suites, which will use no certificate at all, and might be faster as well.


Is one-time pad encryption vulnerable when near identical data is sent many times with different OTP?

No. As long as each pad is completely random and independent, you can encrypt literally anything of the appropriate size (no larger than the pad) and retain information theoretic secure confidentiality. This attack is termed a known-plaintext attack, or KPA. The OTP encryption scheme is only vulnerable to this if you re-use padding material, which breaks the scheme. A proper OTP is not vulnerable to KPA.


How many bits are needed to commit one bit non-interactively in the standard model?

The state of the art regarding non-interactive bit commitment from OWF is quite simple: it is known to be impossible (at least using black box reductions) to build non-interactive commitments from one-way functions (see e.g. this paper).

Are you specifically interested in constructions from generic one-way function, or are you ok with more structured assumptions, such as one-way permutations (which do imply non-interactive commitments)? If you are also interested in OWP (or even one-to-one OWF), then I think the state-of-the-art generic construction of a NIBC is the direct application of the Goldreich-Levin theorem: to commit to $b$, given any OWP $f:\{0,1\}^n\mapsto \{0,1\}^n$, pick random $(x,r)$ and return $(f(x), r, \langle x, r\rangle \oplus b)$. The communication is $2n+1$ bit per bit committed. If you want to commit to a single bit, I do not know of any better solution. When amortizing, however, there might be better approaches - for example, you can at least commit to $\log(n)$ bits at once using a single $x$ and $\log(n)$ different $r$'s, lowering the communication to $n(1+o(1))$. I don't know if there is anything better generically (getting more hardcore bits from the Goldreich-Levin construction seems hopeless, but perhaps a completely different approach can help).

From collision resistant hash functions, at least, this papers provides a construction of a non-interactive commitment with $O(1)$ amortized communication - but their construction still requires a one-time interactive setup phase, the commitment scheme only becomes non-interactive after that.


Choosing a suitable prime for accumulators

I'll use as reference Michael T. Goodrich, Roberto Tamassia, Jasminka Hasic's An Efficient Dynamic and Distributed RSA Accumulator from arXiv (2009), not the version originally in proceedings of ISC 2002 or linked in the question.
Disclaimer: I discover this paper while writing this answer, thus the following is highly tentative. Further, there are important things that I fail to make sense of, which means my understanding or the paper is wrong. Therefore, do not use the following for anything more serious than an exploration.

Preliminary: choice of RSA modulus $N=P\,Q$, and base $a$.
When it is wished to store $e_i$ of up to $k$ bits, the scheme as described starts by generating “strong primes¹” $P$ and $Q$ of at least $3k/2$ bits each. I believe they additionally need to be at least as large as required for security of RSA (that's not stated). The article's Experimental Results states "the parameter $N$ of the RSA accumulator is a 200-bit integer", but if I understand the rest suggests $k=165$, which would make $N$ 495-bit. Even this would have been too low when the article came out, see this. Such disregard for a safe choice of $N$ in both the theoretical and practical parts of the article is crying to be fixed. I'll have a try at that.
The article's reference for “strong primes¹” is the Handbook of Applied Cryptography definition 4.52:

A prime number $p$ is said to be a strong prime if integers $r$, $s$, and $t$ exist such that the following three conditions are satisfied:
 (i)    $p−1$ has a large² prime factor, denoted $r$;
 (ii)   $p+1$ has a large² prime factor, denoted $s$; and
 (iii)  $r−1$ has a large² prime factor, denoted $t$.

In the context of RSA accumulators and problems that rely on the Strong RSA assumption (including the question's scheme), I would require at least (i) to hold for $P$ and $Q$; and for good measure I'd use safe primes of the same bit size, as required in the article's reference [6], Josh Benaloh and Michael de Mare's One-way accumulators: A decentralized alternative to digital signatures, in proceedings of Eurocrypt 1993 (with extended abstract).
For a modern implementation I would consider $k=680$, and $P$ and $Q$ random 1024-bit safe primes in the interval $[2^{1023.5},2^{1024})\,$, which are easy to generate.
Also, it's required “a suitably-large base $a$ that is relatively prime to $N=P \,Q$”. For lack of other guidance, I'd consider $a=\lfloor\pi\,2^{2045}\rfloor$.

Primes representative of the $e_i$ to be accumulated.
The paper defines a function
$$\begin{align}h:\{0,1\}^{3k}&\mapsto\{0,1\}^k\\
x\quad&\to h(x)\underset{\text{def}}=U\times x\end{align}$$
where $U$ is a binary matrix of $k$ lines and $3\,k$ columns. And it defines the prime representative of $e_i$ to be accumulated as a prime $p_i$ in $[2^{3k/2},2^{3k})$ such that $h(p_i)=e_i$ (assimilating integers to bitstrings per e.g. big-endian convention).
In order to find $p_i$ from $e_i$, we can simplify the system of $k$ binary equations with $3k$ binary unknowns $U\times x=e_i$, enumerate solutions at least $2^{3k/2}$, and stop at the first prime $x$ found. I located no requirement on the enumeration order, but I guess that it must be deterministic, and pseudo-random would not harm.
The rest seems standard use of an RSA accumulator.

¹ Note: In normal RSA, it's dubious that strong primes are really needed nowadays. Condition (i) [resp. (ii)] aims at blocking Pollard's $p-1$ [resp. William's $p+1$] factoring, but that becomes hopeless as $p$ increases (as needed to resist GNFS), and could only really help in multi-target attacks at low parametrization. Condition (iii) aims at blocking a cycling attack but seems pointless, see Ronald L. Rivest and Robert D. Silverman's Are ‘Strong’ Primes Needed for RSA?. None of these conditions are required by the conservative FIPS 186-4 appendix B3 for primes 1024-bit or larger intended for RSA moduli used in signature.
² Nothing in either the paper or the HAC hints at how large in the context of RSA accumulators. The guidance in FIPS 186-4 is not intended for this context; using it for (i) would be adventurous.


Does AES-NI offer better side-channel protection compared to AES in software?

Yes, AES-NI was specifically designed to be constant-time and thus offers better side-channel protection than (some) software implementations. Note however that these day there exist quite fast side-channel resistant software implementations for AES, which are in-use by the better crypto libraries. AES-NI mainly offers a speed advantage over these implementations.

From the Intel® Advanced Encryption Standard (Intel® AES) Instructions Set Whitepaper:

  The AES instructions are designed to mitigate all of the known timing and cache side channel leakage of sensitive data (from Ring 3 spy processes). Their latency is data-independent, and since all the computations are performed inter
  nally by the hardware, no lookup tables are required. Therefore, if the AES instructions are used properly (e.g., as in the following code examples) the AES encryption/decryption, as well as the Key Expansion, would have data-independent timing and would involve only data-independent memory access. Consequently, the AES instructions allow for writing high performance AES software which is, at the same time, protected against the currently known software side channel attacks


Most influential/illuminating papers/books/courses on lattice based cryptography?

You seem to have a few questions:

  Why are Discrete Gaussians "not far" from the uniform distribution when you work mod the lattice?

This is worked out in the paper they are introduced in (Miccancio Regev 2004). See Lemma 4.1 in particular.

  How to generate them?

It depends on whether you care about constant-time generation or not. Either way, there are a few techniques. These include using "generic samplers" (that work for any discrete probability distribution), including:

Inverse CDT (cumulative density table) --- If $F_X(x)$ is the cumulative density function of $X$, and $U\sim \mathcal{U}([0,1])$, then $F_X^{-1}(U)\sim X$. This can be used to generate samples from any distribution.
Knuth-Yao sampling --- You create a certain binary tree, then preform an unbiased walk on it, and return a sample based on what leaf you end up in. Very entropy efficient (and where the "Entropy is equal to the # of coin flips you need to sample from a distribution) comes from, but hard to make constant time without destroying the entropy efficiency.
Alias sampling. A little harder to explain, but you can reduce sampling from any distribution to sampling from a uniform distribution, then sampling a (pre-computed) biased coin depending on the uniform value sampled.

There is a non-generic sampler known as Karney's method as well. Moreover, there's a sampling technique known as "convolution sampling", which allows one to generate discrete gaussians of larger parameters from discrete gaussians of small parameters, so one can restrict to the small parameter case.

Recent work can be seen here, and the references can be useful pointers for the rest of the literature (it misses out on some recent work trying to make KY sampling constant time, but that's about it).

  Smoothing Parameter's intuitive meaning

Intuitively, it's the amount of Gaussian mass one has to place on each lattice point such that it "blurs" throughout space.
One can think of the lattice $\Lambda$ as initially a set of points (having discrete gaussians of parameter $\sigma$ of "0" on each point).
As you increase $\sigma$, these points "blur" out.
If you increase $\sigma$ enough, they'll "cover" the whole space (and then, when working mod the lattice, will approach the uniform distribution).
The smoothing parameter measures when a "phase transition" of this form happens, between being quite close to uniform, and non-uniform.

If you're more familiar with geometric notions of the lattice one could think about continually increasing balls around lattice points (instead of gaussians), until one finally covers all points of the ambient space in some ball.
This has another quantity associated with its phase transition known as the "covering radius".


How to get an optimal strategy in computing isogenies for SIDH/SIKE

On page 67 of the same spec, Algorithm 42 does exactly what you are asking for. Here it is again in Python:

def strategy(n, p, q):
    S = { 1: [] }
    C = { 1: 0 }
    for i in range(2, n+2):
        b, cost = min(((b, C[i-b] + C[b] + b*p + (i-b)*q) for b in range(1,i)),
                      key=lambda t: t[1])
        S[i] = [b] + S[i-b] + S[b]
        C[i] = cost
    return S[n+1]

The parameters p and q are used to weigh the strategy, they depend on your implementation of SIKE. Following the definitions of the spec, p is the cost of one multiplication step, q the cost of one isogeny step.

When choosing a strategy, there may be other considerations than those related to the weights p and q. For example, you may prefer a strategy that is slightly more costly, but easier to parallelize. So the algorithm above is by no means a definitive answer: you should choose whatever strategy works best for you, as long as it is a valid one (see page 15 of the spec). If you have no idea what's best for you, choose the ones given in appendix C of the spec, or use a non-optimized strategy.

Regarding your "why" question, each "leaf point" defines the kernel of one ℓ-isogeny step. You want to compute all of them, so you can compute all isogenies, and compose them. This is not a theorem. It is just the best way we know.


Remember: a random permutation (aka "a hamming-weight-preserving one-way function") is known in layman's terms as a shuffle; there are trivially correct algorithms to do this; Python itself, though, makes it quite convenient to just leverage its shuffle implementation by subclassing Random with your choice of deterministic CSPRNG:
from Crypto.Hash import SHAKE256
from random import Random

def deterministic_shuffle(seq, key, alg=SHAKE256):
    """Applies a hamming-weight-preserving random permutation to seq"""
    SpongeBasedRandom(key, alg.new).shuffle(seq)

class SpongeBasedRandom(Random):
    def __init__(self, seed, spongefactory):
        super().__init__()
        self._sponge = spongefactory(seed)
    def getrandbits(self, k):
        n = -(-k // 8)
        # FIXME: squeezes-and-then-wastes k % 8 bits -- Is that
        # a security issue?
        # It'd take about +5 or +6 SLOC to patch it, just dunno if
        # it'd be worth it to bother
        return int.from_bytes(self._sponge.read(n), 'little') & (2 ** k - 1)
    def randbytes(self, n):
        return self._sponge.read(n)

k = b'Hyper Secret Input Key'
h = len(k) * 8
n = 4096
assert n > (8 * h)

bitstream = ([1] * h) + ([0] * (n - h))
deterministic_shuffle(bitstream, k)

print(bitstream)


Explanation of CAVP format for NIST Test Vectors for SHA-2 and 3

All of your questions are answered in the Validation System documents that are linked to by the algorithm test pages.  In this case, look at http://csrc.nist.gov/groups/STM/cavp/documents/shs/SHAVS.pdf

For this case, the message length is expressed in bits not bytes. The fact that the message is also encoded as value of 00 should be ignored in the test vectors smaller than one byte; this just adds confusion to the reader.

Len = The length of a message in bits


Self signed certificate for mobile app and backend from same company

Yes, this (certificate pinning) is the preferred method, since it removes the reliance on external authorities and makes man in the middle attacks even harder.

An additional step would be to obscure the pinned certificate inside the application to stop it easily being edited.


What is a size of mac_length and mac_key_length for TLS cipher suites HMAC using SHA384 and SHA512?

Given that MD5 has a size of 128 bit (16 bytes), SHA-1 of 160 bits (20 bytes) and SHA256 of 256 bits (32 bytes) and that these numbers are exactly reflected in the mac_length and mac_key_size I would assume that these sizes reflect the output size of the hash used. This also matches the definition of the HMAC used in TLS where the last step is to apply the hash and use its full output as result. Similar the HMAC definition recommends the output length of the hash as the minimal (and also probably most suitable) key length.

With this in mind the size for SHA-384 will be 384 bits (48 bytes) and for SHA-512 512 bits (64 bytes).