Why do we use multilinear maps for obfuscation?

Multilinear map is a very natural candidate to build obfuscation: it allows to perform operations on values in an oblivious way, and is in addition enhanced with a "zero-test" procedure, that can be used to obtain the result of a computation, but which should (hopefully) not reveal the intermediate steps of the computation. Hence, it gives a candidate for indistinguishability obfuscation (iO) of small enough circuits. From there, one can bootstrap to arbitrary circuits using fully homomophic encryption with a "small enough" decryption circuit: the circuit evaluation is done obliviously over the ciphertexts, and decryption of the result is performed using the multilinear map (informally).

So, the most obvious reason is that it feels natural. But there is a deeper reason: iO can be shown to imply multilinear maps, as proven is this recent paper. Some care must be taken here: multilinear maps are objects, like encryption schemes are. But one cannot talk about a primitive "implying" another primitive: the security properties that we considered must be taken into account. What the paper shows is that iO implies semantically secure multilinear maps, which were recently shown to also imply iO (see e.g. this paper). Therefore, up to some other classical primitives used in the various constructions, iO and semantically secure multilinear maps are essentially equivalent: if you have one, you have the other.

This does not mean that multilinear maps are necessarily the starting point of any iO construction, just that this starting point will necessarily be "as strong" as multilinear maps. For example, there is a rich line of works in building iO from functional encryption.

Finally, you mention that candidate multilinear maps have been broken. Again, one must treat this with care: one does not break an object, but a security assumption on this object. So, many security assumptions on multilinear maps have been broken, in various settings. For a long time, all these attacks relied on "encodings of zero", which are not used in iO constructions, so those attacks, while breaking mmaps in some sense, did not break iO. More recently, there have been some more powerful attacks (called annihiliation attacks) that threaten iO in some settings. But many of the most recent iO constructions, with more recent candidates of mmaps, remain unbroken. Still, these variety of attacks suggest that we are yet far from deeply understanding what can make iO secure; researchers do not show a considerable confidence in the security of current candidates, but recall that this is a young area, subject to many ongoing research.


Are Blind Signatures Fundamentally Different From Signatures of Hashed Values?

The idea behind a blind signature is that party $\mathcal{A}$ has a message $m$ that they want party $\mathcal{B}$ to sign, but they do not want party $\mathcal{B}$ to learn the value of $m$. Using RSA, where $(e, N)$ is $\mathcal{B}$'s public key and $d$ is it's private key, this may look like:

$\mathcal{A}$ computes $x = m*r^e \mod N$, where $r$ is a randomly sampled value.
$\mathcal{B}$ signs $x$ i.e. $y = x^d \mod N$ and sends the signature to $\mathcal{A}$.
$\mathcal{A}$ computes $s \equiv y * r^{-1} \equiv (m * r^e)^d * r^{-1} \equiv m^d * r * r^{-1} \equiv m^d \mod N$, which is $\mathcal{B}$'s signature of $m$.

Note that $\mathcal{A}$ now has a signature from $\mathcal{B}$ on $m$, and $\mathcal{B}$ has no knowledge of $m$ since they cannot recover $m$ from $x$. [1] Anyone can verify this signature using $\mathcal{B}$'s public key.

Note that this does not work with hashing, because hashing is one-way. If we say $x = H(m)$ then in step 3. we have no way of recovering the signature for the original value $m$.

[1]: as poncho points out, blind signatures have a stronger property than this, namely that if $\mathcal{B}$ signs messages for both $\mathcal{A}$ and $\mathcal{C}$, then given an unblinded message and signature pair $\mathcal{B}$ cannot determine who the signature was for


Why is HMAC-SHA1 still considered secure?

In the first section of this answer I'll assume that through better hardware or/and algorithmic improvements, it has become routinely feasible to exhibit a collision for SHA-1 by a method similar to that of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu's attack, or Marc Stevens's attack. This has been achieved publicly in early 2017, and had been clearly feasible (the effort represents mere hours of the hashing effort spent on bitcoin mining; but the hardware used for that can't be re-purposed for the attack on SHA-1).

Contrary to what is considered in the question, that would not allow an attacker not kowing the HMAC-SHA-1 key to make an undetected change in a document; that's including if the attacker is able to prepare the document s/he's willing to later alter.

One explanation is that the collision attacks on SHA-1 we are considering require knowledge of the state of the SHA-1 chaining variable, and the attacker of HMAC not knowing the key is deprived from that knowledge by the key entering on both extremities of the iteration of rounds in which the message stands in HMAC. A much deeper break of SHA-1's round function would be needed to break HMAC. Not coincidentally, M. Bellare's New Proofs for NMAC and HMAC: Security without Collision-Resistance shows that security of HMAC holds assuming only weaker properties on its round function than needed for collision resistance of the corresponding hash.

What would be possible is for an attacker knowing the HMAC key to prepare a document that s/he willing to later alter, that can be altered without changing the MAC. But since the attacker is holding the HMAC key, that's not considered a break of HMAC.

A comment asks when should SHA-1 not be used?

It is advisable to quickly phase out SHA-1 in applications requiring collision-resistance (as an image: quickly walk away, as you exit a building which fire alarm rings when there's no smoke). That includes hashing for integrity check or digital signature of documents prepared by others even in part (which is, most documents). If continuing to use SHA-1 has strong operational benefits, it can safely be made an exception by inserting something unpredictable by adversaries before any portion of the message that an adversary can influence. For example, by enforcing an unpredictable certificate serial number at time of request of a certificate, a certification authority could still safely issue certificates using SHA-1 for their internal signature.

As explained in the first section of this answer, as long as the key of HMAC-SHA-1 is assumed secret, there is no indication that HMAC-SHA-1 is insecure because it uses SHA-1. If the key is assumed public, or its leak is considered an operational possibility where it is still wanted collision-resistance for HMAC including for message prepared after disclosure of the key, then the precautions discussed in the previous paragraph apply.


How can the Schmidt–Samoa cryptosystem uniquely decrypt large messages?

When you take a look at the paper you can see, that it is actually defined as a key-encapsulation mechanism, meaning that you will never encrypt data, but only keys for a symmetric encryption scheme. (That is, short messages.)

Further in $\mathsf{TKEM.Key}(pk)$ the "key carrier" that will be encrypted is explicitely chosen from $\{0, 1,\ldots, 2^{rLen} - 1\}$ where $rLen = 2k − 2$.
As $p$ and $q$ are both $k$-bit primes, $pq$ will always be greater then $2^{rLen} - 1$ and therefore the problem will not arise.

If you view the scheme as a public key encryption scheme, then the message space is simply $\{0, 1,\ldots, 2^{rLen} - 1\}$. You are not supposed to encrypt larger messages. (which is fine, because $k$ is a lot larger than in your example and you only want to encrypt short keys.)


If you know the prime factors (p,q) of the modulus, then it would be easy to find the private exponent.
You'll proceed as follow:

Compute the Carmichael function $\lambda(n)=\operatorname{lcm}(p-1,q-1)=\frac{(p-1)\times(q-1)}{\operatorname{gcd}(p-1,q-1)}$
Choose a number e such that $\operatorname{gcd}(e,\lambda(n))=1$,
Apply the Extended Euclid Algorithm to compute the inverse of $d=\frac{1}{e}\bmod\lambda(n)$,    Cf Donald Knuth:Semi-Numerical Algorithms II (or any other reference book),

Then the public Key is $(n, e)$, while the private Key is $(n,d)$. This correspond to the straightforward parameters of RSA Keys.
You can also generate with a similar way, the parameters associated to the CRT algorithm with allow a substantial gain when executing Modular exponentiation with the private Key.
If required I could depicted it.


Ideally, you'd implement both versions of the SHA-256 algorithm on some common platform, benchmark them and compare their performance.  This would give you a measure of their actual real-world performance, or at least something close to it.

If that's not practical, the next option would be to map each operation to some nominal number of CPU cycles typically required to execute it on your target platform (or possibly to nominal gate equivalents, if you're considering hardware implementations instead).  Of course, even this measure will still be somewhat platform-dependent.  Also, for modern superscalar CPUs, "typical" per-instruction cycle counts may not be all that useful as a performance metric, since actual performance will depend highly on the amount of instruction-level parallelism present in the code.

Finally, for a quick back-of-the envelope estimate, you could simply assume that all the basic arithmetic operations you listed (additions, rotations, shifts, bitwise ops) take the same time to execute, and simply add the operation counts together.  Indeed, for many CPUs, this may be reasonably close to the truth: even if the actual execution times differ, they probably won't differ by more than a factor of 2 or 3 at most.

In particular, it's generally pretty safe to assume that addition and bitwise ops are among the fastest instructions on any CPU, and that they'll each take the same number of cycles to execute.  Shifts may or may not be slower, depending on the CPU and the type of the shift: one-bit shifts are nearly always fast (and a one-bit left shift can be emulated by addition anyway), but there are some CPUs that have slow multi-bit shifts, and shifts by a non-constant amount may be even slower.  Rotations are even more of a mixed bag, but you can generally assume that they're no faster than an equivalent shift and no slower than two shifts (because you can always emulate a rotation using two shifts plus an addition / OR / XOR, and the latter can often be amortized away).

For some example timings, see e.g. this report by Torbjörn Granlund, titled "Instruction latencies and throughput for
AMD and Intel x86 processors".  Looking at the first two tables, it seems that all the operations you listed do indeed have pretty much identical latencies and throughputs on AMD processors, whereas on Intel processors the throughput varies somewhat (but still by no more than a factor of 3).  Of course, all those timings are somewhat artificial, and performance of actual code with mixed and partially interdependent operations may vary noticeably from the "nominal" values.


What's the difference between digest algorithm and signing algorithm?

This is specific to PKCS7/CMS.
See rfc3370 3.2 and rfc5754 3.2,
noting that the referenced versions of PKCS1v2.0 rfc2437 and 2.1 rfc3447 have been formally superseded by 2.2 rfc8017 but the content relevant here hasn't changed. Bear in mind that the original versions of both PKCS1 and PKCS7 (which became CMS) were written in the early 1990s, before it became understood that describing signature and verification as 'encrypting' and 'decrypting' the hash with the private and public keys, or 'backwards', is misleading; PKCS1 is only descriptive has been corrected but PKCS7/CMS has this mistake baked into the ASN.1 and can't be fully corrected without introducing incompatibility.
For "RSA" signature, more exactly RSASSA-PKCS1-v1_5 from PKCS1v2.0 up, with SHA-1 the 'digest' OID is 1.3.14.3.2.26 and the 'signature' OID is 1.2.840.113549.1.1.5. For e.g. SHA-256 they are 2.16.840.1.101.3.4.2.1 and 1.2.840.113549.1.1.11. Although represented by two OIDs in different parts of the message, these actually use the standard hash,pad,modexp scheme with only one hash operation. Don't use MD5, it's broken for collision and thus signature in any setting where the adversary can affect the data (e.g. certificates), so as a result people no longer trust it for anything. SHA-1 also is broken (more recently, see other Qs and https://shattered.io) for 'high-resource' attackers like a government or google, and most people have stopped trusting it.


I am trying to implement TLS v1.1 {3,1} but get alert 70 on hellomessage to goolge

I was able to realize that the above message is malformed(with help of wireshark). You will notice there are 33 random bytes instead of the 32 as prescribed by record layer protocol. It was an error on my part with the char * holding them. Zero was first char so should go up to 31, mine went to 32. Doh.

Now most servers respond with server hello and certificates.


Does re-iterate AES-128 with different keys gives any benefict?

The idea you describe is vulnerable to a meet-in-the-middle attack that work in approximately $2^{128}$ time and $2^{128}$ memory. The attack assumes knowledge of plaintext/ciphertext pair(s). Given a pair, you encrypt the plaintext with every possible key 1 and store those values. You then decrypt the ciphertext with every possible key 2 and look for a match between the two datasets. Say you find that $E_{k_1}(P)=D_{k_2}(C)$. Likely these are your two keys. This can be validated by looking at additional plaintext/ciphertext pairs.

As codesinchaos says, the attack may not necessarily be applicable with realistic cost models, but it is a theoretical break and is therefore considered weaker than just using a larger key space in the first place. Also, I've got to believe that this idea is slower than just using AES-256.


Encryption in which ciphertext is bigger than plaintext?

There's no blockcipher providing this.

However if you want this kind of mapping there are two usage scenarios.

Strengthen the symmetric encryption. You could double the keysize by this construction. In "Applied Cryptography" Schneier suggested to combine two encryption algorithms so the ciphertext would be double the size of the plaintext.

Generate a pad $R$ at random, as long as your message
Calculate $P=R \oplus M$
Encrypt $P$ using one Cipher-Key-Pair
Encrypt $R$ using the other Cipher-Key-Pair

It might be possible to construct an online AEAD mode with intermediate tagging as one could basically authenticate each single block of the message. F.ex. using HMAC + CTR on 512-bit blocks one could encrypt the continous data stream using CTR and place the 512-bit HMAC tag after each 512-bit block. This might be nice, as you've got all the desireable properties of online encryption and intermediate tag verification that such modes provide. It might as well be possible to construct such a mode using a blockcipher (and maybe something like VMAC).

However for the first usage scenario there's no need as current blockciphers are secure enough and if you need larger blocksizes simply switch to something like Threefish.


Security model for privacy-preserving aggregation scheme.

This is tricky and I don't know that there is a generic way to take care of all domain/auxiliary information.

The way we typically do proofs in multi-party computations is by defining an ideal world and show that the information generated in the ideal world (usually the encrypted inputs and the outputs) could be used to simulate the real world protocol transcript (at least in the semi-honest case). If the simulator can generate the transcript, then clearly the transcript contains no additional information beyond what is already present in the info generated in the ideal world. Therefore, the protocol cannot leak additional information.

Given the protocol you've described, the ideal world would be a trusted party which cannot be corrupted is given encrypted inputs from each party. The trusted party decrypts them all (we don't need homomorphic encryption in the ideal world), adds them up and returns the answer. Well, if the answer is $0$ as you suggest, this leaks information. But, that information is leaked in the ideal world as well as in the real, so we don't consider it a breach of the protocol.

The most natural way then to deal with this problem in the ideal world is to have the trusted party check the output for certain cases (e.g., $0$) before outputting the answer. If one of those cases is achieved, the trusted party output $\bot$. You can definitely implement this functionality in your real world protocol using a secure comparison of some sort. Your protocol will obviously be more complex, but such is life.

That shows how you would handle a specific case. There are definitely other cases where domain/auxiliary information combined with the answer will allow adversaries to infer additional information. I don't know of any generic way to handle all of this, and quite possibly it is impossible to handle in a generic way.

Consider the following, assume we have a generic multi-party comptuation protocol $\pi$. Furthermore, assume this protocol is proven secure for up to $n-1$ adversarial parties.

Now, we might be tempted to use this protocol to compute the sum you describe in the question. But, there is a problem. If there are $n-1$ adversarial parties, they can all set their inputs to $0$. The single honest part sets its input to the proper input say $x_h$. The output of the computation is clearly $x_h$ so the honest party's input is leaked. This would happen in the (standard) ideal world too, though. So even though the protocol can handle up to $n-1$ adversarial parties, the specific functionality we are computing can only handle up to $n-2$ adversarial parties. This suggests that the functionality to be computed must have an impact on the adversary model we choose, and seems to suggest that a generic solution to the problem you mention might not be possible.

So then, it seems the path forward would be to list all possible corner cases for a computation where some undesired leak occurs due to domain/auxiliary information, then adjust the computation accordingly. Then the security could be proven using standard methods. This could then potentially be extended to classes of computations, etc.


Why are security against eavesdropping and security against CPA equivalent in the setting of public-key cryptography?

Under a chosen-plaintext attack, the adversary has the power to encrypt polynomially-many chosen plaintexts. In the symmetric world, since only the valid parties hold the encryption key, only the valid parties can "grant" the adversary access to an encryption oracle. So, it isn't assumed that an eavesdropper necessarily has access to an encryption oracle.

In the asymmetric world, however, the public key — the key used to encrypt data — is, well, public. So, an eavesdropper overhears the public key (or is simply assumed to know it, since it is public), and from there the eavesdropper may encrypt whatever messages he or she so desires. This is the same scenario as a chosen-plaintext attack.


Why is the public/private key length used in libsodium so much shorter than needed for RSA

It's not the algorithm that's more "efficient" (that's just a welcome side-effect) but the security level.

Security levels are usually given in bits; to say that a cipher has 80 bits of security means that we assume it takes roughly $2^{80}$ effort to break it, for some definitions of "effort" and "break".

For RSA, the main problem is factoring large numbers. Factoring algorithms are a lot better than brute force - factoring a $n$-bit RSA modulus takes a lot less than $2^n$ operations. Based on the speed of current factoring algorithms, the latest guess (according to ENISA) is that for 80 bit security your $N$ should have around 1024 bits length and for 128-bit security you need a 3072 bit $N$.

For libsodium, the main problem is taking discrete logarithms over a particular elliptic curve group of order $2^{255}-19$. With the best-known algorithms today, taking a discrete log over such a group (where the elements have about 256 bits length) would take around $2^{128}$ operations, hence you get 128 bit security with a lot smaller elements.


Public key encryption and big files with NaCL

You're vulnerable to a chunk-level replay attack, where Mallory (the man-in-the-middle) can mix and match chunks from different files, to produce a file that appears to be from Bob but which Bob never wrote.

Bob sends two messages to Sarah. Let's say the first message comes in chunks A1 and A2, and the second message comes in chunks B1 and B2.
Mallory intercepts both messages. She then constructs the new message A1+B2.
Mallory sends the forged message to Sarah. The boxes open with Bob's key, and the sequence numbers look good.

Since Mallory can forge a message, this scheme fails to provide authenticity.

You could fix this problem in a couple ways. One way would be to put another token inside each chunk, next to the position bytes, that's shared by all the chunks and unique for each message. Then in addition to verifying the position, the receiver would have to check that this identifier matched the previous chunks.

Another approach would be to use NaCl's nonce to do this for you. (Since after all, a "unique token for each message" is sort of what a nonce is.) If you use 16 random bytes (shared by all the chunks) plus an 8-byte counter as your nonce, you can avoid nonce reuse and also prevent the chunk-swapping replay attack. This saves you some space because you only have to transmit the 16 random bytes once, and it's also safer: a forged plaintext will never be decrypted at all, so it's impossible for an implementation to somehow forget to check the tokens. This sort of use case is why NaCl was designed with a large nonce.

Edit: Adam Langley has a post on this: https://www.imperialviolet.org/2015/05/16/aeads.html


What are options to compute DES retail MAC (aka ISO 9797-1 mode 3) under PKCS#11?

An answer surfaced from careful reading of appropriate documentation.

The MAC in the question is also defined in ANSI X9.19, and is supported by some PKCS#11 tokens as the mechanism CKM_DES3_X919_MAC_GENERAL.

Other than that, this MAC can be simulated using CKM_DES_MAC_GENERAL (or CKM_DES_CBC or CKM_DES3_CBC) for all but the last block, then CKM_DES3_CBC; but derivation of the key for the first part is hairy, and an adversary observing the intermediary result for a single plaintext can mount a key recovery attack requiring about $2^{56}$ work.

Independent of implementation and intermediary result, as pointed by poncho in comment, there is a key recovery attack on that MAC when so much plaintext is processed that an internal collision occurs, which is in the order of $2^{32}$ MACs, then allowing an attack with about $2^{57}$ work.


Discrete logarithm problem in subgroup of index 2. ElGamal

As an example, algorithms, such as baby step giant step  with time and memory complexity $$T=M=O(\sqrt{N})$$ or Pollard's rho  with time and memory complexity $$T=O(\sqrt{N}),\quad M=O(1)$$have complexities that depend on the size $N$ of the group over which the DL is defined.

So $N=\mathbb{Z}_p^{\ast}=p-1,$ while a subgroup of index 2 has size $N'=(p-1)/2$ and the complexity improves accordingly.


Is there an avalanche effect using block cipher modes of operation?

We don't mind the lack of avalanche because of the IV.

The problem that not having full avalanche would have is that if we encrypt two related messages, for example, two messages that differ only in the last block, is that the ciphertexts would be related, for example, they differ only in the last block.  Obviously, that'd not be good - at the very least, we'd be leaking that the plaintexts are related.

However, with the modes in question, this isn't a concern.  If we do encrypt two related messages, we select a different IV for each message.  It turns out that choosing a different IV makes the ciphertexts look completely different, even if the plaintexts are related (or even identical).

One cavaet to the above: with CBC mode, if the IV's were related (for example, had a small bit difference), and the first plaintext block happen to have the same bit difference, then this is leaked.  That's why we specify that the CBC mode IV's are "random" (that is, unpredictable); other modes don't have this restriction.


It is well known that you can compute any combinatoric function (and hence, any encryption method) with a sufficient number of NAND gates, and so the answer to your question would appear to be "yes, any algorithm is able to run on a "physical level", without a fancy GUI, multitheaded operating system, memory, processor or even a motherboard".

However, I do notice that in the question title, you mention "Encryption", while in the text, you mention "Signing".  Now, we in the cryptographical community use those terms to mean rather different things:

Encryption means a method of transforming the data in such a way that someone without the 'key' cannot read it (but someone with the key can).
Signing means a method of producing a tag with the data and a 'private key', in such a way that someone with the 'public key' can verify that the data and the tag correspond to each other.

In addition, there is a third option, which we don't call signing, but is sometimes confused with it:

A Message Authentication Code (MAC) is a method of producing a tag with the data and a 'key' in such a way that someone else with the 'key' can verify that the data and the tag correspond to each other.

Signatures and MAC do sound similar; the distinction is that with a MAC, the person authenticating the MAC can also generate valid MACs if he wants; with a signature, someone with only the public key cannot generate valid signatures.  This is a distinction that sometimes comes in handy, however known signature methods are considerably more expensive than MACs.  Because of this, we never use a signature unless we need this additional property.

Now that we have defined the terms, we can get back to your question: is your question about encryption, signature generation or MACs?

Well, in practice, it is quite possible to encrypt data or generate MACs without any processor being involved, and we actually sometimes do it in practice.

When we're talking about generating signatures, well, it's more questionable.  Generating a signature is considerably more complex; you could do it without an internal processor (using a pile of NAND gates), however, it's not clear why anyone would choose to.  I don't know the internals of every crypto chip that does signatures (or even the internals of everything I've used), but of the ones that I do know, they all have an internal processor involved (at the very least, to orchestrate the signature process)


Can the TLS 1.3 PSK-DHE handshake be turned into a PAKE?

The current TLS 1.3 draft proposal with PSK does not have PAKE properties; in particular, a client can send a single message, get a reply, and then check every entry in his dictionary to search for the PSK used by the server.

To do this, the client would send a valid hello, specifying the identity that the client is interested in (and a valid keyshare).  The server will also generate its key share, generate a key that's based on the psk, and the key share shared secret, and encrypt some data based on that key.  Then, the client computes the key share shared secret (which doesn't depend on the PSK), and then for each entry in his dictionary, compute what the key would be if that guess was correct, and then see if that decrypts the encrypted region into something readable; if it does, he has recovered the PSK.

I believe that the same approach would work against your proposal, with the possibility that it's the server that can do the dictionary attack; it's the first guy to receive a message encrypted by a key that's a function of the PSK.

Hashing the password doesn't add PAKE properties; the attacker can just as easily hash each entry in his dictionary, and use those.

To make TLS 1.3 into something that does PAKE, the right approach would be to integrate some protocol with PAKE properties (such as SRP or EKE) into it.


Public key crypto without modular arithmetic?

Breaking such a scheme is easy.

Suppose Alice wants to transmit a message $M$ to Bob. First thing, Alice picks an integer $R_a$ and sends the cipher text $C_a = M \times R_a$ to Bob. Bob then picks another integer $R_b$ and transmits $C_b = C_a \times R_b$ back to Alice. Alice calculates $D_a = \frac{C_b}{R_a}$ and sends $D_a$ to Bob. Bob calculates $D_b = \frac{D_a}{R_b}$ and clearly $D_b = M$.

Now, Eve intercepts the messages $C_a, C_b, D_a$ and might easily calculate $R_a = \frac{C_b}{D_a}$ and consequently $M = \frac{C_a}{R_a}$. Eve is clearly not supposed to be able to do this, so this constitutes a break.

Furthermore, it doesn't really matter if the multiplication is done in a finite group or not. In a group, division would be defined as multiplication with the inverse element of the divisor, e.g. $D_a = {C_b} \times {R_a}^{-1}$. Eve would still be able to calculate $M$.


Indeed both have the aim to prevent same messages "encrypting" to the same plaintext.
The difference is the context.

People speak about using IVs if they want to use them in blockcipher modes, like CTR or CBC.

People use the word "salt" if they want to refer to something that is stored in public but must be somewhat random and large. Usually this applies mainly to password hashing schemes like scrypt or bcrypt.


How ROCA get the polynomial used with coppersmith

You are correct—you do want to find a small root of [*]
$$
  f(x) = M \cdot x + (65537^a \bmod M) \bmod N
$$
modulo a divisor $p$ of $N$. In other words, you want to find a divisor of $N$ in the residue class $M \cdot x + (65537^a \bmod M)$. This is explicitly accomplished by the Coppersmith/Howgrave-Graham method, as long as the appropriate restrictions are respected.

However, Coppersmith's method to find such roots traditionally expects a monic polynomial as input. So, to make it monic we simply divide it by the coefficient associated with $x$, that is, $M$:
$$
  g(x) = \frac{1}{M}f(x) = x + \frac{65537^a \bmod M}{M} \bmod N\,.
$$
The roots of $g(x)$ are the same as $f(x)$; to see this decompose the polynomial into its factorization:
$$
   f(x) = (x - \alpha_0)(x - \alpha_1)\dots(x - \alpha_n)\,,
$$
$$
g(x) = \frac{1}{M}(x - \alpha_0)(x - \alpha_1)\dots(x - \alpha_n)\,,
$$
and notice that both have the same roots $\alpha_i$. The Coppersmith method finds the appropriate root modulo a factor of $N$ once you guess the correct $a$.

[*]: The ROCA paper uses alternative $M'$ there, but this is irrelevant here.


Randomized algorithms and the one time pad

You indeed need to define what you understand by an encryption algorithm. The common way of doing this is to consider and encryption scheme as a tuple of three primitives: a key generation algorithm (upon a security level, output a randomly chosen pair of keys), an encryption algorithm to be instantiated with the generated key (that maps an input plaintext to an output ciphertext) and a corresponding decryption algorithm to be instantiated with the corresponding key.

To be semantically secure for an encryption scheme means that given an a priori information about a plaintext and the corresponding ciphertext under the encryption algorithm, no information from the plaintext can be derived that could not have been derived from the a priori information alone. (This has to be understood complexity theoretic-wise.)

Now the one-time pad encryption as you describe it does not fit the above scheme as it does not have this set of three primitives: the key (one-time pad) is to be changed for each plaintext. One could however construct a close encryption scheme this way (I assume fixed length plaintexts for simplicity, but it's not a limitation): one can see the key generation algorithm as a big table of pads indexed to somehow correspond to each one of the possible plaintexts. The encryption algorithm then lookup this table and xor it with the plaintext to produce the ciphertext. This scheme is semantically secure.

Here's is the bottom-line: an asymmetric encryption scheme has to be probabilistic since otherwise, given the encryption key (which is not the decryption key) it would be possible to distinguish, say, the encryption of the "hi bob!" message from that of the "hi alice!" message. But a symmetric encryption algorithm does not have to be probabilistic for the scheme to be semantically secure (the encryption scheme defined above is). However, if the security goal is to achieve the same for pairs of ciphertexts instead of single ciphertexts, then scheme defined above to fit the framework would not be sufficient as it would allow an adversary to distinguish between the pairs of ciphertexts corresponding to the same messages from the pairs of ciphertexts corresponding to distinct messages.

So, yes, a probabilistic encryption algorithm inputs a plaintext and outputs a ciphertext that will vary according to the random coins generated internally.


Using "Additional Authenticated Data" as a secondary key

You certainly could keep the AAD secret; however, for GCM, it wouldn't provide any additional security beyond what the secret key already provides; for CCM, it does still provide some limited authentication protection (but probably not enough).

The bottom line: if you can't trust that your key is secret, well, keeping the AAD secret (or have a secret portion) won't help you.

Details:

If the attacker has a guess for the secret key, he can still verify it, by using that key to decrypt the data, and seeing if the decryption makes sense.  He can do this because for both GCM and CCM, the AAD affects only the tag, it does not modify how the ciphertext is converted into plaintext.
If the attacker has the secret key, he can decrypt ciphertext (just as above).
If the attacker has the GCM secret key, and has seen one valid encrypted message, he can encrypt any plaintext of his own choosing.  This is because the GCM tag can be expressed as $F( Key, Nonce, Plaintext ) \oplus (G( Key, AAD ) \otimes H( Key, Plaintext))$ (where $\otimes$ is multiplication in $GF(2^{128})$).  If he has the key, he can compute $F$ and $H$; if he has seen a valid packet, he can solve the above for the value of $G( Key, AAD )$, even if he doesn't know the value of $AAD$.
If the attacker has the CCM secret key, and has seen one valid encrypted message with a specific nonce, he can encrypt any plaintext of the same length of his choosing with the same nonce.  That's because the CCM tag can be expressed as $F_{K, Plaintext}( G(Key, Nonce, AAD, PlaintextLen) )$, where $F_{K, Plaintext}$ is an invertible function; hence, given a valid message, the attacker can recover $G(Key, Nonce, AAD, PlaintextLen)$, and use that to generate a tag for another message with the same length.

The above assumes you transmit the entire 16-byte tag in both cases; if you truncate the tag to $n$ bits, this actually adds some additional protection to CCM (as inverting the $F_{K, Plaintext}$ function does require all 128 bits; if the attacker isn't given all 128 bits, he'll end up having to search for them).


Basically, this part of the paper aims at proving that, as long as the approximate GCD problem is hard, the DGHV scheme is "secure". So, as it is standard in reduction proofs, you go and prove the contrapositive: you show that if there exists an adversary $\mathcal{A}$ that is able to break the DGHV scheme, then there exist an adversary $\mathcal{B}$ that uses $\mathcal{A}$ to break the approximate GCD problem. For more information on reduction proof and how they work, I recommend this video.

The outline of the proof is as follows: first, the authors exhibit the Learn-LSB routine, in which $\mathcal{B}$ uses $\mathcal{A}$ to learn the leats significant bit of the secret key. This corresponds to step 2 in the paper. Then (step 3 and 4), the authors show that, using this Learn-LSB, it is possible for $\mathcal{B}$ to fully recover the secret key $p$, which also means breaking the approximate GCD problem.

Concerning the Learn-LSB routine (step 2 of the proof)

Here, $\mathcal{B}$ uses $\mathcal{A}$ in a black-box manner to find the least significant bit of the secret key $p$, assuming that when $\mathcal{A}$ is fed with a ciphertext, it returns the corresponding plaintext. The subroutine LearnLSB takes some number $z$ and a public key $pk$ as input. It should output the least significant bit of the quotient of $z$ by $p$, noted $[q_p(z)]_2$ in the paper.

EDIT: note that $\mathcal{A}$ and $\mathcal{B}$ are sorts of imaginary adversaries. Thought experiments, I you will. It is actually impossible to realize the Learn-LSB subroutine (or at least, all crypto experts agree that it is impossible). We are using them only to show that, IF there exists $\mathcal{A}$ able to break DGHV, THEN we can construct $\mathcal{B}$ that breaks approximate GCD problem (and in passing, that realizes the Learn-LSB oracle). YET we know that approximate GCD is hard. We reach a contradiction: therefore $\mathcal{A}$ can not exist. See the video linked above on this reasoning.

Let's look at what happens in one turn of the loop. In lines 2 and 3 of the subroutine, $\mathcal{B}$ creates a rigged ciphertext $c_j$ for the public key $pk$, which it feeds to $\mathcal{A}$ at line 4. $\mathcal{A}$ should return its guess on the plaintext that is inside $c_j$. $\mathcal{B}$ is not directly interested in the plaintext itself, but a function of it (see line 5). The trick is in how $c_j$ is rigged: notice (on line 3) that $c_j$ is a standard ciphertext, except that $z$ was added to $m_j + 2r_j +2\sum x_k$. So instead of $c_j$ being an encryption of $m_j$ it is actually an encryption of a combination of $z$ and $m_j$: specifically, of $[r_p(z)]_2 \oplus m_j$  where $r_p(z) = z \bmod p$. To understand why, see that the decryption of $c_j$ will give (if we simplify, and under some assumption of the form of $z$, which the authors detail in section 4.1.1):
$$\begin{align}
\mathsf{Dec}(sk = p, c_j) &= \left[ \left[ [z+m_j+2r_j+2\sum x_k]_{x_0} \right]_p \right]_2 \\
&\approx \left[ \left[ [ q_p(z) \cdot p + r_p(z) +m_j+2r_j+2\sum x_k]_{x_0} \right]_p \right]_2 \\
&\approx \left[ r_p(z) +m_j + 2r_j+2\sum x_k \right]_2 \\
&= [r_p(z) + m_j]_2 = [r_p(z)]_2 \oplus m_j \\
\end{align}$$

Therefore, coming back to what $\mathcal{A}$'s guess, on line 4, $a_j$ should be equal to $[r_p(z)]_2 \oplus m_j$. However, remember that we want $[q_p(z)]_2$ and not $[r_p(z)]_2$. But as the authors note $[q_p(z)]_2 = [r_p(z)]_2 \oplus parity(z)$, where $parity(z) = 0$ when $z$ is even, and $1$ otherwise. What this small relation says is that, when $z$ is even, then $[q_p(z)]_2 = [r_p(z)]_2$ ; and when $z$ is odd, then $[q_p(z)]_2 \neq [r_p(z)]_2$. Convince yourself by looking at all possibilities for the parities of $[q_p(z)]_2$ and $[r_p(z)]_2$, knowing that $z = [r_p(z)]_2 \cdot p[r_p(z)]_2$ and $p$ is odd.

At last, we can understand line 5, in which $\mathcal{B}$ translates $\mathcal{A}$'s guess on the rigged ciphertext $c_j$ into $[q_p(z)]_2$ by computing $a_j \oplus parity(z) \oplus m_j$

The whole process is repeated a several times because errors might appears (notably, $c_j$ may not be well formed), and the majority of votes is returned.

Concerning the Binary GCD (step 3)

Now, with the Learn-LSB subroutine, the authors run a special version of the binary GCD algorithm on $z_1$ and $z_2$ near-multiples of $p$, and are able to obtain $z = q \cdot p + r$, where $q$ is the odd part of $GCD(q_p(z_1), q_p(z_2))$.

The binary gcd algorithm is not complex in itself. Only, here, the authors run an algorithm on $z_1$ and $z_2$ in appearance, but the actual GCD is computed on $q_p(z_2)$ and $q_p(z_2)$. The Learn-LSB subroutine is useful to know, given $z_1$ and $z_2$, whether $q_p(z_1)$ and/or $q_p(z_2)$ are odd or not. Indeed, the binary GCD algorithm on some number $a$ and $b$ needs to make decision based on the parity of $a$ and $b$.

Finding the secret key p (last step)

At last, using these tools, it is possible to recover $p$ by a final twist. First, $\mathcal{B}$ takes two near-multiples of $p$, $z_1^*, z_2^*$, and runs the above algorithm on them. The result is: a number $\bar{z} = q \cdot p + r$ where $q$ is the odd part of $GCD(q_p(z_1^*), q_p(z_2^*))$. If $q \neq 1$, $\mathcal{B}$ begins again with new $z_1^*$ and $z_2^*$ ($\mathcal{B}$ can check whether $q = 1$ later actually).

Next, perform the above binary GCD with $z_1^*$ and $\bar{z}$. And magically, the bit-decomposition of $q_p(z_1^*)$ appears during the iteration of the algorithm. That is, at iteration $i$, $b_1$ (of line 2 of the paper's binary-GCD) gives the $i$ least significant bit of $q_p(z_1^*)$. Maybe the best way to see how/why is by running (by hand) the algorithm with small parameters, such as $p = 23$, $z_1^* = 11 \cdot p + 2$ and $\bar{z} = p + 1$. It finishes in 4 steps, yielding in order $b_1 = 1, 1, 0, 1$, and $(1011)_2$ is $11$ (Remember that the authors define that all remainders are $r_p(z)\in (−p/2, p/2]$)

Last step: now that you know $q_p(z_1^*)$, do $z_1^*/q_p(z_1^*) = p + r_p(z_1^*)/q_p(z_1^*)$. Round the result and you obtain $p$, since $r_p(z_1^*)$ is (normally) much smaller than $q_p(z_1^*)$.

Wrap-up

So $\mathcal{B}$ started with access to samples of $\mathcal{D}_{\gamma,\rho}(p)$ giving near-multiples of $p$, and found $p$. Thus, it broke the approximate GCD problem. Yet, the approximate GCD problem is deemed hard and assumed unbreakable: we reach a contradiction. Thus, the DGHV scheme is secure !

Note: the answer, although very long already, purposely ignores many important elements, such as the size of some elements and possible wrap-around in moduli computation.


Is the salt value a secret or can it be stored in cleartext just like the IV?

The salt can be kept public.

All that matters is that the salt is available for you to use when it comes to re-deriving your password from some input guess.

In many ways, a salt performs the same function that an IV does for ciphers.

You can read more about salt and password hashing here.


Symmetric encryption algorithms with large IVs and authentication?

Let's look at your requirements:

  have a large IV — specifically, one large enough that using a CSPRNG to generate a fresh IV each time is secure.

Generally, IVs/nonces longer than 96 bits are thought to be okay for random generation. If it is at least 128 bits you can safely use it as long as you can a 128-bit block cipher like AES, because before you run into random nonce collisions you already have random block collisions.

Shorter nonces, such as the 64-bit nonce in Salsa20 and ChaCha cannot be used as freely, since you would expect a collision after a few billion ($10^9$) messages and after just millions with non-negligible probability.

  provide authentication.

Unless you want to compose your own authenticated encryption using a cipher and a MAC, this basically leaves you with one option that is in common use: AES-GCM. ChaCha20Poly1305 is also in common use (TLS), but has a short 64-bit nonce. XSalsa20Poly1305, which CodesInChaos mentions, is also an option, but basically only used in NaCl/libsodium as far as I know.

The X in XSalsa20 is important. That algorithm has a 192-bit nonce. That long nonce allows you to e.g. use a 128-bit random value and a 64-bit timestamp, making collisions unlikely even in the case of a deficient RNG.

  have easy-to-use, well-regarded, portable open-source implementations that are resistant to timing attacks.

This is a bit off topic here, but again, AES-GCM and XSalsa20Poly1305 both have open source implementations. E.g. libsodium has implementations of both.

  I have some ideas (such as encrypting a randomly-generated 512 bit IV with a single round of ChaCha20 – and then transmitting it) but I am not a cryptographer so I don't trust them.

This does not seem to accomplish anything. IVs do not need to be secret and ChaCha20 itself requires a (short) nonce.


Modern cryptographic algorithms are specified in terms of bytes or even bits, not characters.
Whether the data you encrypt happens to represent latin or cyrillic letters or pictures or audio data or anything else does not matter at all to an encryption algorithm; all it ever sees is a bunch of bytes.

What this means in practice is: You have to fix some encoding (UTF-8 is very common nowadays) to translate your characters to a string of bytes which can then be processed by any cryptographic implementation as usual.


Keys-space for a restricted substitution cipher

It is called derangement, see Wikipedia.
Also, in Mathematics Stack Exchange 1, 2

Number of derangements of n elements $=\sum\limits_{k = 0}^{n}(-1)^k\frac{n!}{k!}$

When n = 26 the result is 148362637348470135821287825 $\approx 2^{87} $


This is not an answerable question.  The requirements for a P-box (whatever that is) depend upon the cipher it is embedded in; that cipher imposes some requirements on the P-box.  Therefore, you cannot do P-box design in the abstract, without knowing what the requirements are.  There is no one, single answer that is valid for all ciphers.

P.S. Where did you hear the term "P-box"?  As far as I know, this is not an accepted or widely used term, let alone "straight P-box".


No, you don't have to worry about collisions.

As long as no pair of users have the same LowEntropy input, they will receive different MasterKeys.  If the MasterKey is different, then the AuthKey will be different.  Even if you use the same MasterKey to generate multiple AuthKeys, you don't need to worry about collisions: as long as the keynumber values are different, the derived AuthKeys will be different, too.

You don't need to use scrypt if you are using a 128-bit crypto key (assuming the crypto key is kept secret and not revealed to others).

I don't understand what you are asking when you talk about using multiple times the same ECC key.  I think you should post about that separately, as it sounds like a separate question.  (On this site, we want you to post one question per question; if you have multiple different questions, please post them separately.
  Don't forget to read the FAQ.)


You may be aware of the fact that zero-knowledge proofs for any language in $NP$ can be constructed if you have a zero-knowlege proof for any $NP$-complete language. Then you can reduce your original language to the $NP$-complete one in polynomial time and you are done (more precisely you reduce the instance and the corresponding witness). As the $NP$-complete language you could use 3-coloring or circuit satisfiability for instance. Although in theory such an approach is feasible, it is not practical for cryptographic protocols.

Group dependent language here means relations of elements and exponents in bilinear groups that can be expressed using all the equations illustrated in Figure 1 of the paper you linked to. Although this language is a more restricted language than "any language in $NP$", it is expressive enough for many interesting tasks that show up in cryptographic protocols to prove statements about ciphertexts, commitments and (structure-preserving) signatures for instance. The benefit is that it is practically efficient.


Not understanding deterministic authenticated encryption (DAE) security definition

As I wrote in a comment, the reason your proposed attack does not work is that the random oracle also returns the same result when queried with the same input.
The ideal functionality should clearly still be a (random) function, but I agree that the definition in your reference is not as clear as it could be. It would be more precise to say "uniform random function" rather than "random-bits oracle". For example, see Definition 1 in this paper.


Is the "secure-as-worst-case" version of NTRU patented?

I work for Security Innovation, which owns the NTRU patents. We think the NTRU patents would cover this algorithm too -- the patents are written broadly enough to cover different types of keys.

Note that although there are patents, we try to be reasonable about licensing terms. We have granted a free license for non-commercial use on many occasions and are currently exploring our options about licensing both the patents and a reference implementation under an open-source license. If you're interested in learning more, you can contact me directly on wwhyte@securityinnovation.com.


What is the difference between $\in$ and $\in_{\small R}$?

As the comments pointed out $a\in_{R} M$ means picking a sample $a$ uniformly from some set $M$. If a non-uniform distribution is implied, this will be stated.

In case you are also asking about it, $\mathbb{Z}_p^\ast$ is the multiplicative group (nonzero elements) of the integers modulo $p.$ In general
$$
\mathbb{Z}_n^\ast=\{k: k \in \mathbb{Z}_n, \gcd(k,n)=1\}
$$
is the multiplicative group over the integers modulo $n,$ made up of exactly the integers $k$ such that $\gcd(k,n)=1,$ and there are $\varphi(n)$ of them. Of course $\varphi(p)=p-1.$


Indeed, ISO 10126-1:1991 and ISO 10126-2:1991 titled Banking -- Procedures for message encipherment (wholesale) have been withdrawn circa 2007.

The padding specified by ISO 10126 was adding random until the message has length 7 (mod 8) bytes, then adding a byte coding the number of bytes added (including that byte), making the length 0 (mod 8) and suitable for DEA/DES block encryption. The rationale for adding a little randomness is dubious at best; it creates a subliminal channel, for no clear advantage.

I conjecture that the rationale of the withdrawal is not the padding algorithm, but rather the use of single-DEA/DES (56 bit key), which is clearly obsolete and insecure; and availability of other standards for the same purpose.


Authentication protocols for authenticating devices to a server

"The problem I face is that all authentication protocols require

some kind of shared secret between the devices and the server."

Similarly, the problem I face is that $\:1 = 0 \;\;$.

Since your post includes "(eg: a digital signature of a random string by the server)", I will assume

that the server has a signature key-pair and the devices alrady know that pair's verification key.

To start, the device generates a signature key-pair $\:\langle vk_{\hspace{.02 in}d}\hspace{.02 in},sk_{\hspace{.02 in}d}\rangle\:$, $\;$ and sends $vk_{\hspace{.02 in}d}$ to the server.

When it receives a value $vk_{\hspace{.02 in}d}$, the server generates a random value $\:\operatorname{token}\:$, $\:$ sends that along with

a signature on the pair $\:\langle vk_{\hspace{.02 in}d}\hspace{.03 in},\operatorname{token}\rangle\:$ to the device, and stores $\:\langle \text{current_time}\hspace{.02 in},\hspace{-0.02 in}\text{token}\hspace{.02 in},\hspace{-0.02 in}vk_{\hspace{.02 in}d}\rangle\:\:$.

The device tests the signature. $\:$ If the signature verification algorithm accepts, then

the device displays $\:\operatorname{token}\:$ and the user manually authenticates that value to the server.

When a value is manually authenticated to the server, it deletes all triples whose left entry is too old, where "too old" depends on how many triples there are, and for each remaining

triple whose middle entry was just manually authenticated, the server stores $\langle vk_{\hspace{.02 in}d}\hspace{.02 in},\hspace{-0.02 in}\text{context_from_the_manual_authentication}\rangle\:$ and then

deletes that triple and accepts the device as authenticated.

The server also deletes the oldest triple(s) whenever the list of

triples gets too long or the left entry in those triples is way too old.

Subsequently, messages from the device to the server can be signed with $sk_{\hspace{.02 in}d}$ and verified with $\hspace{.01 in}vk_{\hspace{.02 in}d}\hspace{.02 in}$.


How would P=BPP affect zero knowledge proofs?

It would not affect this at all. Note that under reasonable complexity hardness assumptions, it holds that P=BPP. So, even though we don't know how to prove this unconditionally (and in fact seem far away from doing so), it is what we assume to be correct.

I am not sure why you would think that this would affect the Fiat-Shamir heuristic. Even if P=BPP it doesn't mean that randomness has no role. In particular, you cannot sample a distribution deterministically. P=BPP relates to the ability to decide a language, not sample distributions. In particular, the necessity of randomness for zero knowledge holds, even if P=BPP.


Vigenère cipher: Security when key length and plaintext length are the same

Forming my comment into an answer:

If the key has the same length as the message and is used only once, it is basically a One-Time-Pad. This means, that in theory you can match any ciphertext to any plaintext with $a key$. If this key has to match certain criteria (e.g. be a word of a certain language), the information theoretic aspect will be lost. It depends on the actual keyspace if this is a problem.

However, the re-usage is more tricky, because all security is lost in Vigenere once a key is reused. If you have two ciphertexts created by the same key, you can just combine them and have the key eliminated. Then you are left with the combination of the two plaintexts, which is easy to deal with by using frequency analysis.


Conjugate variables in Quantum Key Distribution?

In the simple BB84 protocol, Alice prepares a state in either the Hadamard or the Standard basis. In order to measure Eve need to choose a basis to measure in. The problem for Eve is these two are two orthogonal basis or in a sense "Conjugate". This however is not the same as the conjugate variables you mention in your question.

Measuring in the one of the bases, collapses the state onto a vector in that basis. Measuring in an orthogonal basis would result in a truly random collapse onto a vector in this basis. Hence, no new information is gained about the original state. Thus Eve's choice of basis and the basis which Alice used to encode her bit in must match if Eve hopes to reliably learn Alice's bit.


Does AES-CBC always use PKCS#7 padding?

No. Other common or plausible paddings include

No padding, where the plaintext's length is known to be a multiple of 16 bytes.
Bit padding, where the plaintext is considered a bit stream, it is appended a bit at 1, then 0 to 127 bits at 0 to reach a block boundary. With big-endian bytes, that's appending a byte at 0x80 then 0 to 15 byte(s) at 0x00.
Zero padding (same as above without the initial 1), suitable when what uses the the plaintext is known to ignore extra zero bits, as is often the case for compressed audio/video/image.

Among paddings I have heard of in the past (but never consciously met in combination with AES), there are ESP padding and CipherText Stealing. Others know more.

An AES-CBC library can be used to obtain encryption with no padding, even if it is hardwired for one particular, by submitting plaintext of length multiple of the block size and removing the last block of ciphertext.

Such library with hardwired padding can also be coerced to ignore the padding on decryption. That's easy if the library is designed for on-the-fly decryption: just don't tell it that the end of input is reached. Otherwise, an option is to use the library in encryption mode to encipher an empty plaintext with the same key, take the 32-byte resulting ciphertext $C'_0\mathbin\|C'_1$ (where $C'_0$ is the IV, zero will do) then after the last block $C_k$ of the actual ciphertext append an extra block $C_k\oplus C'_0\oplus C'_1$ before using the library for decryption. This will insure that the padding check passes, and yield a deciphered plaintext as with no padding.

And on top of encryption or decryption with no padding, it is easy to build any padding.


Actually there are a lot of cases where side-channel are important threats.

To name a few:

IOT devices that are storing secret keys to communicate to each other or do whatever they need to do with it, and that are not supposed to be impersonated by an attacked from his computer.
Trusted Execution Environment such as TrustZone, SGX or TPMs in general. For a very recent example, see tpm.fail.
cloud computing: being able to read somebody's else secrets in memory because you are both sharing the same server in the cloud's system
Pay-TV systems or any other system where the providers is broadcasting encrypted content, that is meant to only be decrypted by authorized key holders. (Typically done using smart-cards that are supposed to be impossible to clone, and whose key should be impossible to extract.)

And it even appeared that side-channel such as Spectre and Meltdown could be remotely used through a web browser running malicious Javascript to steal your passwords!


Security strength EC signature for variable message size

You haven't specified the signature algorithm, but let's assume ECDSA.

  The probability of best attack known to secp256r1 key per trial, with variable "length of the message-to-be-signed"

The hash over the message is computed as the first step to generate the signature. The size of the message doesn't matter. So the security strength remains at $2^{128}$, i.e. nothing to be worried about.

  The expected number of trials to make expected value of success = 1

It is unclear why the expected value of success should be 1; I'd worry if the chance of success would be $1 \over 2$ as well. I presume it is when you've tried all options for a specific public key, so close to $2^{128}$ (trying all possible start values in Pollards Rho if I'm not mistaken).

This is all rather basic, I doubt if you can find any explicit references for it, because this is just what's assumed.

What this has to do with the size of the input message for the OTP is unclear to me. I'd rather worry about the security of the overall scheme rather than the signature.

If you want to shorten the signatures themselves then you could take a look at the BLS signature scheme. ECDSA has a signature size of 64 bytes for secp256r1 (independent of the message size, as you may now imagine), while BLS may halve the number of bytes required.


Are "non-mathematical" encryption algorithms comparably secure against brute force key recovery?

The premise of this question is flawed: There is no such thing as a "non-mathematical" cipher.
Every algorithmic procedure admits a mathematical description, hence is inherently mathematical in nature.

Besides that:

It is not hard to make primitives with massive key spaces, but that doesn't really achieve anything.
One can easily construct ciphers with $2^\text{gazillion}$ keys that are totally insecure.
This fallacy feels like a "freshman's converse" to Shannon's theorem: Perfect secrecy does imply big keys, but not the other way round!

The hard part of designing a good cipher is to make it small and fast while still achieving the desired security level.
The performance figures from the linked website are ridiculously slow according to modern standards.
Thus, even if that cipher is not broken — which I strongly doubt anyone has seriously studied — there is absolutely no reason to to prefer it over AES‑256.


Is there a way to tell if a given string is a sha256 hash?

Hashes have no defined structure as e.g. IBAN bank account numbers, to follow your example (not sure about the case for credit cards).

The output of SHA is essentially a number value, without checksums or other additional elements.

To answer your question, the only check you can perform is to verify that the potential SHA-256 hash is 256-bits long. In fact, since you can feed arbitrary inputs into the algorithm, any 256-bit value will be a correct SHA-256 hash for some input(s).

Since you mention strings as the datatype to check: note that the “string” hash is commonly a minimal hexadecimal representation of said hash. The minimal form of hexadecimals consists of two digits per byte, where each digit is a character ranging from 0 to 9, a to f or A to F.

So if your candidate string contains any other letters/symbols it can be rejected. This is a trivial check that lets you distinguish between (2 * 32 = 64) hexadecimals and other text - it doesn't proof that the bytes are the output of a hash function.


How many collisions (identical pairs) are possible in meet in the middle attack on double DES with two unique keys?

Now our job is to find all $x_i,y_j$ such that $x_i = y_j$. I suppose we can use $2^{56}$ binary searches so we could do this in $2^{56}\lg{2^{56}}= 2^{56} \times 56$ steps?

Actually, you're more likely to go with a hashing-based approach (which doesn't scale at O(n log n)), or a disk-based sorting approach (which is technically O(n log n), but a rather better constant of proportionality than repeated binary search); a binary search approach would run into a lot of cache misses (assuming you had that much memory).  On the other hand, sifting through that much data is a tad on the nontrivial side, and one we generally ignore when doing this high-level analysis; we simplify the problem by assuming that all computations, aside from the DES evaluations themselves, are "free".
And, the 'steps' involved with doing this search for duplicates are quite a bit different than performing a DES operation (and are likely to be considerably faster); that makes it difficult to sum them meaningfully.
However, to get your real question:

on average the probability is that $x_i = y_j$ is $1/2^{56}$ right?

Nope; it's $2^{-64}$; that's because both $x_i, y_j$ are 64 bits, and can be assumed (with an incorrect key) to act completely random.

So now we have to check the $2^{56}$ candidate pairs

Nope; there are about $2^{112} / 2^{64} = 2^{48}$ expected
That should explain where the slide is coming from.


How does one conduct a known-plaintext attack on an algorithm?

If your black-box access entails being able to query the cipher with keys and plaintext of your choice, then it is straightforward to mount a brute-force search for the key if given some plaintext-ciphertext pairs. This will in expectation, however, need about as many queries to the black box as the key space is large.

For strong modern ciphers, this brute force attack is meant to be the best attack already. For a cipher not known to be cryptanalytically broken, knowledge of the internals of the cipher will "only" help you to parallelize the attack and maybe do some inner-loop optimizations.

If "black-box access" means only having some pairs of ciphertext and plaintext but no access to the algorithm or an implementation of it, efficiently implementable algorithms can still be broken in theory given enough data. Briefly, given an algorithm A and some plaintexts P as well as ciphertexts C, checking whether A transforms P to C is doable basically in the time needed to run A on P. Hence, an adversary can for instance enumerate all instruction sequences in a language of their choosing in ascending length and stop when they find a match.

Note that while this is clearly even more impractical than the standard brute force attack on ciphers with a reasonable key size is, checking a solution is a polynomial-time problem in the length of P and A, under reasonable assumptions on A. There is no known proof that problems that are polynomial-time checkable cannot be solved in polynomial time (this is the P versus NP problem), so there is no proof that known plaintext attacks on unknown efficiently implementable ciphers cannot be executed efficiently (although there may be polynomial-time separation results that show that the defender can always get an advantage over the adversary).

However, everyone very strongly conjectures that secure ciphers exist. If that is the case, then of course breaking a strong cipher with only some examples of plaintext-ciphertext pairs will be utterly hopeless.


You misread the parameters: $p$ is $$\mathrm{0xDB7C2ABF62E35E668076BEAD208B} \text,$$ but $a$ is $$\mathrm{0xDB7C2ABF62E35E668076BEAD208\underline{\mathbf8}}$$
which is $-3$ $\bmod p$!


Why hash the message before signing it with RSA?

In addition to the performance problems poncho already mentioned when using RSA signatures without hashing I just want to add on the security warning of poncho:
Reordering
If you have a message $m>N$ with $N$ being the RSA modulus, then you have to perform at least 2 RSA signatures as $m$ does not longer fit into $Z_N$. Let us assume that it requires $k$ such signatures and write the message $m=(m_1,\ldots,m_k)$ and the overall signature will be $\sigma=(\sigma_1,\ldots,\sigma_k)$, i.e., $k$ RSA signatures. Now without any additional measures, anyone getting to hold $(m,\sigma)$ can manipulate the message and adopt the signature by 1) swapping any pair of sub-message $m_i$, $1\leq i\leq k$ and corresponding sub-signature $\sigma_i$ or 2) dropping a sub-message and corresponding sub-signature.
As an example for swapping lets say we have $m=(m_1,m_2,m_3)$ and thus $\sigma=(\sigma_1,\sigma_2,\sigma_3)$, i.e., 3 indepenendet RSA signatures for a message consisting of 3 blocks, then an adversary who gets $(m,\sigma)$ can simply swap, for instance to $m'=(m_2,m_3,m_1)$ and $\sigma'=(\sigma_2,\sigma_3,\sigma_1)$, which is a forgery, as it clearly is a valid signature.
Existential forgery
If you do not use a redundancy scheme for messages prior to signing within RSA (textbook RSA signatures), they are susceptible to existential forgeries. Let $(e,N)$ be the public signature verification key of RSA, then one can randomly choose a signature $\sigma \in Z_N$ and compute the corresponding message as $m\equiv \sigma^e \pmod N$.
Note that given an RSA signature $\sigma$, a message $m$ and a public verification key $(e,N)$, the signature verification for the textbook RSA signature will be to check: $m\stackrel{?}{\equiv} \sigma^e \pmod N$.
Clearly, this check will hold for the forgery by construction. Observe, however, that the adversary can not control what the message $m$ will exactly be. In particular, it will be a random element of $Z_N$. However, this may be sufficient in some applications, e.g., when only signing random numbers when issuing some tokens. Applying a redundancy scheme to messages, i.e., hashing and padding prior to signing renders so computed forged signatures useless in practice.
Final Remarks
Consequently, textbook RSA signatures must not be used and instead standardized padding methods for RSA involving hashing and padding the message must be used. Then, RSA signatures provide strong security guarantees (UF-CMA security).


What prevents the successful use of the Giant-step/Baby-step algorithm solving a discrete log problem implemented with modulo arithmetic?

The Discrete Logarithm Problem for a fixed public prime modulus $p$ and generator $g$ of multiplicative order $q$ in $\Bbb Z_p^*$ (that is, $q$ is the smallest positive integer with $g^q\bmod p=1$ ) asks, given $y$ obtained as $y\gets g^x\bmod p$ for a random unknown $x$ in $[0,q)$, to find that $x$ (which is unique).

The Baby Step/Giant Step algorithm solves that problem with $\mathcal O(\sqrt q)$ multiplications modulo $p$, ignoring the cost of memory and memory accesses. The cost of one multiplication modulo $p$ grows slightly slower than $\mathcal O((\log(p))^2)$.

Thus what "prevents the successful use of the Giant-step/Baby-step algorithm solving a discrete log problem implemented with modulo arithmetic" is mostly choosing $p$ and $g$ such that the multiplicative order $q$ of $g$ is large enough: at least twice the desired security level. Say, 256-bit for 128-bit resistance.

Update per comment: The Pohlig-Hellman DLP algorithm essentially attacks each prime factor of $q$ separately. Guarding against it is obtained by insuring that at least one prime factor of the multiplicative order $q$ is at least twice the desired security level.

Further, due to yet other DLP algorithms (GNFS in particular), $p$ must be considerably larger than twice the desired security level (2048-bit $p$ should be a bare minimum nowadays).

The multiplicative order of any element in $\Bbb Z_p^*$ is always a divisor of $p-1$. Hence one way to ensure that $q$ is large and has a large prime factor is to choose prime $p$ as large as required per the above, and such that $(p-1)/2$ is also prime (that is, choose $p$ as a safe prime). It ensures $q$ is among $\{1,2,(p-1)/2,p-1\}$, and allows to choose $g$ leading to one of the two later options (both used in practice), giving a huge security margin w.r.t. Baby Step/Giant Step (or Pollard's Rho) and Pohlig-Hellman combined.

Another option is to first choose $q$ (usually as a prime at least twice as wide as the security level), and build $p$ as a large enough (thus much larger) prime such that $q$ divides $p-1$; then construct $g$ of multiplicative order $q$. That builds a so-called Schnorr group. It is used in Schnorr signature and similar, including DSA, with the advantage of shortening the signatures.


The problem is probably in the usage of BN_bin2bn to construct K (H in the picture) and ADD. GCM specifies that a 16-byte buffer should be transformed into a binary polynomial in little-endian format, but in each byte, it considers the bits in reversed order. Yes, it's confusing. So for example:

The byte array 80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 represents the polynomial $1$ (e.g. with a poly = {0} when using BN_GF2m_arr2poly
The byte array 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 represents the polynomial $z^7$ (poly = {7})
The byte array 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 represents the polynomial $z^{127}$ (poly = {127})

So, before using BN_bin2bn, you need to reverse the bytes, and then reverse the bits in each byte. Maybe there is something already implemented in OpenSSL, but I didn't check it.


What is the official, generally accepted definition of "lightweight crypto"?

There is no official definition, of course. However, at least in my experience, the word is used consistently.

The word lightweight typically refers to something that is significantly less expensive to use than other stuff, while at the same time achieving the same desired effect, but this lightweight-ness has some cost. (If there was no cost to lightweight-ness, it would not be lightweight, but just "better".) This means that the lightweight stuff may be desirable in some situations, but not in others.

Typically, a lightweight block cipher will be amenable to implementations that are small or use little power or ..., compared to the usual block ciphers. This happy state is achieved at some cost, perhaps by reducing the security margin or having more rounds, etc.

Note that people may talk about lightweight public key cryptography, but it is lightweight only when compared to ordinary public key cryptography, not compared to other kinds of cryptography such as block ciphers.

People also talk about lightweight implementations of cryptographic primitives. Again, lightweight refers to some reduced cost, typically achieved by increasing some other cost. People may be interested in an AES implementation with extremely small gate count, for instance, even if it would be slower or use more power than other implementations.

The word lightweight is of course not limited to cryptography, but is used everywhere, with somewhat differing meanings. Consult your dictionary. In technical contexts, it usually has positive connotations in my experience.


This is to prevent two different types of attacks.

Bias attacks. It may in the future be that ChaCha20 is broken like RC4 is and that you can recover the secret key (or something equivalent) only given enough parts of the keystream. By re-keying often enough you can limit the length of the keystream for each given key, rendering those attacks impossible.
State recovery attacks. Assume an attacker learns the state of the PRNG at some point in time. Now while he can still predict future bits, he won't be able to predict past bits beyond the last re-key, because the key needed to do this is gone and you can't recover it from the current key (if you could you could passively recover the key from a short fragment of the keystream).


Splitting text before Format Preserving Encryption operation

I'd strictly perform FF1 on the entire postal code. That means converting the code to a number in the range $\big[0,26\cdot10\cdot26\cdot10\cdot26\cdot10\big)$ and then encrypting, decrypting and getting it back. This is relatively simple base conversion so it should be easily done using division and remainder math.

Obviously, otherwise you may leak repetition of parts of the input. For instance, if we encrypt the first and second part separately, you may also have Sneezy's postal code, $\mathtt{H0H\space1H0}$ in there ($\mathtt{H1H\space0H1}$ was already taken by the evil witch). Now you can see that $\mathtt{H0H}$ repeats, so anybody knowing Sneezy's code will also indicate the first part of Santa's code; not good.

With many known postal codes - many of which may already be known - this means that it will become easy to quickly guess all the postal codes. If one is relatively unique then it clearly indicates a rather sparsely populated part of the country.

Other schemes - like the one you are proposing - may have similar issues, it kind of depends on how the postal codes are generated. By converting the entire postal code to a number issues such as these can be avoided.


Digital signatures using a partially public key

A few things.  First of all, MD5 is broken, and no longer suitable for cryptographic purposes.  Instead, prefer newer algorithms, like those from the SHA-2 family (SHA-256, SHA-512, etc).

Second, the term "signature" in cryptography is defined more narrowly than you would expect.  It specifically refers to situations where there is a public key (the "verification" key), and a private key (the "signing" key).  Everyone can verify a signature themselves, if they have the public key.

It sounds like what you're actually after is a Message Authentication Code (MAC).  MACs use a single "secret key" for both signing and verifying, instead of having separate keys for each purpose.

Since that's the behaviour you want (assuming I understood your comments correctly), it's best to use an algorithm designed for that purpose, such as HMAC-SHA256.


Proving the knowlege of e-th root in an non-interactive way

Bad news is that what you ask for is impossible to achieve with the proposed Guillou-Quisquater (GQ) identification protocol. Unfortunately, $\Sigma$-protocols for group-homomorphisms are not efficient in groups of unknown order.

1) Efficiency Limitations of $\Sigma$-protocols in groups of unknown order

Informally speaking $\Sigma$-protocols in groups of unknown order for group-homomorphism $\phi(\cdot)$ have large knowledge error. This was shown by Bangerter et al. in case of generic-groups (see Theorem 6. in the linked paper). More specifically, in your specific scenario, the knowledge error of the GQ-protocol is $1/e$, where $e$ is your exponent (prime in your case). Hence, to achieve reasonable knowledge error, you need to repeat the protocol several times which would sacrifice the succinctness of your proof, given that supposedly your RSA group elements are already large (few thousand bits, I suppose).

For instance, let's take your setting: $e=65537\approx2^{16}$. Assuming you want to achieve $128$-bit security you need to repeat the GQ-protocol $8$ times. If you have $2048$-bit length for the modulus, then the proof size is $2\cdot8\cdot2048$ bit, which is $4.096$ kilobytes.

2) Circumventing the limitations by a trapdoor-free CRS

Efficiency limitations of $\Sigma$-protocols in groups of unknown order can be circumvented by applying a trapdoor-free CRS. In this case it is enough to repeat the $\Sigma$-protocol only once as it was shown by Boneh et al. Namely, the CRS would contain only a single group element whose DLOG should be not known to anyone. The downside of this approach is that it assumes a non-standard assumption, i.e. the Adaptive Root (AR) assumption. As of today we know quite little about AR. For example, it is not known yet whether AR is equivalent to Factoring in the generic ring model or not. However, we do know that AR holds in the generic group model, although this is not a decisive result as the generic group model is quite a restricted computational model.

3) Making $\Sigma$-protocols non-interactive

There are standard ways to implement the FS-heuristic. However, there are some pitfalls you need to have in mind. In the weak-FS (wFS) the challenge is computed as the hash of the commitment (first message of the prover). In the strong-FS (sFS) the challenge is obtained by hashing both the statement and the commitment. It was shown by Bernhard et al. that a protocol implemented with the wFS becomes insecure if a malicious prover can adaptively choose her statements she wants to prove. So to be on the safe side always implement FS with the strong variant.

TL,DR: either you have an inefficient protocol or you need to assume a non-standard RSA assumption, called the Adaptive Root assumption.


What does it mean : "Canonical representative of Sbox is 0123468A5BCF79DE"? and How can we calculate this representative for Sbox?

Let's start with the basics: a bijective 4×4 bit S-box is a permutation of the set $\{0,1\}^4$ of 4-bit bitstrings.  These bitstrings can be viewed as the binary representations of the integers from $0$ to $15$, which in turn are naturally represented by hexadecimal digits.  Thus, we can also regard a 4×4 bit S-box as a permutation of the hexadecimal digits 0123456789ABCDEF.

A common compact way of representing a permutation of a finite naturally ordered set (such as the hex digits listed above) is to list the results of applying the permutation to each element of the set in order.  Thus, for example, the string 0123468A5BCF79DE represents the permutation:

0123456789ABCDEF
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
0123468A5BCF79DE

(See e.g. this answer for examples.)  While the article you've linked does not seem to actually define this notation, I'm all but certain that this is what they mean.

The story doesn't end here, though.  The article you've linked does not discuss individual S-boxes, but equivalence classes of them.  One type of equivalence is defined at the beginning of section 3 (formatting original, [editorial notes] mine):

  Definition 5. Let $M_i$ and $M_o$ be two [4×4] invertible matrices and $c_i$ and $c_o$ two [4-element] vectors [over $\mathbb F_2$]. The S-Box $S'$ defined by two affine transformations $$S'(x) = M_oS(M_i(x ⊕ c_i)) ⊕ c_o$$ belongs to the linear equivalence set of $S$; $S' ∈ \mathrm{LE}(S)$.

Later, in definition 7, the author also defines a narrower notion of equivalence of S-boxes, called "permutation equivalence" (PE), which is the same as the linear equivalence defined above, except that the 4×4 binary matrices $M_i$ and $M_o$ are further required to be permutation matrices.  (Note that these matrices represent permutations of the four bits in a 4-bit input/output bitstring, not permutations of the entire set of such 4-bit strings!)

The reason for considering these equivalence classes of S-boxes, instead of each S-box individually, is of course that any two S-boxes that only differ by a permutation of their input or output bits (and/or XORing those inputs and outputs with some constant bitstrings) have essentially the same cryptographic strength against attacks that don't care about such details, such as all those considered in the paper.

Anyway, to be able to usefully discuss these equivalence classes of S-boxes, we need to have some way to name them.  One obvious way to do that, which the author of the paper indeed uses, is to somehow pick one specific "canonical" S-box out of each equivalence class to represent it.  But which one?  The author describes their choice in definition 6:

  Definition 6. The canonical representative of an equivalence class [of S-boxes] is the member [whose compact representation as a list of hex digits] is first in lexicographic ordering.

For example, the S-boxes 0123468A5BCF79DE and 5BCF79DE0123468A are permutation equivalent as defined in the paper, since one can be obtained from the other by XORing the input with the 4-bit vector $1000$ (8 in hex) before applying the S-box.  But the string 0123468A5BCF79DE sorts before 5BCF79DE0123468A in lexicographic order (since 0 < 5), and indeed (assuming the author made no silly mistake) also before all other members of its equivalence class, making it the canonical representative of that class.

As for how to calculate the canonical representative of a particular equivalence class of S-boxes, given one member of the class, I believe the simplest (and possibly the only) way to do that is by brute force: just apply all possible input and output bit permutations (or invertible bit matrices, for linear equivalence) $M_i$ and $M_o$ and XOR masks $c_i$ and $c_o$ to the S-box to generate all members of the equivalence class, calculate the hex digit string representation of each of them, and find the one that comes first in lexicographic order.


what are the NTRU keysize and application in industry?

Usually, in public-key cryptography, the "key size" is implicitly referred to the size of the public key.

In the case of NTRU, both public and private keys are conveyed by the same thing: polynomials defined over a specific polynomial ring. These polynomials can be  represented as vectors in $\mathbb Z_q$ of size $N$. Therefore, raw public and private key will have the same size ($N \cdot \lceil\log q\rceil$ bits). For instance, with $N = 1171$ and $q = 2048$, which are recommended parameters, public and private keys are of size 1.57 KB.


Has human-generated entropy ever been a real problem?

In World War II, this practice of generating "random" code books by hand is known to have been used by the Special Operations Executive, or SOE:

  Various techniques have been used to do the random generation. Marks
  describes how SOE agents’ silken keys were manufactured in Oxford by
  little old ladies shuffling counters.

(Security Engineering: A Guide to building Dependable Distributed Systems)

The Marks mentioned there is Leo Marks, who was the cryptographer for SOE.  His book Between Silk and Cyanide describes a meeting with Commander Denniston of Bletchley Park:

  [Commander Denniston] questioned me closely about WOK-production, and
  wanted to know why we preferred keys made by hand to the machine-made
  keys supplied by Bletchley.

  I explained that Bletchley hadn't produced them in sufficient
  quantities, and that the ones which they'd sent us didn't seem to me
  as random as the keys the girls produced by shuffling counters.

  He looked at me doubtfully, so I gave him six sheets of keys produced
  by the girls, and six by Bletchley.  He correctly identified
  Bletchley's, agreed there was a pattern to them, ...

(WOK stands for Worked Out Keys, and is a hand-enciphered code using shared random keys to seed it)

While I'm unable to cite a specific instance of hand-generated random data being insufficient, I'm sure it happened.  The coding systems used in World War II, both manual and machine-based, generally relied upon unpredictable keys rather than strong cryptographic algorithms.  Attacks upon keying material were the primary focus (again, both by hand and by machine).  Any weakness in randomness could be exploited.

When you consider the fact that the systematic and massive compromise of Enigma was kept largely secret for around 30 years, the likelihood of a particular hand-shuffled one-time pad being compromised and documented as such is pretty low.  So the fact that examples don't abound isn't really noteworthy.

Neal Stephenson's fiction novel Cryptonomicon does include such a story (although, again, it's fiction) - Detachment 2702's one-time pad traffic is decoded for a few reasons, including re-use of pads but also insufficient randomness:

  "Enoch, why are you . . . here?"

  "Oh. I am here, in a larger sense, because Mrs. Tenney, the vicar’s
  wife, has become sloppy, and forgotten to close her eyes when she
  takes the balls out of the bingo machine."


It is an object, not a function. The difference is important: the thing you get with m = hashlib.md5() is a structure in memory that has an internal state. Each update() call updates that state (hence the name).

You can imagine the object has a kind of box. Each update() call accumulates input bytes in that box. When you want to obtain the hash value, the MD5 mathematical function is applied to the complete box contents. That way, it does not matter whether you put the bytes in the box as one or two or seventeen successive calls;  what matters is that you ultimately sent all the bytes in the box.

Technically, MD5 processes input data by blocks of 512 bits (64 bytes) and maintains a running state consisting of 128 bytes (16 bytes) along with a counter (the number of bytes that were hashed is used at the end of the function evaluation). Thus, a practical MD5 implementation will indeed contain a "box" (usually called a "buffer") that can accumulate up to 64 bytes; whenever 64 bytes have been accumulated, they are processed as per the MD5 specification, and the box is emptied. That way, the object remains small in RAM, even if you hash gigabytes of data.

Reading the specification to implement your own MD5 code is a very nice programming exercise, that is very enlightening. I recommend that you try it.


How should the key schedule be designed for this general block cipher?

It's not a good idea to assume that your F-function is strong by itself. With very few exceptions, it's not true even with professionally-designed Feistel networks. In fact, the reason Feistel networks are even needed is because they're used to build a secure PRP from an insecure PRP or PRF. Said insecure function must be designed so that it is extremely lightweight and is secure after sufficient iterations.

Without more information, no one can tell you how to design a key schedule. They're generally tightly integrated with the rest of the cipher. All we can do is give you possible designs that would be inefficient but would work, or which would only be secure assuming your F-function is a strong PRF (which is quite an assumption). You have to think about a few things when designing a key schedule:

Do you need key agility and if so, how light must the key schedule be?
How does it interact with the rest of the cipher (this is a very complex question)?
What is your maximum memory and ROM footprint?
Is side-channel resistance important to you?
What kinds of operations do you wish to implement it in?

If you are not making any assumptions about the F-function, then you could use an algorithm like HKDF to expand an input master key into an arbitrary number of subkeys. If you do assume that the F-function is a strong PRF, which it very likely will not be, then the key schedule could be as trivial as XORing a round counter (functioning as a round constant) with the key to derive each round key. That would be necessary to avoid the slide attack, but relies on assumptions about the F-function's security.


If you're operating in some finite field, and the PRG used to generate the coefficients and $x$ is cryptographically secure (that is, it is infeasible to distinguish the output of the PRG from a truly random source of field elements), and you go back to the PRG for every single message, then it is secure as far as privacy is concerned (of course, you need to make sure that $bx$ is nonzero; otherwise, it might be a bit tricky for the decryptor to recover $m$).

As for integrity, well, if the attacker replaces a ciphertext $C$ with another $C'$, then that will decrypt to some message $m'$, where $m - m' = I(C - C')$ for some invertible element $I$ which is unknown to the attacker.  This is why you want to do the operation in a finite field (rather than a finite ring); in a field, $I$ can be any nonzero value, and so while the attacker can make the altered ciphertext decrypt to something else other than m, but he literally has no control beyond that.

On the other hand, the simpler polynomial $P(x) = mx + a$ has the same property; if $a$ and $m$ is generated via cryptographically secure source and you're operating in a finite field, then transmitting $mx+a$ also provides privacy, and prevents the attacker from making nonrandom changes to the decrypted ciphertext.

This garbling property (where any change in the ciphertext will make a random change in the plaintext) is the best we can do if the ciphertext must be the same size as the plaintext.  Generally, that is not considered good enough, and usually we include an authenticate operation which makes the ciphertext strictly larger than the plaintext, but also makes sure that any change in the ciphertext will cause the decryptor to reject the modified message (rather than emitting a random decryption).


Feasibility of using a base 26 LFSR for cryptography by hand

LFSR theory, for an $n$-bit register uses an isomorphism between the shift operation, and the multiplication of a polynomial in $\mathbb{F}_2[X]$ by $X$; the multiplication is taken modulo a given polynomial $P$ of degree $n$; that modulus polynomial is the one defined by the position of the "feedback" bits and we usually want it to be primitive (i.e. irreducible, and such that $X$ generates, with the multiplication, all the non-zero polynomials modulo $P$). The XOR operation is, in fact, an addition of polynomials, i.e. a pairwise addition of monomials. In $\mathbb{F}_2$, values are bits and addition is XOR.

This extends to any finite field. But there is no finite field of size 26. What you can do is to map letters to integers modulo 26, and compute in the ring of such integers. By the Chinese Remainder Theorem, when you do arithmetic operations modulo 26, you are actually doing them in $\mathbb{F}_{13}$ and $\mathbb{F}_2$ simultaneously. So the theory can be applied through the CRT.

Namely, you could select a polynomial $P = X^n + \sum_{i=0}^{n-1} p_i X^i$ where each $p_i$ is equal to $0$ or $1$ (only), such that $P$ is primitive both in $\mathbb{F}_2$ and $\mathbb{F}_{13}$. The corresponding base-26 LFSR will then operate as the CRT mixture of a base-13 and a base-2 LFSR, of respective periods $13^n-1$ and $2^n-1$. Total period would be the least common multiple of these two values.

Notes :

Though LFSR have good statistical properties, for cryptography they tend not to be very good (e.g. you cannot keep the feedback polynomial $P$ secret, because of the Berlekemp-Massey algorithm). A secure LFSR-based stream cipher will need a trick, normally irregular clocking, as in A5/1. Resistance of A5/1 to cryptanalysis is roughly two thirds of its internal size (i.e. $2^{64·2/3}$) which is not high and allows for a lot of practical precomputations. For a "manual" LFSR, you may need to use a state size which will make it impractical. Also, the CRT duality can make analysis more complex. I suppose that a A5/1-like base-26 stream cipher can be designed and be secure, with a big enough internal state, but I don't have clear ideas on how big is "big enough".
You may have better luck using 32 signs (26 letters and some extra for spaces and punctuation). $\mathbb{F}_{32}$ is a field (not integers modulo 32, mind you; in $\mathbb{F}_{32}$, addition is indeed a XOR and each value, added to itself, yields a 0). However, you would also need a feedback polynomial where not all coefficients are $0$ or $1$ (otherwise you end up with running 5 binary LFSR in parallel). This can make the feedback rule application more complex.
A "manual" base-26 LFSR can be efficiently executed with a Scrabble game.


Practical quantum attacks on AES - Is AES-128 used in a block mode vulnerable to attack using quantum algorithms

Sure, you can use Grover's algorithm to attack AES-128 in CTR mode. Assume the attacker knows a few plaintext blocks and the counter. The AES ciphertext blocks that are generated by encrypting this counter and XOR'ing it with the plaintext. In that case the input and output of the AES-128 block cipher are known and Grover's attack can be applied (as if AES-ECB was used).

Similarly SHA-256 in HMAC mode could well fall for Grover's attack. But Grover's attack only halves the security of the symmetric algorithms. That means that for SHA-256 you would still be left with 128 bits of security for most situations.

However, SHA-512 is actually faster on 64 bit architectures than SHA-256, so it seems a good idea to use that if you can spare the space (and otherwise SHA-512/256 exists as well). Note that later Intel and AMD CPUs may contain Intel SHA-1 and SHA-256 instructions that offer hardware accelleration. So the performance of SHA-256 is much higher, easily beating SHA-512, if those instructions are utilized.

So yes, AES-128 could fall to Grover's attack and although HMAC-SHA256 is considered pretty secure, it does make sense to at least design your protocol in such a way that future updates to the protocol are a possibility. Although there is no pressing need to change from AES-128 or HMAC-SHA256, in general you want your algorithms to be configurable for different versions of the protocol.

The only reason to switch now is to make sure that captured sessions cannot be decrypted in the future. In that case you may also have to look at the way the session keys are calculated. Asymmetric algorithms, for instance, are much more vulnerable to QC crypt-analysis. So if you're dealing with that level of confidentiality you should switch to AES-256 as soon as possible.


ECC public key encryption and authentication - ECIES with ECDSA vs ECDH with AES

ECDH or DH for that matter doesn't provide any authentication of a user. ECDSA as a public key scheme does provide authentication, but lacks validation. You need to certify that the exchanged public keys are indeed from Alice or Bob. So Alice and Bob must let an authority certify their own public keys such that Alice trusts the authority of Bob and Bob trusts the authority of Alice. The authorities might in fact be the same authority. You can call it certificate authority.

A possible attack might be a man-in-the-middle attack where

Alice sends $K_A$ to Bob, but Martin intercepts $K_A$ and sends a newly generated key $K_{MA}$ to Bob
Bob sends back his public key and a signature, containing both public keys and her identity: $K_B,Sig_B(K_B,K_A,A)$, but Martin intercepts it and sends a newly generated key $K_{MB}$ and re-signs with its private key $Sig_{MB}(K_{MB},K_A,A)$
Alice replies similarly with her signature: $Sig_A(K_A,K_B,B)$, but Martin intercepts it and re-signs $Sig_{MA}(K_{MA},K_B,B)$ with the private key $MA$ from #1.

This is applicable to ECDH and ECDSA.


Factors of the group order to secure against Pohlig-Hellman

[Isn't this] just as hard as the RSA problem?

Oddly enough, no.  If we were given a random $p$, and were asked to see if there's a large prime factor $q$ of $p-1$, yes, that would be, on average, a hard problem.  However, that's not what we actually do.

Instead, we get to pick $p$, and so that gives us a lot of flexibility.

One way is to pick $q$ first (for example, a 256 bit prime), and then search for 1024 bit values $kq + 1$ that happen to be prime; if we call the value we find $p$, then we know that $p-1$ has a large prime factor $q$.

Alternatively, we can search for values $p$ where both $p$ and $(p-1)/2$ are both prime; this takes longer, but is still quite feasible.  And, in this case, we know that $p-1$ has a large prime factor, namely $(p-1)/2$.

You can find both these strategies being applied in practice.


The Lindell and Katz, in their book, give the definition as follows;

  An encryption scheme $(Gen,Enc,Dec)$ over a message space
  $\mathcal{M}$ is perfectly secret if for every probability
  distribution of over $\mathcal{M}$, every every message
  $m\in\mathcal{M}$, and every ciphertext $c \in \mathcal{C}$ for which
  $Pr[C=c]>0$;

  $$Pr[M=m|C=c] = Pr[M=m]$$

We can view this definition as the distribution over messages and ciphertext are independent.

The proof used this definition and the equivalent definition of perfect secrecy

$Pr[C=c|M=m] = Pr[C=c]$

and, this can be said, the ciphertext reveals no information about the plaintext other than the size.

On your proof;

On the third P, on the numerator and denominator;

$Pr[Enc_k(m_1)=c] = Pr[Enc_k(M) =c | M=m_1]$


In PALISADE, CKKS is configured to use $\alpha = 8/q$ (using the definition of $\alpha$ in the LWE estimator). This corresponds to the standard deviation of $8/\sqrt{2\pi} \approx 3.19$. This value was chosen based on the HE security standard at https://homomorphicencryption.org/standard/
You can manually change this value from 3.19 to something else by modifying $\textbf{genCryptoContextCKKS}$ in https://gitlab.com/palisade/palisade-release/-/blob/master/src/pke/lib/cryptocontextfactory.cpp


Does Signal Application use Eliptic Curve cryptography for encryption as well?

Signal Double Rachet and X3DH protocols for key initialization and session/temptorary encryption key generation. Whilst the XEdDSA and VXEdDSA are used for signing.

All of the schemes are based on X25519 and X448 curves.


SSL-like protocol with public-key hard-coded in the client

If the application completely trusts the public key (e.g., runs code signed by it), then you could add "master key change" messages that can be signed by it, that make the application change it's hard-coded key. For additional security, you could require that the new key be additionally signed by a key hopefully separated from the now-compromised one - here decent options are either an additional more-secured key or confirming the new master key via HTTPS (trusting the CA hierarchy).

Of course in all methods you must ensure the client gets reasonably recent revocation messages - which may require periodic signing of "non-revocation" messages - but note that CRLs have this problem too.


Sign a self-signed X.509 certificate using PGP signature generation.

Let the web user create a self-signed X.509 certificate and store the certificate and private key in a PKCS#12 key store. Then create a PGP signed container with this certificate included. Let the web server put it in a trust store after verifying & stripping the PGP signature. The client needs to configure the PKCS#12 soft token with the browser used (or the Windows store, if IE / Edge / another SChannel based browser is used).

You would need to provide guidance to the users on how to create the self signed certificate and how to put the self signed certificate and private key store in the local key store of the browser. You could also create an application to do this for the users.