In Elliptic Curve, what does the point at infinity look like?

You can think of the point at infinity as an extra point kludged into the set to make the curve work out as a group, but that's a little unsatisfying: in the geometric picture of a curve there's no place for the point at infinity, and in the algebraic construction the point at infinity is this weird magic object $\mathcal O$ with no coordinates.

$$E := \{ (x, y) \in k^2 \mid y^2 = x^3 - x + 1 \} \cup \{\mathcal O\}$$

Instead, it is better to think of things in projective coordinates: $$E := \{ (X : Y : Z) \in \mathbb P^2(k) \mid Y^2 Z = X^3 - X Z^2 + Z^3 \}.$$  Here the notation $(X : Y : Z)$ means the set of all triples $(\lambda X, \lambda Y, \lambda Z)$ for some $\lambda \in k$, or equivalently the line in the three-dimensional space $k^3$ that passes through the origin $(0, 0, 0)$ and the point $(X, Y, Z)$, provided at least one of $X$, $Y$, or $Z$ is nonzero.  Notice that I didn't write $\cdots \cup \{\mathcal O\}$: as it happens, there is a natural set of projective coordinates for the point at infinity, namely $(0 : 1 : 0)$ (or $(0 : 2 : 0)$, or $(0 : 128364/2486 : 0)$, etc.).

Not only is there a natural set of projective coordinates, but there is a geometric picture too.  If we paste the picture above on the plane $z = 1$, we are taking the intersection of all the projective lines $(X : Y : Z)$ satisfying $Y^2 Z = X^3 - X Z^2 + Z^3$ with the affine points $(x, y)$ satisfying $y^2 = x^3 - x + 1$ pasted on the plane $z = 1$—all except for one such projective line:

The one exception is the $y$ axis, $(0 : 1 : 0)$, which is exactly the point at infinity!  If you draw lines from the origin to the affine curve pasted on the plane $z = 1$, that is if you map $(x, y) \mapsto (x : y : 1)$, as you get further and further out the wings of the curve, the line gets closer and closer to the $y$ axis—along both wings!  In the limit toward infinity, which has no affine coordinates, you just get the $y$ axis $x = z = 0$.  For every other point, affine coordinates can be computed by $(X : Y : Z) \mapsto (X/Z, Y/Z)$.

So while it doesn't show up in the affine picture, the point at infinity has a natural geometric and algebraic interpretation in projective coordinates of lines through the origin.

Appendix A: Asymptote code for affine elliptic curve plot

import graph;

size(5cm, 0);

pair O = (0,0);
pair X = (1,0);
pair Y = (0,1);

// y = F(x) = sqrt(f(x))
real f(real x) { return x^3 - x + 1; }
real df(real x) { return 3*x^2 - 1; }
real F(real x) { return sqrt(max(0, f(x))); }

draw(-2X -- 2X, arrow=Arrows(TeXHead), p=gray(2/3) + dashed,
  L=Label("$x$", position=EndPoint, align=S));
draw(-3Y -- 3Y, arrow=Arrows(TeXHead), p=gray(2/3) + dashed,
  L=Label("$y$", position=EndPoint, align=E));

real lo = newton(f, df, -1);
real hi = 2;

guide g = graph(F, lo, hi, Hermite);
draw(g, arrow=Arrow(TeXHead));
draw(reflect(O, X)*g, arrow=Arrow(TeXHead));

Appendix B: Asymptote code for projective elliptic curve plot

import graph;
import three;

size(10cm, 0);
currentprojection = perspective(4, -8, 4);

// y = F(x) = sqrt(f(x))
real f(real x) { return x^3 - x + 1; }
real df(real x) { return 3*x^2 - 1; }
real F(real x) { return sqrt(max(0, f(x))); }

draw(-Z -- 2Z, arrow=Arrows3(TeXHead2), p=black + dashed,
  L=Label("$z$", position=EndPoint, align=N));
draw(-2X -- 2X, arrow=Arrows3(TeXHead2), p=black + dashed,
  L=Label("$x$", position=EndPoint, align=E));
draw(-3Y -- 3Y, arrow=Arrows3(TeXHead2, arrowheadpen=emissive(red)),
  p=red + dashed,
  L=Label("$y$", position=BeginPoint, align=W));

dot(O);
draw(shift(Z)*scale3(0.1)*unitdisk, surfacepen=emissive(gray(2/3)));

real lo = newton(f, df, -1);
real hi = 1.8;

// Draw the curve on the z=1 plane.

guide gp = graph(F, lo, hi, Hermite);

draw(shift(Z)*shift(-2X)*shift(-3Y)*plane(4X, 6Y), p=gray(2/3));
draw(shift(Z)*(-2X -- 2X),
  arrow=Arrows3(TeXHead2(Z), arrowheadpen=emissive(gray(2/3))),
  p=gray(2/3) + dashed);
draw(shift(Z)*(-3Y -- 3Y),
  arrow=Arrows3(TeXHead2(Z), arrowheadpen=emissive(gray(2/3))),
  p=gray(2/3) + dashed);

draw(shift(Z)*path3(gp), arrow=Arrow3(TeXHead2(Z)));
draw(shift(Z)*path3(reflect((0,0),(1,0))*gp), arrow=Arrow3(TeXHead2(Z)));

draw(unitsphere,
  surfacepen=material(white + opacity(0.5), ambientpen=white));

// Draw the curve on the surface of the sphere.

guide3 gs;

int nsamples = 400;

// Sample with linear spacing for the first part of the curve.
for (int i = 0; i < nsamples; ++i) {
  real x = lo + ((hi - lo)*(i/nsamples));
  real y = F(x);
  gs = gs -- unit((x, y, 1));
}

// Then sample with exponential spacing for the rest.
for (int i = 0; i < nsamples; ++i) {
  real x = hi + (exp(200*(i/nsamples)) - 1)/100;
  real y = F(x);
  gs = gs -- unit((x, y, 1));
}

// Oughta converge to the Y axis.
gs = gs -- Y;

// Draw all four copies of the same shape.
draw(gs);
draw(reflect(O,X,Z)*gs);
draw(reflect(O,X,Y)*reflect(O,Y,Z)*gs);
draw(reflect(O,X,Y)*reflect(O,Y,Z)*reflect(O,X,Z)*gs);

// Draw some sample points in projective space on the curve.

void
showpoint(real x, pen p=blue)
{
  real y = F(x);
  triple P = (x, y, 1);
  draw(-P--1.5P, arrow=Arrows3(TeXHead2, arrowheadpen=emissive(p)), p=p);
  dot(P, p=p);
  dot(unit(P), p=p);
  dot(unit(-P), p=p);
}

showpoint(lo + 0.3);
showpoint(lo + 1.0);
showpoint(lo + 2.0);
showpoint(lo + 2.8);

// Axis line already shown; add a dot.

dot(Y, p=red);
dot(-Y, p=red);


Is there any restriction in using lossless compression algorithms for huge key sizes?

The problem is that the key is essentially random data and thus cannot be meaningfully compressed. Several variations of the McEliece cryptosystem have tried modifying it to produce public keys with special structure which are compressable. However, all such systems have been broken (as far as I know), and it seems that in most cases, adding special structure like that makes it more vulnerable to attack.


If you have a secure MAC algorithm $M$ and a collision-resistant hash function $H$, then you can define another secure MAC algorithm $M'$ such that $M'(x) = M(H(x))$. Historically, though, HMAC was defined as a construction that provides reasonable security as a MAC even for an underlying hash function which is a bit flaky in that respect (in that case, Merkle-Damgård functions like SHA-1, that suffer from the so-called length extension attack, which illustrates the subtleties of MAC-building out of hash functions).

(For reference, my comment in the TLS-1.3 mailing-list is about the need to buffer incoming data until the MAC can be verified; this is unrelated to the moment the key is injected in the MAC process.)


If performing as in a typical description of textbook RSA, Bob has:

secretly drawn distinct primes $p=83$ and $q=103$;
computed $n=p\cdot q=8549$;
computed $\varphi(n)=(p-1)\cdot(q-1)=8364$ where $\varphi(n)$ is Euler's totient function;
chosen $e=445$, as some arbitrary $e>1$ with $\gcd(e,\varphi(n))=1$;
published his public key $(n,e)\;$, which in particular Alice knows;
computed $d=e^{-1}\bmod \varphi(n)\;$ using the extended Euclidean algorithm, giving $d=7537$; Bob's private key is $(n,d)$, and he does its best to keep $d$ secret.

The definition of RSA worded in PKCS#1 allows Bob to choose $d$ as any positive integer less than $n$ such that $e\cdot d-1$ is a multiple of $\lambda(n)$, where $\lambda$ is Carmichael's function, with (since $n$ is the product of distinct primes $p$ and $q$) $\lambda(n)=\operatorname{lcm}(p-1,q-1)=4182\;$. That allows $d=e^{-1}\bmod\lambda(n)\;$, which is the smallest positive working $d$ (here $d=3355\;$), and often gives Bob a little less work when using his private key. Bob would have more than two possible $d$ for some other choices of $p$ or $q$, or if we removed the mathematically arbitrary constraint $0<d<n$. In particular, $d=11719$ or $d=-827$ are functional.

Factorization

One way Alice has to find Bob's private key is to factor $n=8549$, finding it's prime factors $83$ and $103$. She then knows, within order, the $p$ and $q$ chosen by Bob at step 1, can repeat steps 3 and 6, and find Bob's private key as computed in step 6. However that's prohibited by the question's "without using the definition $d=e−1\bmod\varphi(n)\;$". More importantly, if Bob had chosen $p$ and $q$ as random primes of more than 384 bits, Alice would have to perform a factorization more difficult than was ever openly performed. For random 1024-bit primes (a common practice), Bob is likely safe from a factorization of his $n$ directly from $n$, for the time being.

Enumeration

As pointed by poncho, Alice can find by enumeration the smallest positive odd $d$ such that $((r^e)\bmod n)^d\bmod n\;=r$ for $r$ the first few primes. That will give Alice $d=3355$, after in the order of $1700$ modular multiplications (noting that most unsuitable $d$ will be eliminated for $r=2$, and that going from one candidate $d$ to the next can be done with a single modular multiplication by $r^{2e}$). That will give Alice the smallest working $d$ such that $(n,d)$ behaves as Bob's private key. Alice may not have calculated Bob's actual private key, but the difference is semantic and it could be fixed by various methods. However, that way of finding $d$ would be impractical if Bob had chosen $p$ and $q$ as primes of $45$ bits or more.

Other ways

Alice can perform as she claims in several other ways:

coerce Bob to reveal his private key, by force, law, or trickery;
read the information about Bob's private key from the device(s) Bob uses to store his private key or make use of it; absent encryption under a strong passphrase (e.g. stored un-encrypted, or under the protection of a short PIN), only physical security measures can prevent such extraction once Alice gets her hands on the device(s); Alice's job is made significantly easier by the fact that she can verify a guess of $d$ (e.g. by the method used for enumeration);
as a special case of trickery (or law, in some countries and times), steal Bob's private key by using a Trojan horse somewhat planted in Bob's device(s); the insertion could be by Bob unknowingly (letting some vulnerable software) installing the trojan; by some evil maid; during transport of the device before delivery to Bob; or by (exploitation of a weakness left by) the manufacturer of (some part of) the device at time of manufacture (intentionally or not); there are numerous accounts of such practices, and it is extremely difficult to demonstrate one is safe from them (it is easier to be likely safe from them);
as a refinement of read above, analyze the power consumed, the electromagnetic radiation, or perhaps just the noise emitted by Bob's device(s) when Bob uses his private key, which in the most naive implementations of RSA will directly leak the bits of $d$;
other side-channel attacks, including timing, allowing factorization of $n$, then performing steps 3 and 6;
fault attacks: for some possible construction of Bob's device, induce it to make computation errors when using his private key, and exploiting the erroneous results to factor $n$; this is the so-called Bellcore attack: D. Boneh, R. DeMillo, and R. Lipton, On the importance of checking cryptographic protocols for faults (pdf); however if Bob's device checks its results before revealing them, by way of the public key, as it should, this attack simply won't work.


Is it possible to anonymize web traffic so that the IP Address cannot be determined while still being able to determine distinct IPs?

In general, against an attacker that has fully compromised your webserver, your full requirements are unsatisfiable.

The reason is that, in order to find out which requests have been made from a given IP address, the attacker can always simply fool your server into thinking it has received a request from that address, and then compare the resulting log entry to the others.  (Of course, there may be more direct ways to achieve the same result, but this is a generic attack that works against any scheme.)

Conversely, against attackers who don't have full access to your webserver, but only to the logs, there's a simple solution: store a secret key on the server (in some way that will keep it out of the attacker's hands) and tag each log entry with HMAC(key, address).  Without the key, an attacker cannot distinguish HMAC from a random function; in particular, they won't be able to tell anything useful about the HMAC tag except that each IP address corresponds to a particular tag.

However, it's generally pretty hard to ensure that attackers can't get the key (and can't otherwise fool the server into logging a fake request) even if they can somehow get access to the database.  Just storing the key in, say, a secure hardware security module isn't enough, since the generic fake request attack still applies, so basically you need to harden your entire webserver.

You'll also want to make sure that your server isn't vulnerable to IP spoofing, e.g. by making sure that your TCP sequence numbers are unpredictable, and that requests are only logged after packets have been exchanged both ways between the client and the server.  Otherwise that would provide yet another way to create fake log entries without having to directly compromise the webserver at all.


Can iterated key expansion in Blowfish slow down bruteforce attacks on small key sizes?

Something similar as what you suggest is already known as "Expensive key schedule Blowfish", or "EksBlowfish". It is the encryption algorithm in the core of Bcrypt (a slow hash function designed for password hashing).

It also incorporates a salt, and its setup function is like this (retyped from the paper):

EksBlowfishSetup(cost, salt, key):
   state ← initState()
   state ← ExpandKey(state, salt, key)
   repeat(2^cost):
      state ← ExpandKey(state, 0, salt)
      state ← ExpandKey(state, 0, key)
   return state

InitState() is the same as in Blowfish: It fills the P- and S-boxes with digits of $\pi$.
ExpandKey(state, 0, ...) also works just like the key expansion function of Blowfish - it XORs the P-boxes with (a repeated version of) the key, then encrypts a zero stream in CBC-mode with Blowfish (using the existing state), replacing the boxes with the results after each block is encrypted. The version with a salt parameter simply uses this salt (repeated) as the original value to encrypt.

The actual encryption of EksBlowfish works just like normal Blowfish encryption. In Bcrypt, this is then used to encrypt (64 times in ECB-mode) the 3-block ASCII-string OrpheanBeholderScryDoubt to produce the bcrypt hash, but you can use EksBlowfish also separately.

It can't get worse than "normal" Blowfish, and will get as hard to bruteforce as a bcrypted password with same cost factor.
I suppose you could use a constant salt, but using some random (but not secret) salt delivered with the message looks better (and avoids precomputation). If your performance is critical, you should of course not change the salt with every SSL packet.

There is another problem with Blowfish: It only has 64-bit blocks, and as such can't get more secure than any 64-bit block cipher. Repeating blocks will occur likely after $2^{32}$ blocks (i.e. 32 GB), which might be enough or not, depending on your application. And repeated blocks give points of attack.

You might consider instead using a 128-bit block cipher like AES, and derive your key with bcrypt from the "short" 64-bit key.


Key Agreement between two nodes of a Wireless Sensor Network

Yes, using identity-based cryptography; in particular the Sakai-Ohgishi-Kasahara non-interactive key distribution protocol, generalized in "Provably secure non-interactive key distribution based on pairing".

The downside is that it requires a "Private Key Generator", a trusted party which is able to compute the private key of any node. The private keys also need to be securely deployed in each node.

Using the protocol, each node will have and ID. They simply need to exchange IDs and will be able to compute a shared key.


RSA signing - does EMSA-PKCS1-v1_5 padding need to be verified?

Is step #3 (verifying the EMSA-PKCS1-v1_5 padding) important to the security of the system?

Yes. That's paramount for small RSA public exponent $e$.

For $e\in\{3,5,7\}$, the easily computed integer $s=h^{(e^{-1}\bmod2^{254})}\bmod2^{256}$ is an acceptable signature for any message with an odd SHA-256 hash $h$ (that is about one message out of two). The attack can be extended to $e=9$, and with significant computational effort to $e=11$, by trying multiple messages until $s$ thus computed verifies $s<\sqrt[e]N$. The number of odd $h$ to try is about $2^{256}/\sqrt[e]N$.

That works because by construction of $s$, it holds $s^e<N$, therefore $s^e\bmod N=s^e$. Therefore $(s^e\bmod N)\bmod 2^{256}$, which is what's checked by the question's faulty signature verification procedure, is $h^{(e^{-1}\bmod2^{254})e}\bmod2^{256}$, that is $h$ for odd $h$ (notice such $h$ is coprime to $2^{256}$ and $\lambda(2^{256})=2^{254}$, where $\lambda$ is the Carmichael function, such that $\forall m>0$ and $\forall a$ coprime to $m$, $a^{\lambda(m)}\bmod m=1$).

If there is an attack working for $e\ge13$ for the question's parameters, I want to know. But as the saying attributed¹ to the NSA goes: "Attacks always get better; they never get worse".

The conclusion is that we should fully check RSA signature padding. In my opinion, it's not a sufficient reason to systematically avoid very small $e$, which should only be an extra precaution taken when we can afford the $\approx8$ time penalty in signature verification incurred by using the standard $e=F_4=2^{(2^4)}+1=65537$. Additionally, we should use a padding with an argument of reducibility to the RSA problem like that in RSASSA-PSS, or ISO/IEC 9796-2 scheme 2 or 3.

Incorrect verification of PKCS#1 V1.5 type 01 signature at least used to abound. That was first made public by Daniel Bleichenbacher's RSA signature forgery based on implementation error (account by Hal Finney of Crypto 2006 rump session). Among later derived attacks: Ulrich Kühn, Andrei Pyshkin, Erik Tews, Ralf-Philipp Weinmann, Variants of Bleichenbacher’s Low-Exponent Attack on PKCS#1 RSA Signatures; and the BERserk vulnerability. I have always wondered if "never attribute to malice what can be attributed to incompetence" really applies to these faulty implementations.

¹ by Bruce Schneier in Applied Cryptography IIRC.


Statistical (innefective) Fault Attacks on DES

In case you are still wondering, the answer to this question is "Yes".
DES can also be targeted by the same sort of attack.

This was actually already almost entirely done against DES in a paper from 2006, by F. Amiel, C. Clavier and M. Tunstall called "Fault analysis of DPA-resistant algorithms", you can look at section 6 and the next ones, in which they show that both known and unknown faults against the S-Boxes of DES can lead to a full key recovery. What they did not cover is the case where you have a fault countermeasure in place, either a detection or an infective one.

Now, if you have some fault countermeasure, but are able to target specific location of your S-Boxes, then performing this attack remains easy. But, if you are in the unknown fault setting, with fault countermeasure, you'll need to use the same statistical tools as in the SIFA paper, but would eventually also be able to recover the key. It just needs some tweaking.


You cannot create a verifiable $Z$ but you can create a verifiable $W$ but you have to add public keys multiple times as well. So $W$ can be verified using a key $PK_a + 2*PK_b + 2*PK_c + PK_d$ if you had the same message or doing having multiple pairings for each repeated key in case of distinct messages


Possibility of Man-in-the-Middle on X3DH

This is "covered" by section 4.1 of the X3DH spec:

  Before or after an X3DH key agreement, the parties may compare their identity public keys $IK_A$ and $IK_B$ through some authenticated channel. For example, they may compare public key fingerprints manually, or by scanning a QR code. Methods for doing this are outside the scope of this document.

Signal and WhatsApp both support verifying identities through QR codes, and provide a warning (optional in WhatsApp) if the other party's identity public key changes. That would stop MITM attacks, or make them detectable, though in practice almost no one does the verification.

Also note that the connection between the app and server is TLS-protected, so any MITM attack would need to be carried out by compromising the server itself.


Recommended skills for a job in cryptology

It seems we have aligned interests. I'm also a university student (although I am a math/comp sci double major) looking to pursue a career in cryptography. To that end, I have been self-studying it for a while now. So, take what I say with a grain of salt. As a forewarning, this post focuses specifically on what topics cryptographers often encounter and less about what, as a person, makes you useful as an employee to a crypto-agency.

From what I can best tell, the requisite knowledge of computer science is entirely dependent on what you want to do with cryptography exactly. If you are looking to work in an applied area, then you had best had a strong grasp of the basics of computer science. If you are implementing algorithms, then you will likely need to know the basics of modern-day computer architecture.

The reasons for this are many-fold. First, an understanding of computer architecture will allow you to optimize code like no other. For instance, a knowledge of things like instruction-level parallelism and pipelining is incredibly important because taking proper advantage of both can seriously speed code up. Second, you may need to know some basics about architecture in order to ensure security of your scheme. For instance, if you are working with smart cards, you will need to be able to design, or at least verify the security of, tamper-resistant circuitry.

Further, you will need a strong knowledge of C, which sits so close to the hardware that it isn't too far a step away anyways. From what I can tell, the vast majority of "serious" crypto code is written in C, even if it has a language wrapper around it (e.g. PyCrypto). Other languages, especially interpreted ones, simply do not allow the same performance as C, and we do like performant implementations. Another selling point of C is that, in crypto, you are most often working with raw bytes and bits, which is exactly where C shines. It's the de facto language for low-level work.

To that end, I would really recommend you pick up a minor in computer science if you are going to work with applied cryptography at all. Relevant courses include introductory programming, operating systems, assembly language, architecture, and complexity theory. There are lots of computer science resources on the web, though, so don't feel too discourage if a minor is simply not possible! An excellent C resource is Learn C the Hard Way. If you want to know more about operating systems (especially important if the code you write will be run on a real-life computer...) then Operating Systems Design and Implementation is an excellent resource. Unfortunately, I don't know of a good reference on computer architecture because of the extreme fast-paced movement in the field; I recommend trying to understand some of the optimizations current crypto algorithms implement.

Of course, to get very far in crypto, you will have to have a strong understanding of mathematics. The Handbook of Applied Cryptography, an excellent reference for crypto in general (with the entire book free online, by the way, on the linked site), has an entire chapter devoted solely to the mathematical background necessary, and then another entire chapter just for number theoretic problems. Since you are a math student, this is probably where you shine.

The HAC lists probability theory, information theory, complexity theory, number theory, and abstract algebra as being introductory background material, and the rabbit hole just goes deeper and deeper. In that list, I don't think there is any particular area that is neglected; all of them are used frequently in different areas of crypto. I can give specific examples if you would like.

You will also need the tools of theoretical computer science. (Sometimes, you will even see cryptography as a field under theoretical computer science, though I feel this definition is rather restrictive.)

Of course, complexity theory is already on the list, and it is indeed the premier star of the show as far as TCS topics in cryptography go. But you might also need to know a few models of computation, e.g. Boolean circuits, Turing machines, random access machines, and the like, because sometimes they're important to a particular problem. (For instance, Craig Gentry used Boolean circuits as the computational model in his fully homomorphic encryption scheme presented in his thesis.) You might consider these models of computation a part of computational complexity theory, though.

Information theory is also on the list of topics in the HAC, and you might find it sometimes included in theoretical computer science lists. Honestly, the line between theoretical computer science and math is often blurred.

For good references in theoretical computer science, I would first recommend a good text on complexity theory; the one I studied was Computational Complexity by Papadimitriou. The wonderful folks over at cstheory.se recommend two other works on complexity theory, but I can offer no evaluation of either. They also have a post devoted to some good books for crypto, which I just now spotted! There are some on the list there I haven't seen. The full post is, in general, worth checking out, but I thought I would link you to crypto-specific areas.

Of course, there are areas of cryptography that are, shall we say, less often "applied" to the real world than others. An example of such is the idea of a zero-knowledge proof, namely proving you know something without revealing what that something is. These things are applied sometimes, and their applications are fantastic, but they haven't been --- as far as I can tell --- widely adopted as, say, generic "guarantee confidentiality and integrity" areas of crypto (e.g. things like AES+HMAC). At least, not in the public eye. If you are not convinced, take a look at the front page of this StackExchange.

For a good reference on "theoretical" crypto topics, I would highly recommend Foundations of Cryptography by Goldreich. It's a two-volume work and covers the real theoretical material lurking in the background. The second book is more applied than the first. Further, Katz and Lindell's Introduction to Modern Cryptography is also quite good, although I haven't studied it extensively.

Of course, there are also generic crypto references, which is probably what you're most after here. Applied Cryptography and other books by Schneier (et al?) are good. The HAC, which I linked to above, is an excellent tome, touching on tons of topics in applied crypto with a heavy dose of theory too. The post I linked to above (on cstheory.se) has a few recommendations too. For a good history of the subject matter, I would highly recommend (if you want brevity) The Code Book, which is a really nice overview of the history of crypto. Of course, if that interests you, there is always the tome on the subject, Kahn's The Codebreakers. You can also see Thomas Pornin's excellent answer on a question similar to yours on security.se.

In short, this post is a high-level overview of some possible self-study options in crypto. Since I am only a university student, I can't tell you what employers do and don't want you know (especially not the NSA), nor can I tell you what topics are the most important in current-day research. I also make no claims that this post is complete and doesn't make glaring omissions. But I think it has been fairly accurate, at least to the extent that my knowledge and experience permit.


Isn't AES-NI useless because now the key length need to be longer?

No, AES-NI provides a hardware implementation of AES. Before AES-NI, anyone could have purchased a specialized hardware encryption device that ran AES in hardware. So having AES-NI doesn't really change anything. When key sizes are chosen, they must take into account that specialized hardware could be developed. So, the key sizes we use already take this into account.


There's a standard argument that NFS finite field discrete log computations can be factored into a precomputation for a particular group ($p$) and then a cheap computation to break each target $g^x$ and recover $x$.*  See, e.g., https://weakdh.org for an application of this in practice to justify scrambling in 2015 to eradicate 512-bit ‘export-grade’—i.e., breakable by the NSA in 1995—DH groups.

The reasoning then goes that if every application uses a different $p$, it eliminates the batch advantage of doing a precomputation in the first place: the bad people in Ft. Meade, MD, would have to repeat the costly precomputation for every application.  However, this precomputation is infeasible to do even once for sufficiently large groups: there's no evidence that humanity has the resources to do it for a well-chosen 2048-bit group in the foreseeable future.

But let's say you wanted to use bespoke DH groups for vanity's sake.  This poses several problems:

It's costly to find them—you can get a sense of how slow it is in the privacy of your own living room with the openssl dhparam command.
The parties in an application have to agree on a DH group, and validating the group according to standard security criteria is costly—and has been a source of vulnerabilities in practice.  Sometimes bogus DH parameters get hard-coded in software in the wild.
We have known since 1993 of theoretical ways to put back doors in DH groups, and more recently that they might even be practical for reasonable group sizes like 2048 bits (summary).

Just use the smaller-faster-safer-simpler X25519 and forget about finite-field Diffie–Hellman groups, or if you must use FFDH, use the RFC 3526 groups chosen semi-rigidly by the RFC 2412 process.

* This is the case for multiplicative groups of integers modulo a large prime $p$—that is, finite-field discrete logs in prime fields.  The story for binary fields is much worse, so nobody uses binary fields for this.  In contrast, no such precomputation is known for elliptic curve discrete log computations—there's factor of $\sqrt{n}$ cost advantage to attacking a batch of $n$ targets simultaneously over attacking each of them individually, but it doesn't break down into a target-independent precomputation followed by a low per-target costs.


Why does FIPS 180-4 require the final padding block start with a 1?

If you don't start the padding with a $1$ it is not completely obvious where the padding starts.

If the message ends in

$...011010$

and you pad it to

$...01101000000$

which zeros were part of the message and which part of the padding?

If the padding is $1000...$ you know it started at the last $1$ in the padded string.

$...011010$

$...01101010000$

Edit:
Considering Why does the padding in Merkle–Damgård hash functions like MD5 contain the message length?
This looks a bit like $10000...$ was used in the beginning and then the length was added for weaker assumptions on the compression function. In which case implementers probably complained that there are no real problems and that they didn't want to do any work, and that changes would require new certifications of products, etc. pp. and they ended up with this compromise which allows simply ignoring the last 64-bit block and using the old algorithms.


Rainbow Table - Number of Chains and Chain Length

You can't compute these without a lot of other parameters, the most basic being the size of the keyspace you are searching, are you using perfect vs non-perfect rainbow tables, etc. See, e.g., this paper on eprint for the gory details.


How were shift amount constants in MD5 found?

The rotation countsr (together with the order of access of the 4 words of the state) are engineered for fast diffusion, as documented in RFC1321:

  The shift amounts in each round have been approximately optimized, to yield a faster "avalanche effect". The shifts in different rounds are distinct.

The general idea is to move bits to a 32-bit position on which they previously had no or little influence (limited to the effect of carry propagation in 32-bit addition, which works only to the left, and has odds like $2^{-n}$ to influence the $n$th bit on the left of a particular one); also, the choice made should facilitate efficient propagation in the next few steps. Among particularly bad choices would be to change the constants r to a mix of 1 and 31; or to all 16.

I do not know if the choice made for MD5 turned out to prevent or facilitate attacks on collision-resistance.

All the other constants in the question are chosen with a nothing-up-my-sleeve rationale; that is, convincingly unlikely to have been chosen according to a hidden property. That includes numbers computed according to a simple formula unrelated to the rest of the context (like floor(abs(sin(i + 1)) × 2^32) is); or numbers matching an obvious pattern (like being the representation of the hex string 0123456789ABCDEFFEDCBA9876543210 according to the endianness used in the context).


How can I convert a mathematical formula into a logical formula?

Considering you are working in $GF(2)$, every multiplication is equivalent to a AND and addition to a XOR.

  $GF(2)$ also known as $<\mathbb{Z}_2,+,\times>$ is the Galois Field (GF) of two elements: $0$ and $1$.

  Because $GF(2)$ is a field,

  addition has an identity element ($0$) and an inverse for every element;
  multiplication has an identity element ($1$) and an inverse for every element but $0$;
  addition and multiplication are commutative and associative;
  multiplication is distributive over addition.

  One of the most interesting property of $GF(2)$ is its link with the logical functions over booleans. An analogy can therefore be done between the two:

  The field addition ($+$) correspond to the logical XOR operation ($\oplus$), also $\forall x \in GF(2), x + x = 0$.
  The field multiplication ($\times$) correspond to the logical AND operation ($\land$).

  Remarks: $0 + 1 = 1$ ($0 \oplus 1 = 1$) and $1 + 1 = 0$ ($1 \oplus 1 = 0$), therefore $x \mapsto x + 1$ is equivalent to the logical NOT. With this in mind, every booleans operations have an equivalent in $GF(2)$.


Given a secure PRF $f(k, x)$, is $f(x, k)$ also a secure PRF?

No. A PRF assumes that the key is chosen randomly.

Example based on @LuisCasillas's comment: With a secret random key, you cannot determine the key from input output pairs. If you reverse the role of key and input, then you have the question: Can you learn "input" ($k$) from output ($f(x,k)$) and "key" ($x$)?

Yes. If $F(k, x) = f(x, k) = E_x(k)$, where $E$ is a PRP, then you can recover $k$ from one input/output pair of $F$. If your output is $c = E_x(k)$ then anyone can compute $k$ if they know $c$ and $x$.
$$k = E^{-1}_x(c) = E^{-1}_x(E_x(k))$$

(Where $E$ is block encryption and $E^{-1}$ is the inverse, decryption.

This answers your question because a PRP is a PRF because a permutation is a function. (Or maybe I'm wrong on that. There should be a caveat for small blocksizes. The presence or absence of collisions could distinguish a PRP from a non-PRP PRF.)

However PRPs are an example, not the exception. It's still not safe in general. There can be chosen key attacks, related key attacks, weak key sets, etc. A specific algorithm with no weakness when used correctly is not guaranteed to also be free of weakness when used incorrectly.


Efficient Aggregate Signatures With Same Key

Can Bob, without interacting with Alice, generate a new aggregate signature for the entire message set, i.e. (M,s′), that validates with Alice's public key?

That would be troubling if Bob could sign anything verifiable by Alice's key (on behalf Alice).

  if there is a simpler and more efficient method available if there is only one signer. I am mainly concerned with validation speed.

I am not sure if it's the most efficient way, however, I may disclose how it was done in reality.  At one of the public sector publishers, the publisher is mandatory to digitally sign a set of publications and all their translations.  So the system generates a new message consisting of a list of publications and their hashes and then the whole list is signed. However - in this case, the concern here was signing speed (so the signing person doesn't need to enter her PIN into HSM for every single publication).


Difficulty of forging MACs based on linear functions over $GF\left(2^n\right)$

You are in the right direction.

First, some intuition. The idea is that $y = ax+b$ constitutes a line, and if you need two points in order to fully determine it. However, if you only know one point, and if you don't have any additional information, then it is not possible to determine which line is it since there are "infinitely many" lines passing through the given point (of course, since we're on a finite field there are finitely many, but you get the idea).

Now, for the formalization, imagine that $A$ queries the oracle on some $m$ to get $t = a\cdot m + b$ (let's ignore how $A$ chose $m$, maybe it was crafted in some way, perhaps $m=0$ as you said, but this will turn out to be irrelevant).
We claim that if $A$ successfully crafts another message-tag pair $(m',t')$ with $m=m'$, then it is because $A$ guessed $a$, which is not possible since it was chosen at random from a large enough domain.
Now, this is argued easily by something I already mentioned: given two different points on a line, you can get the line and therefore the coefficients $a,b$.
In other words, once you fix $(m,t)$ with $t = a\cdot m+b$, getting a new $(m',t')$ allows an adversary to find $a$ as $a = (m-m')^{-1}\cdot(t-t')$.
This finishes the argument.


How to derive a private/public keypair from a random seed?

How to derive a private/public keyset from a random seed?

In principle: seed a Cryptographically Strong Pseudo Random Number Generator with the random seed, and use it to generate the RSA key pair "normally". For the later, we could use FIPS 186-4 B.3.2.

Are there major security flaws with this approach?

Yes, the obvious one: any entity knowing the seed can compute the private key. We need to trust every such entity beyond the designated holder of the private key to only use the seed to compute the public key.
As an aside, deterministic RSA key pair generation may need extra work to be protected from side-channel attacks (timing, power analysis).
There's also a functional issue: RSA key generation is rather slow, and implementations often have no firm stated upper bound on their execution time.


About converting Leveled FHE to Pure FHE and the Circular Security Assumption

You need the "circular security" assumption to obtain an FHE scheme with a single public-private key pair, as you want to homomorphically decrypt using the private key $k_0$ (whose corresponding public key was used for encrypting the data) that is encrypted using a public key $k_1$.

If the public key $k_1$ used for encrypting the private key $k_0$ is the "partner" of the private key $k_0$ in the public-private key pair, then you can repeatedly use the encryption of $k_0$ under $k_1$ to get your pure FHE-scheme via Gentry's bootstrapping, but to prove security you need the "circular security" assumption (cycle length 1).

Otherwise there is some other private key $k_2$ belonging to the public key $k_1$, so that in your second application of Gentry's bootstrapping you now need an encryption of the private key $k_2$ under some public key $k_3$. You can define in this way a sequence of keys $(k_i)_{i\in\mathbb N_0}$ (where for odd $i$ the keys $k_i$ are public keys and for even $i$ private keys, and for $i$ odd the key $k_{i+i}$ is the matching private key for the public key $k_i$).

If all the keys $k_i$ are different, then you don't need the "circular security" assumption, but your system needs infinitely many different public keys as well as infinitely many different encryptions of private keys, which is not really satisfying. If you have some repetition, then you can choose $k_i = k_{i+2\cdot n}$ for some $n\in\mathbb N$, but for proving security you need the "circular security" assumption (cycle length n).


Maximum steganographic embedding rate not detectable by steganalysis?

It is an interesting question, let me clarify some points before.

Nowadays F5 can not be considered an advanced steganographic method. There are algorithms as for example HUGO[1] or WOW[2] that are much harder to detect. Usually these algorithms hide information in the bitmap. F5 hide information in the DCT coefficients and this is easier to detect. Therefore, let's assume that we are using one of these modern algorithms.

Almost every research in modern steganalysis is based on machine learning. The common framework can be found in [3] and uses a feature extractor called Rich Models and Ensemble Classifiers. Using this framework (or reading this paper and other papers dealing with the same issues) you can find a first answer. An example result could be about 80% of accuracy using HUGO with bitrate 0.40. Maybe HUGO with a bitrate around 0.20 or 0.10 can be acceptable for you.

There are a lot of similar papers with different techniques and different results, getting better in recent papers. But there exist an important problem in steganalysis: the Cover Source Mismatch (CSM). It is, in fact, a problem of machine learning called "domain adaptation" with a new name [4,5]. It refers to the problem of using the classifier with images from a different source from those with which it has been trained. Unfortunately, we never known the source or domain of the steganographer, so we always have the CSM problem. And this worsens the results.

If you take into account the CSM problem you will see that the results presented in some papers may be a little bit confusing. So, if you see something similar to my previous example (HUGO 0.40 with 80% of accuracy) you can not consider that HUGO 0.40 is insecure because if you have no access to the camera used by the steganographer, you can not train your classifier properly. Currently the CSM problems is an active area of research.

At this point, reading the referenced papers, we have the optimistic answer (it will be for example 0.20/0.40 using HUGO) because the CSM problem and the cautious answer (it will be for example HUGO 0.10 or lower).

[1] Pevný, T., Filler, T., Bas, P., 2010b. Using High-Dimensional Image Models to Perform Highly Undetectable Steganography. In: Information Hiding - 12th International Conference. pp. 161–177.

[2] Holub, V., Fridrich, J. J., 2012. Designing Steganographic Distortion Using Directional Filters. In: International Workshop on Information Forensics and Security (WIFS). IEEE, pp. 234–239.

[3] Fridrich, J., Kodovský, J., 2012. Rich Models for Steganalysis of Digital Images. IEEE Trans. Information Forensics and Security 7 (3), 868–882.

[4] Cancelli, G., Dorr, G., Barni, M., Cox, I. J., 2008. A Comparative Study of ±1 Steganalyzers. In: Multimedia Signal Processing, 2008 IEEE 10th Workshop on. pp. 791–796

[5] Ker, A. D., Bas, P., Böhme, R., Cogranne, R., Craver, S., Filler, T., Fridrich, J., Pevný, T., 2013. Moving Steganography and Steganalysis from the Laboratory into the Real World. In: Proceedings of the First ACM Workshop on Information Hiding and Multimedia Security. ACM, pp. 45–58.


How can a hash function that implements random oracle model have collision resistance?

As Ella Rose points out in a comment, it is not that there are no collisions; rather, one can prove that the probability of encountering a collision is small in the random oracle model.

The random oracle model posits a finite domain and a finite codomain; otherwise the space of functions would be infinite and there could not be a uniform distribution on them.  If $f\colon A \to S$ is a uniform random function into a set $S$ of $n$ elements (e.g., $S$ is the set of $t$-bit strings, so that $n = 2^t$), then $f(x)$ is independent for each distinct $x$, and $\Pr[f(x) = h] = 1/n$ for each $x$ and $h$.

When we combine these two properties—$x \ne x'$ implies $f(x)$ and $f(x')$ are independent, and $\Pr[f(x) = h] = 1/n$—we can conclude from a standard birthday argument that any algorithm making $q$ queries to a random oracle has probability at most $q^2/n$ encountering a collision.  Following Ramanujan, Knuth, etc., the expected number of queries before a collision is $$1 + \sum_{k=0}^{n - 1} \prod_{i=1}^k \biggl(1 - \frac i n \biggr) = 1 + \sum_{k=1}^n \frac{n!}{(n - k)! \, n^k} \approx \sqrt{n \pi/2}.$$   Consequently, the expected query cost of any algorithm to break a cryptosystem like RSASSA-PSS signature by finding a collision in a $t$-bit random oracle is about $2^{t/2}$—which for typical values of $t$ like 256 is far beyond the capacity of humanity to carry out.

Of course, it is possible that we will learn something about SHA-256 that enables finding collisions more cheaply than generic collision searches, like we did with MD5 and SHA-1.  But this is how the random oracle model works.


In general the answer is no.

First, you need to make sure that your DH key agreement is authenticated. Otherwise you have no guarantee that you are talking to A at all.

Second, the symmetric cipher you use needs to provide authenticity so you should use some AEAD scheme. Otherwise somebody could just change the symmetrically encrypted messages.


It seems you're worried about two distinct attacks: replay attack (attacker reads a packet and re-sends it later), and a "delay attack" (attacker intercepts a packet, blocks it, and sends it later).

The replay attack can be avoided with counters or timestamps; as you mentioned, timestamps can be easier. The hard part is keeping clocks synchronized.

The delay attack can be detected with a timestamp (you need to authenticate the timestamp, e.g. in CCM mode you can include it in the additional data field).

Of course, you need to think about your application to see if you really need to protect against these attacks.


However if you added a counter to ECB mode and XORed each block of plaintext with the counter, you could avoid that problem.

This is trivially insecure. Counter-Example: Consider the nonce $0^n$ and the plaintext $0^{2n-1}\|1$. This mode will encrypt the first block to be $E(0^n)$ and the second block to be $E((0^{n-1}\|1)\oplus(0^{n-1}\|1))=E(0^n)$ and so the two blocks will match revealing that they were all zero and all-zero appended with 1. This easily breaks IND$-CPA and RoR-CPA security (the latter being equivalent to more standard CPA security).

  Why is this kind of mode not a thing?

This sort of mode is a thing actually. Just not in the naive formulation as described in the question. Namely if you have a almost-XOR-universal hash function $H_K$ keyed with some key $K$ and a block cipher $E$, then $H_K(T)\oplus E(M\oplus H_K(T))$ is a secure tweakable block cipher1. Now you can put a counter in the tweak $T$ and change it for each block so swap attacks no longer work as do the pattern attacks you know from ECB. In fact tweakable block cipher (modes) are so useful, they see widespread use as XTS (which is based upon LRW which is the above construction and used by essentially all disk encryption software in a variant of this mode) and are the basis for the famously fast OCB modes.

1: Technically this constructs a strong tweakable pseudo-random permutation. For a non-strong TPRP it actually suffices to compute $E(M\oplus H_K(T))$ and the simplest $H_K(T)$ is actually $K\cdot T$ over $F_{2^{128}}$ which when used with a counting $T$ is very close to the question's construction it's just the additional secret value that makes the difference.


AES Key Generation based on database guid

It isn't secure at all unless the GUIDs are completely inaccessible to everything except the encryption code. I doubt that is the case in a real application; I assume every DB query and API call passes those GUIDs around. Any anyone who can access the database can easily hash the GUIDs as well and decrypt any of the data. Your scheme as described is basically pointless obfuscation, not strong encryption.

One alternative would be to use the per-customer GUID as a salt for the input to HKDF, and then use a global secret key for the whole app as the key input to HKDF. This will give you a per-customer secret key while not requiring the GUIDs to be secret.

Protecting this "master" app key will be challenging, but protecting it in the same way you protect your TLS certificate private keys makes sense as compromising either would break all security.


Implementing symmetric encryption algorithms with whole words

Your best bet is, I think, to do it the other way round.

encrypt securely using a proven algorithm.
make the encrypted text human readable.

For example: AES-256 encode "Squeamish Ossifrage" using some key. Get, say, 512 bits of absolute gibberish. That is 64 bytes of 8 bits each; each byte can have one of 256 values.

Get a dictionary of 256 words (possibly, short words?). Read the 64 bytes, and for each value transform it into the appropriate word, giving you a "sentence" of 64 words:

Cat Hue Way Ten One Bat Bob Nod Ben Elk Joe Sex Van Eke ...

To decode, read in each word, and look for it in the dictionary. It is the 42nd word ==> read it as byte with a value of 42. Put all the bytes one after the other and get back the encrypted text, AES-256 decode it and Bob's your uncle.

This way, approximately 100 bytes of text become 60 bytes of encrypted binary code and those become 240 bytes of rehumanized code (each word is 3 letters plus one space). Or 180 bytes if you camelcase it: BobTenHueNitPinZoo... . You've got an overall expansion of about 1:2 or 1:3, which is quite reasonable.

And at the core you've got AES-256. Nobody wants to mess with AES :-)

Word becomes word

You want 'Cat' to always be encrypted as 'Dog'. This presents two problems. In the first place you either need to specify all the possible input words, or accept that some words will become gibberish; possibly pronounceable gibberish (there are algorithms for that) but still gibberish.

For example you can use a dictionary, consisting in a simple scrambling algorithm. When you find word #1138 in the cleartext, encrypt 1138 - this can be done with bit swapping if the dictionary has a size that is an integer power of two, for example 65536 words - so that it becomes another number within the same dictionary, say 31794. Word 1138 ("Horse") becomes word 31794 ("Staple").

What if a word is not in the dictionary? Then you need to encrypt it as a different word that is surely not in the dictionary (or you wouldn't be able to decrypt it). So Cat becomes Dog, Horse becomes Staple, Battery becomes Correct... and rumplestiltskin becomes xyzbatelkjoesexvanekewayhuejimsixnoddandinsupfoxfenjoeputits - where the xyz prefix warns the decoder that what follows is an encrypted sequence.

Or if you can store the new word in the dictionary, then you can simply use its MD5 to index it in 32 bits, or 4 bytes, or 4 three-letter words; giving you xykjimsuptitbat. The xyk prefix now tells the decoder that what follows is a 32-bit MD5 hash. Sender and receiver must agree on the dictionaries and now they also need to keep them synced.

Your encrypted sentence would become something like

Fence, xykjimsuptitbat!
Normal bog nuclear cascade iron irksome
Welcome japanese brillig sympathetic
Anathematize copper bleat irksome kill airplane
Severn'emporium zip cascade enormous

and here's the second (and possibly third) problem: on long texts, some words will repeat and lend themselves to analysis. Here, irksome and cascade are present twice each. Which makes one suspect that they (or at least one of them) might be a common English word such as "it", "the", "of", or something like that. Just as database applications need to be wary of little Bobby Tables, this kind of encryption schemes need to fear young Etaoin.

Also, you know which words are not common (by their prefix), so that you can tell between a normal sentence and 'Twas brillig, and the slithy toves... at a glance.

Notice the punctuation is kept, therefore it is quite easy to surmise that emporium is either 'll, 'm, 's, 't or 've; not too many English words contain a quote sign (a dozen? Twenty? Still too few).

To encrypt anything except very short texts, and seldom at that, means that an attacker will (relatively) quickly discover that xykjimsuptitbat actually means supercalifragilisticexpialidocious. In other words, this is not encryption -- it is "mere" obfuscation.

So... why do you have such a "dangerous" requirement?

I'll go out on a limb and guess that you need this to be able to run searches on the encrypted texts. There are techniques that allow you to do this securely, but they all exploit some features of the search being performed; in other words, there is no one-size-fits-all solution that is also proved and secure (i.e. demonstrably at least as secure as some proven, or at least widely adopted, solution). But if you supply some more information we might be able to help.

Or, of course, you may need it for some other reason altogether - but without knowing the why, one is hard put to come out with a how.

Some search schemes

There are several possible "searches". First of all let us consider that all searches by necessity disclose some information, and if you allow powerful enough searches, this is exactly equivalent to having the text unencrypted (you basically run a (sort of) Hangman game with the ciphertext - what is called a oracle attack).

Now a "search" could be the operation of querying "What records contain a particular keyword among a given set?", or "What records contain this arbitrary keyword?", or "What records contain this arbitrary user supplied text?", or even "What records match this regex?". There has been quite some work on the matter; try googling for 'PEKS'.

The easiest (and most secure) case is that where you have a fixed set of keywords. So in the records

 1: Shall I compare thee to a summer's day?
 2: Thou art more lovely and more temperate.

you can search by thee, day, art or thou, but not by summer.

You can implement this by simply appending to the encrypted text a sequence with the keywords - which could as well be in cleartext:

 1: blindalasbirigudacomefosseantani|Thee|Day
 2: tarapiatapiocalasupercazzolaprematurata|Thou|Art

After a search for Thou we know that it is contained in record 2, and nothing else. And as you see, the more keywords we store, the less security we have. Store all keywords, and you might as well not encrypt at all.

The above scheme can be made more space efficient by noticing that the encrypted text is actually never used, so you can just store the keywords.

Otherwise, we're just obfuscating; and therefore we might just as well go for performance.

For example you might XOR all records with a so-called "worm" (we're talking Vigenère cipher here) of, say, 16 bytes, and expand all letters to their hexadecimal equivalents. The resulting text is vulnerable to several possible attacks, but could still be thought of as "encrypted". To search, you XOR the search string with the 16 possible rotations of the worm - SAYHELLOWORLDNOW, AYHELLOWORLDNOWS, YHELLOWORLDNOWSA..., hex-encode it, and use the result as a normal text search. It will be anywhere from 1.x to 16 times slower depending on storage retrieval performance, but it will work.

The most promising possibilities exist wherever the actual search is not under control of the Searcher - he may submit texts to the search engine, but can not act on behalf of it, and for instance, is limited in the submission and retrieval speed (in other words, there is no real feasibility of a large scale dictionary/oracle attack). For instance, you could have a MySQL engine with a search function implemented as a closed source, loadable UDF module.


Compare RFC 5246 SessionID re-use versus RFC 5077 Session Resumption?

UPDATE: the below was valid through TLS 1.2. TLS1.3 in 2018 changes this radically; both the old resumption and old optional ticket mechanisms are gone. Instead there is an option for both ends to store (like old resumption) a secret plus some attributes, but instead of the prior session's master secret this stored secret is now a 'pre-shared key' (PSK) one-way derived from the prior session, so that a compromise of the stored PSK does not compromise the prior session. The server uses the 'New Ticket' message type defined for 5077, but now it contains only an identifier not an actual ticket. The new session can use this PSK either directly as the 'input' secret, or to authenticate a new keyexchange using DHE or ECDHE, in the same way it can (and 1.2 and lower already could) for a manually configured PSK -- except that manual PSK always was and I expect still will be extremely rare. In addition renegotiation is now gone -- although specific operations to do client-auth and to renew the working (symmetric) keys are added -- so session and connection now are basically the same.

Yes, you have the basic idea. Session-id info is stored (cached) at both ends; ticket is stored only at client, encrypted by server. Both re-use the "key exchange" which in SSL/TLS is actually key exchange combined with authentication; although authentication can be both directions (server and client) and thus an "exchange" of certs, it is usually server-only.
To be clear on the details, you need to distinguish session and connection. A SSL/TLS session is basically the results of a full handshake: the negotiated version, ciphersuite, and (most importantly) master secret, and perhaps some other bits. This plus nonces is the data needed to correctly do encryption and HMAC, or in TLSv1.2 optionally the "authenticated encryption" modes GCM or CCM instead. A connection is coterminous with a TCP connection, and starts with an initial handshake to either create and use a new session, or resume an existing session. Resumption can be used on connections at different times within some window, or multiple connections at the same time -- most if not all browsers will open maybe 4 to 10 parallel connections to download the 10s or 100s of resources used on most(?) webpages now. It is also possible but rarer to have multiple sessions on one connection using renegotiation, usually to authenticate differently or to rekey a long-lived connection. (Well, possible unless the server disables renegotiation as a clumsy defense against the MitM-prefix attack for which the proper fix is rfc 5746.)
Session-id has been in the base protocols since SSLv3 in 1996; ticket is an optional extension since 2006. Although session-id is in the protocol you don't have to fully implement it -- a server can always return an empty session-id, and a client can always "forget" any session-id it receives. Ticket is mostly useful for servers with large numbers of clients -- like the many millions for google, yahoo, twitter, facebook -- which would need to save huge numbers of sessions and distribute/synchronize them across numerous machines in a server "farm" (solvable problems, but if you don't need to it's easier).
So to your specifics:

session-id is good as long as both endpoints choose to save it and have room. Usually this is minutes to maybe an hour at most, but it can be more if both endpoints support that. On implementations I've looked at, it's configurable per application. It fails gracefully -- if client discards the session for a server and sends ClientHello with empty, server just creates a new session and discards the old one if still saved; if client has (and requests) a session server has discarded, server forces a new one and client discards its old one.

When I've looked I've seen ticket provided (if client offers support) only on a few high-volume sites (and my OpenSSL testbench) but I don't claim to have made anything like a thorough survey and I haven't seen any published. As 5077 describes, if you do use ticket you effectively ignore session-id for that session. It could certainly make sense for server to allow ticket to be valid longer than it would have kept session-id in its (possibly limited and crowded) cache, but I don't have data.

Initial handshake is always unencrypted up to ChangeCipherSpec and Finished, except for specific elements. In particular for RSA keyexchange, client public-key encrypts the premaster secret to server. (For DH* and ECDH*, public-keys don't need to be encrypted and aren't but still produce a secret agreement.) And ticket if used is encrypted by server to itself. If you do use renegotiation, that entire handshake is (super)encrypted, even though it usually doesn't need to be, giving a (clumsy) way to get that functionality.


Implementing AES-CBC (Matasano Crypto Challenge 10)

I suppose you have removed the base64 decoding, so you are working on the raw data.

Then indeed the first block is decrypted as if we were in ECB-mode, because after decrypting the first block, we xor with the IV, which is all 0 and indeed has no effect.

However, the IV for the next block will be the original previous ciphertext block. So after decrypting that block we have to xor with this new IV, so there we cannot suffice with just ECB mode. See also this picture from the comments:


What is the algorithm behind PasswordDeriveBytes?

The password P in the Microsoft implementation is first encoded using UTF-8. The iteration count c defaults to the value 100, and the hash algorithm Hash to SHA-1.

The output is identical to PBKDF1 up to the maximum output size of PBKDF1, which is the output size of the hash. After that the first-to-last hash is prefixed with a counter (as a string containing a decimal number encoded using ASCII) and hashed again to produce the output. If GetBytes is called multiple times it will just return the next output bytes from the stream.

Note that this description does not describe the broken implementation that Microsoft shipped with earlier Windows operating systems. Those contained a bug which could result in repetition in the output of the GetBytes method if it was called two or more times.

The following is a more formal description of the algorithm. It extends the definition of PBKDF1 in RFC 2898, section 5.1.

PBKDF1_MS (P, S, c, dkLen)

   Options:        Hash       underlying hash function

   Input:          P          password, an octet string
                   S          salt, an eight-octet string
                   c          iteration count, a positive integer
                   dkLen      intended length in octets of derived key,
                              a positive integer, bounded to 100 times
                              the output size of Hash

   Output:         DK         derived key, a dkLen-octet string

   Steps:

      1. If dkLen > 100 * Hash output
         "derived key too long" and stop.

      2. Apply the underlying hash function Hash for c iterations to the
         concatenation of the password P and the salt S,
         apply the Microsoft extension by hashing the concatenation of
         an encoded counter and the output of the hash produced for
         iteration c - 1, then extract the first dkLen octets to produce
         a derived key DK:

                   T_1 = Hash (P || S) ,
                   T_2 = Hash (T_1) ,
                   ...
                   T_c = Hash (T_{c-1}) ,
                   R_1 = T_c ,
                   R_2 = Hash (Ctr(1) || T_{c-1}) ,
                   ...
                   R_n = Hash (Ctr(n-1) || T_{c-1}) ,
                   R = R_1 || R_2 || ... || R_n
                   DK = R<0..dkLen-1>

      3. Output the derived key DK.

    The Ctr function converts the given number to a decimal
    representation in ASCII.

Original Mono implementation in C# here. Java port here.

You are strongly encouraged to use the RFC2898DeriveBytes instead, which implements PBKDF2.

If output is required of PBKDF2 that extends beyond the output size of the underlying hash then it is recommended to use a Key Based Key Derivation Function such as HKDF. If you don't have an implementation of that, then simply hash the output and a statically sized identifier to create a derived key SHA-256(master | identifier) and take as many bytes from the left as needed.


If you have a solver for P1, then it can also solve P2, so the problems are comparable: P2 is easier.
P1 is assumed hard, and is used as the basis of, e.g. https://eprint.iacr.org/2020/1012.
P1 is known to be generically equivalent to P3 (see https://hal.archives-ouvertes.fr/hal-02373179 and https://eprint.iacr.org/2020/1012), however P2 is probably not equivalent to P4: the reduction does not work for these more constrained problems, and P4 is known to be easy, whereas P2 is likely not.


How many polynomials are used in Secure Multiparty Computation?

For "standard" Shamir secret sharing you use a new random polynomial for each secret you want to share (including when you use Shamir secret sharing in SMC). I.e., you would use different polynomials for each secret. Note, that Shamir secret sharing does not directly work on "words" but rather elements of some field. You would have to translate your data into field elements and then share those elements individually.

There is, however, a variant of Shamir secret sharing called "packed secret sharing". In this variant you are able to share a "block" of $l$ secrets using a single polynomial. This means you would be using a factor $l$ less polynomials. There are SMC schemes that rely on this kind of sharing as well, although they are somewhat more complicated than those using standard Shamir secret sharing (an example of such a scheme can be found here: iacr eprint link).

As to how search would work, this is really not something that is standardized. The SMC allows you to compute any arithmetic circuit over the shared data. You can essentially express any function, including keyword search, as an arithmetic circuit. However, exactly how to do this is not trivial to figure out.

In fact, for this particular task you may be better off picking a different SMC technique, based on Boolean circuits instead of arithmetic circuits. This is because keyword search probably involves a lot of comparisons. Something that Boolean circuits are much more well suited for.


openSSL created CSR signature size of 73 bytes but should't it be 70 bytes

The "extra" octet is needed because ASN.1 uses two's complement notation for integers, per section 8.3.3 of X.690:

The contents octets shall be a two's complement binary number equal to
the integer value

In two's complement, the highest bit indicates a negative number. Since none of our numbers are actually negative, the correct notation needs to have leading zeros.
We can see this in action on the following signature:
$ openssl asn1parse -i -in foo.csr -strparse 126 -out raw
    0:d=0  hl=2 l=  69 cons: SEQUENCE
    2:d=1  hl=2 l=  32 prim:  INTEGER           :1937197C689C3E511CCB830E5F3677D3FA18F045EBA969739B622B95FEB619C1
   36:d=1  hl=2 l=  33 prim:  INTEGER           :BA1B75CEE9714860639A20B50125C20224CBBEBE01F4CCBFA46731706F55D171

You'll notice that my first integer has length 32 but the second has length 33.
Dumping the raw contents, we get:
$ hd raw
00000000  30 45 02 20 19 37 19 7c  68 9c 3e 51 1c cb 83 0e  |0E. .7.|h.>Q....|
00000010  5f 36 77 d3 fa 18 f0 45  eb a9 69 73 9b 62 2b 95  |_6w....E..is.b+.|
00000020  fe b6 19 c1 02 21 00 ba  1b 75 ce e9 71 48 60 63  |.....!...u..qH`c|
00000030  9a 20 b5 01 25 c2 02 24  cb be be 01 f4 cc bf a4  |. ..%..$........|
00000040  67 31 70 6f 55 d1 71                              |g1poU.q|

Let's break it down into the various components:

30 45: SEQUENCE of length 69
02 20: INTEGER of length 32
19 37 19 7c ... 19 c1: the INTEGER contents (32 bytes)
02 21: INTEGER of length 33
00 ba 1b 75 ... d1 71: the INTEGER contents (33 bytes)

This matches exactly what asn1parse tells us. Notice the difference between the first integer (encoded to a length of 32 bytes) and the second (encoded to a length of 33 bytes).
The first one begins with 19 which is 00011001 in binary. Because it does not have a high bit set, this is indeed a positive number.
But the second one begins with BA which is 10111010 in binary. The high bit is set which would be negative if we decoded it as is. Since it isn't negative, the correct two's complement notation has leading zeros.
In your case, both numbers have the high bit set, so they both get 00 prepended.
You end up with a total size of: $2 + 2 + 32+1 + 2 + 32+1 = 72$.
Oops, we're still one short of 73. This is part of the BITSTRING encoding which is defined in the spec, section 8.6.2.2 as:

The initial octet shall encode, as an unsigned binary integer with bit
1 as the least significant bit, the number of unused bits in the final
subsequent octet. The number shall be in the range zero to seven.

This is because a BITSTRING can represent a number of bits that is not a multiple of 8. In our case, we're making use of all bits, so the initial octet for the bitstring is 00.
We now have the right length: $72 + 1 = 73$.


Let $N(\alpha,\beta)$ be the number of times the equation
$$
\alpha\cdot x \oplus \beta \cdot y=0 \tag{0} \label{0}
$$
holds. Then the LAT matrix entry is
$$
L(\alpha\cdot x \oplus \beta \cdot y )=
N(\alpha\cdot x \oplus \beta \cdot y)-2^{n-1}
$$
and since the second term is even (can prove $n=1$ case directly) we need to show that $N(\alpha\cdot x \oplus \beta \cdot y)$ is even.
The basic idea is that the set of vectors over $\mathbb{F}_2^n$ of the form
$$a\cdot x=c \tag{1} \label{1} $$ has even cardinality
for any constant $c\in \mathbb{F}_2.$ Observe that this applied to $\alpha\cdot x$ and $\beta\cdot y$ means that $N(\alpha,\beta)$ is also even if we can prove $\eqref{1}$.
To prove $\eqref{1}$ assume $a\neq 0$ in $\mathbb{F}_2^n,$ since if $a=0,$ the relation holds for all $x\in \mathbb{F}_2^n,$ i.e., for $2^n$ vectors.
If $a\neq 0,$ let $w$ be the Hamming weight of $a$ and let $s_a$ be the support of $a,$ i.e., $s_a=\{i: 1\leq i\leq n, a_i=1\}$. Then, the inner product $a\cdot x$ is invariant when the components $a_i$ in the complement of the support take on all possible $2^n-2^w$ values, since they don't feature in the inner product. Clearly $2^n-2^w$ is even.
Finally note that equation $\eqref{0}$ holds if and only if $\alpha\cdot x$ and $\beta\cdot y$ are both equal to the same constant $c$. So it holds an even number of times.
Remark: This argument also works for an arbitrary $n\times m$ S-box $S:\mathbb{F}_2^n\rightarrow \mathbb{F}_2^m$ for any $m\geq 1$.


How does compression before encryption leak info about the input?

The problem is not with compression and encryption, it is with the protocol that is being used, and the type of data being compressed (or not) prior to encryption.

The most damning leaks are on protocols that were either designed to be compressed without encryption, or encrypted without compression.

The best example I have is VOIP systems that use a variable bitrate compression prior to encryption. Since the gaps between words and even syllables are highly compressed, and the words and syllables themselves are compressed at different rates depending on their content, traffic pattern analysis can be used to accurately detect spoken words and phrases. Public research only began within the last decade, but NSA designed encrypted voice protocols used constant bitrate compression and i/o clocking, meaning the technique was either known or they expected it to be exploited.

An excellent presentation of the subject here, as well as a more detailed initial report from 2008.

When a protocol is properly designed with compression and encryption in mind, it is much more difficult to gain information. For example, an SMS message where the entire message space is encrypted using AES-GCM, and the text is first compressed, allowing potentially more than 160 characters to be included in a single message. Some of the SMS must be used for nonce/auth tag, so the more message it can fit the better. This is of course an additional encryption I am talking about and not part of the SMS protocol. Multiple sequential SMS messages reveal information about the message size (being larger than the limit), and compression can prevent that if done correctly.

Padding any compressed plaintext to a multiple of some given number (say 128 bytes) prior to encryption makes certain attacks less effective, especially if the majority of plaintexts are small (like text messages). The methods used to pad the data are also important, as there are attacks that exploit padding used in various protocols.


Why can a symmetric encryption algorithm be considered a pseudo-random number generation algorithm?

Here are two standard (and equivalent) definitions of confidentiality in symmetric encryption. If Alice sends Bob a message and Eve manages to see it in transit, Eve cannot (without an unreasonable amount of computation):

Learn any fact about the plaintext other than possibly its length (semantic security);
Tell the ciphertext apart from random data of the same length (ciphertext indistinguishability).

The latter criterion indirectly answers to your question. One way to implement a pseudorandom number generator is just to encrypt arbitrary inputs—say, encrypt the all zeroes string and use the ciphertexts as the pseudorandom output.

This also works in the opposite direction—if you have a secure pseudorandom generator, you can build a secure cipher out of it (called a stream cipher) by XORing its output with the messages. So in that sense, encrypting messages confidentially and generating secure pseudorandom numbers are equivalent problems.


Swapping a single bit inside a 40 bytes inputs fed to keccak256. Is it safe to assume no change in the first 20 bytes can result in the same hash?

There are no known attacks on SHA3 series that are faster than the generic attacks.

Your problem is the 2nd pre-image attack: given a message $m_1$ finding another message $m_2$ such that $m_1 \neq m_2$ and $Hash(m_1)=Hash(m_2)$.

SHA3-256 has $2^{256}$ 2nd preimage resistance.

Now, you only allow the attacker first 20-byte which is 160-bit of your data. The attacker must try to find the $m'$ if exist. He cannot brute-force the 160-bit space to execute the generic attack. That is not reachable, even 128-bit is not.

The bitcoin miners' latest SHA-256 hash rate peak was $2^{66}$ hashes per second and $2^{83}$ per day from 108464285TH/s on 29/09/2019.

Another question is: does this 2nd pre-image exist? With a negligible probability, no!

  Even if the change is about a single byte,

We want the avalanche effect from the hash functions that is; a single bit flip should randomly flip the %50 percentage of output bits.

In general, if you want to find an attack into a good hash function you need some degree of freedom. What you are looking for is the reverse.


Attacks on code misusing RSA_public_decrypt

In OpenSSL 1.0.2 (and former) at least, based on its documentation and code of an implementation, the big picture is that RSA_public_decrypt with RSA_PKCS1_PADDING applies the RSA public-key transformation $S\mapsto S^e\bmod N$ where $S$ is the alleged signature, then checks that the outcome (considered as a big-endian bytestring of the same size as $N$) is of the following form
$$\mathtt{00}\mathbin\|\mathtt{01}\mathbin\|\underbrace{\mathtt{FF}\ldots\mathtt{FF}}_{\ge8\text{ bytes}}\mathbin\|\mathtt{00}\mathbin\|D$$
and in the affirmative returns the bytestring $D$, and its length.

However, implementation is configuration dependent. Sticking to openssl-1.0.2t, RSA_public_decrypt of rsa_crpt.c can vector to a number of things, including RSA_eay_public_decrypt of rsa_eay.c with padding checks in RSA_padding_check_PKCS1_type_1 of rsa_pk1.c, but also to various other engines for HSM, Smart Card, OS-dependent service (like CryptoAPI on Windows). Thus exactly what it does is quite configuration-dependent. In particular:

Implementations should check that $S<N$, and the aforementioned version of RSA_eay_public_decrypt does, but some implementations do not. The main cryptographic significance is that, if this check is not performed, it is possible to transform a rightful signature $S$ into into another accepted one $S'=S+jN$ (depending on if there is a length check for $S$, that could be for all or a fraction of rightful $S$). In the context of the question where the easiest forgeries $S$ are much smaller than $N$, $S+N$ would typically have the right size, and would look less regular (thus suspicious) to the naked eye.
Implementations often accept that the leading $\mathtt{00}$ is absent, and the aforementioned RSA_padding_check_PKCS1_type_1 does. There might be some even more lenient checks in other implementations. Either would give more freedom in the following attack.

  code (..) is misusing RSA_public_decrypt to "authenticate" a variable-length response without using any hash. The code assumes that a successful decryption means that the given data buffer was generated by the server and processes it without any additional checks.
  (..) 2048-bit key with $e=3$.

With these parameters, it's indeed possible to forge the signature for a number of $D$. In particular, it is enough that $\mathtt{00}\mathbin\|\mathtt{01}\mathbin\|\mathtt{FF}\ldots\mathtt{FF}\mathbin\|\mathtt{00}\mathbin\|D$ is a $e^\text{th}$ power. If the key is $k$-bit, and $\tilde k=8\lceil k/8\rceil$, it is enough that $D$ is the low-order $\tilde k/8-11$ bytes of $S^e$ with $S$ the signature in the integer range
$$\Biggl[\;\biggl\lceil\sqrt[e]{2^{\tilde k-15}-2^{\tilde k-80}}\;\biggr\rceil\;,\ \biggl\lfloor\sqrt[e]{2^{\tilde k-15}-2^{\tilde k-80}+2^{\tilde k-88}-1}\biggr\rfloor\;\Biggr]$$

For small enough $e$, this interval in non-empty, and it is possible to obtain $D$ with some of its left bits at a chosen value, by putting the others at zero and computing $S$ as $\biggl\lceil\sqrt[e]{2^{\tilde k-15}-2^{\tilde k-80}+D}\;\biggr\rceil$. More (smaller, possibly empty) intervals are possible for shorter $D$.

Here $k=\tilde k=2048$, $e=3$, that interval contains over $>2^{603}$ signatures $S$, and there are as many 245-byte $D$. One such signature $S$ is

00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000032cbfd4a7adc7905583fd1456434c26cdf83a920b31e26cc57a313376f4148ebf9544218c1bdc0793bf961895224ef87d397320d586eb7c6ce051ad3fe93b96e22c7f1ec329b88780a17483947fbb7bf3707b0f445

with $S^3$ equal to

0001ffffffffffffffff0077652063616e20666f7267652061207369676e6174757265206f7574206f66206e6f776865726500000000000000000000000000000000000000000000000000000000000000000000000018e546e7c17e2565ec99cfa7249fd76b89b819c73a68a5e19d0302472cdd57230fb23fba23f25e9e76d6345156620f5ecabd14f65fd2fd230a38a769eb521b6e61ac9d9a995e857d03525128e8c1689814fec44d88abded8e3ee67e87b227536f1c42b9a8a1c08d918de54653f8cb1cd54699edfd00763fb0644e304c9644b87b75731bd6fabe7920bb47ba3151f614256814655db5ced95b7c480c5daf51d96145dc26d831fea327f3d

thus this $S$ is acceptable (regardless of the value of the public key) by most RSA_public_decrypt, and produces a 245-byte $D$ of

77652063616e20666f7267652061207369676e6174757265206f7574206f66206e6f776865726500000000000000000000000000000000000000000000000000000000000000000000000018e546e7c17e2565ec99cfa7249fd76b89b819c73a68a5e19d0302472cdd57230fb23fba23f25e9e76d6345156620f5ecabd14f65fd2fd230a38a769eb521b6e61ac9d9a995e857d03525128e8c1689814fec44d88abded8e3ee67e87b227536f1c42b9a8a1c08d918de54653f8cb1cd54699edfd00763fb0644e304c9644b87b75731bd6fabe7920bb47ba3151f614256814655db5ced95b7c480c5daf51d96145dc26d831fea327f3d

which, when interpreted as a C string in ASCII or UTF-8, is the string

we can forge a signature out of nowhere

The LLL algorithm may allow further forgeries, I'm not a specialist of that.


Lightweight block ciphers that support decryption with minimal overhead?

Why is there a need for lightweight block cipher to support decryption routine?

You might want to use a mode that is not based on CTR mode, which will require the availability of the decryption procedure.

  What all other lightweight block ciphers support decryption with minimal overhead?

Any designs that are Feistel networks and/or use components that are involutions will offer minimal overhead for the decryption procedure.

The following designs mention using components that are involutions, according to wikipedia:

Anubis
KHAZAD
Cellular Message Encryption Algorithm
MULTI2
NOEKEON

This list is probably not exhaustive.


Coincidentally I had the Twofish and Camellia design papers open on my computer when you asked this question.

S-boxes in the ciphers

Both are Feistel ciphers, and the way the s-boxes are used is quite different when compared to AES. The s-boxes are used almost identically in Twofish and Camellia, but key mixing and post s-box diffusion are quite different. I assume you know the general structure of the ciphers so I will not go over that here.

Camellia uses each s-box twice per round, and runs the entire 64-bit input through those s-boxes in parallel, then mixes them together. Key material is added to the input prior to the s-boxes. Twofish uses each s-box twice per round in parallel, then mixes each 32-bit half, then mixes those halves together, followed by addition of key material.

AES of course uses the same s-box on all 16 input bytes prior to mixing, followed by diffusion and key mixing.

S-box design

The way the s-boxes in these ciphers are generated is also different. AES uses its single s-box generated from finite field inversion followed by affine transformation and addition of a constant.

Camellia uses 4 AES-like s-boxes (finite field inversion), S2 S3 and S4 are generated from S1, which has a base design optimized for minimum hardware resources. A time-memory tradeoff can be made in implementations where only the table of S1 is in memory, and the permutation to the other s-boxes is done at runtime, which is composed of fixed rotations. Minimal hardware resources and a Feistel design (same decrypt hardware, less data processed per round) can make Camellia more efficient than AES in dedicated hardware. The key schedule is more complex than AES, and it reuses the round function to generate key material.

Twofish s-boxes are made from 2 different permutations and key material. The permutations themselves are made from 4 fixed 4-bit s-boxes each. A time-memory -storage tradeoff can be made in implementations where only the tables of 4-bit s-boxes are stored in code, and the permutations are generated and stored in memory during key scheduling, where the s-boxes are generated. Twofish has a much more complex and expensive key schedule by design.

S-boxes and security

When it comes to the question of security, Camellia is a more modern cipher than AES, with a complex key schedule more resistant to related key attacks, but a more simple round structure which requires more rounds to meet its required security bound. Twofish has a very complex key schedule along with a complex round structure which requires 32-bit addition, limiting performance on platforms with only simple logical operations. Twofish was considered to be more secure than AES but lost out due to its slow key schedule and implementation issues due to 32-bit addition on non 32-bit platforms.

Because Twofish and Camellia are a completely different structure than AES, the way the s-boxes contribute to security is different. Round counts in all ciphers are chosen to keep known security properties within the margin defined by the key size. At this time, out of the 3 only AES is known to have a security level under any condition lower than the key size, and only in a related key model, and it is not a practical attack.

It is certainly possible than the use of additional s-boxes could have eliminated such an attack, but at the expense of an additional s-box, possibly making storage requirements on constrained platforms such as 8-bit microprocessors and smartcards substantially larger, which is quite small for AES when compared to other ciphers of similar security and performance on a variety of platforms.

There are multiple ways additional s-boxes could have been added to AES. You could have 2 s-boxes, one for odd rounds and one for even rounds. A different s-box could be used in the key schedule. You could have multiple s-boxes in each round like Camellia and Twofish. You could have a combination of these using 4 s-boxes, like 1 and 3 on odd rounds, then 2 and 4 on even rounds. If the s-boxes have similar or identical properties to the original, the full cipher would have similar or identical security against some attacks, and most likely superior security against some others.

The other problem with adding more s-boxes is that security proofs and analysis gets more complicated, using a single highly nonlinear s-box allowed initial analysis on Rijndael to use very simple and easy to analyze descriptions, which gave confidence in the algorithm under intense scrutiny. This same simple description is also one reason why people are looking for alternatives. S-boxes based on finite field inversion are also under scrutiny due to CCZ-equivalence, which may be exploited to reduce the complexity of attacks.

With 15 years since AES was chosen to replace DES, much of block cipher design has been focused on smaller faster designs as opposed to more secure designs, and on designs immune to side channel attacks, which have been the bane of many AES implementations. S-box table lookups are a problem for cache timing consistency, they can reveal plaintext or key material. Multiple s-boxes can make it more difficult to mount such an attack, but s-box free designs can eliminate them. Since the AES s-box is already as nonlinear as you can get with an 8x8 s-box, adding more s-boxes will not improve overall linear properties, only a larger s-box will do that, or addition of more nonlinear steps to the round function.

Conclusion

This question is similar to "If I add more pistons to an engine, will the car go faster?" My 6cyl car is much faster than my old V8, but its also turbo charged, and direct injected and the V8 was not, so there is more to a car than just the piston count of the engine. There is also more to a car than just speed, just as there is more to a cipher than just security.

Adding more s-boxes to an AES derivative will probably increase security, but since AES is still considered secure for use, even for top secret US government use, that is not a good use of resources. An improved key schedule will improve resistance to many attacks at the expense of performance, with less hardware and software resources required when compared to an additional s-box, and way less when compared to multiple s-boxes, unless it was done in the way the Camellia s-boxes are created, which are permuted from a single s-box.

Using maybe 2 or 4 different types of s-boxes and increasing the round count by 1 or 2 rounds would most likely result in the the best balance of security, performance, and implementation resources based on adding s-boxes alone. By different types I mean those with a more complex algebraic description or those without CCZ-equivalence, like the Skipjack s-box for example.


You are correct that the function of using a distinct salt for each user is to thwart any batch advantage an adversary attacking one of many targets might have gotten out of precomputed tables.  If there are $2^n$ distinct salts and they're chosen uniformly at random for each user, it's only around $\sqrt{2^n} = 2^{n/2}$ users that a collision in the salts might happen so that the adversary might even get a chance to apply one precomputed table to many users.

Pick $n = 256$ bits and you won't ever have to worry about it.
Pick $n = 128$ bits and you probably won't ever have to worry about it even if everyone else uses the same hash function.
Pick $n = 64$ variable bits and an application-specific constant that nobody else uses and you're probably mostly OK because the precomputation of the table is expensive already, even if there are a handful of collisions in a few billion users.  But consider revisiting once you've hit a million users just to be safe.

No need for $n = 500$ bits or anything obscenely large like that.


Questions regarding parallel AES CTR with merkle trees

Since it's a bad habit to answer questions in comments, I'll take my comments, and put them as an answer.

First off, you appear to be looking at designing your own homebrew method to do parallelizable MACing; don't do it.  There are too many ways to get it wrong, and you don't know what to avoid.

However, since you asked specific questions, I'll try to answer them:

  From my understanding, it should be possible to encrypt, decrypt and verify the data completely in parallel, is that true?

Obviously, yes, for example, with GCM.  You said that GCM doesn't work for you; it still is a proof of concept that parallelization is possible.

  In addition to that, I've seen that a lot of hashing methods (like GCM) verify the length of the ciphertext. Is that necessary with a merkle tree?

Maybe; GCM includes the length so that you cannot come up with two different ciphertexts/AADs that map to the same GHASH polynomial; one way an attacker could do that (if you don't include the length) is just prepend a 0 block to the ciphertext; that doesn't change the polynomial evaluation at all, no matter what the internal $H$ is.

Does your Merkle tree construction require something similar?  Without knowing the details of your construction, it is literally impossible to say.

  Also, should I hash the plaintext or ciphertext? and how should I encrypt the hash value?

Again, without knowing the details of your scheme, I can't really say.

On the other hand, if you're interested in a parallelizable authenticated encryption mode which is not GCM, you might want to consider CWC; it was designed by people who know what they're doing.  It's similar to GCM internally (and actually predates it a bit), however it uses software-friendly operations internally (additions and multiplications modulo $2^{127}-1$), rather than the $GF(2^{128})$ multiplications in GCM.

That may work out better for you.


How to show that any 2-round key-exchange protocol satisfying a given definition can be converted into a public-key encryption scheme?

My reputation won't let me post this as a comment, but I believe you could simply use the key exchange as a one time pad.

Alice and Bob could use the key-exchange as normal. Alice initiates the key-exchange and sends the first round. Bob sends the second round. They now both have enough information to generate a shared key of length $k$ bits, which is CPA secure. Bob then sends a message of length $l \leq k$ XORed with the shared key (obviously only sending $l$ bits). Alice can decrypt this message, simply by XORing with the shared key.

Note that the entire key exchange needs to be repeated for each block of $k$ message bits. This repetition must be secure.


How can I make my cipher show the avalanche effect?

Don't bother with changing the actual cipher algorithm.  Read about Kerckhoffs's principle: you should only change things like the key and the IV, not the actual algorithm.

In order to test your avalanche, flip one bit in your key.  That should change about half the bits in your output.

For cipher design, Applied Cryptography has already been suggested.  As well as that you need to look at introducing Diffusion and Confusion into your algorithm.  Also it is well worth while studying existing algorithms to see how they go about things.  I started by designing my own simple Feistel cipher, that way a lot of the surrounding structure is already done for you.  It also simplifies the design, in that the F function does not have to be invertible.  That allows you a lot more flexibility in that area.

The warning about not using your own design for anything other than a learning exercise is a good one.


Does Coron and May's paper for deterministically reducing finding  to factoring  work with $\lambda(n)$?

As mentioned in the other answer, the probabilistic method always works, and I've described both of these methods before.
We'll deal exclusively with $p, q$ of approximately the same size here. Suppose $l = \gcd(p-1, q-1)$, the ratio between $\phi(n) = (p-1)(q-1)$ and $\lambda(n) = \mathrm{lcm}(p-1, q-1)$. As usual, let $n = pq$, $e$ be the public exponent, $d = e^{-1} \bmod \phi(n)$, and $d' = e^{-1} \bmod \lambda(n)$.
The original Coron-May reduction observes that $f(x) = n - x$ has a "small" root $p+q-1$ modulo $\phi(n)$, a "large" divisor of $ed - 1$. More specifically, as long as there's a $\beta \in [0, 1)$ such that $p+q-1 \le (ed - 1)^{\beta^2}$ and $\phi(n) \ge (ed - 1)^{\beta}$, the method works in polynomial time. Because $\phi(n) \approx n$, this effectively translates into the requirement $ed \le n^2$.
Without any changes to the method, replacing $\phi(n)$ by $\lambda(n)$ means that $f(x) = n - x$ has a small root $p+q-1$ modulo a large factor of $ed' - 1$. Because of the common factor $l$, $d'$ may be much smaller than $d$, and in particular the size is no longer neatly related to $n$, so as to achieve a bound like $ed' \le n^2$. However, the method still works under the more elaborate constraint that there be a $\beta$ such that $p+q \le (ed' - 1)^{\beta^2}$ and $\lambda(n) \ge (ed' - 1)^{\beta}$.
For typical $e = 65537$, we still have $\lambda(n) = (ed'-1)^{\beta}$ for a $\beta$ very close to $1$. As long as $2p < (ed' - 1)^{\beta^2}$, the reduction still works.
Here's a worked example using Sagemath, where $\phi(n) \approx 2^{130}\lambda(n)$.
sage: p = 30010719099306564150822479775631261956587370647517629976046542673406882291177
sage: q = 91932507744510266739810220416155764940049951037172916877150162469889273507869
sage: n = p * q
sage: l = gcd(p-1, q-1)
sage: l
1361129467683753853853498429727072846028
sage: e = 65537
sage: d = inverse_mod(e, lcm(p-1,q-1))
sage: P.<x> = Zmod(d*e-1)[]
sage: f = x - n
sage: beta = d.log(d*e).n()
sage: beta
0.959304860280816
sage: assert(p+q < (d*e-1)^(beta^2))
sage: f.small_roots(X=2^257, beta=beta, epsilon=0.05)
[121943226843816830890632700191787026896637321684690546853196705143296155799045]
sage: p+q-1
121943226843816830890632700191787026896637321684690546853196705143296155799045

With a larger $e$, it still works. Say, $e \approx 2^{180}$:
sage: e = next_prime(2^180)
sage: d = inverse_mod(e, lcm(p-1,q-1))
sage: P.<x> = Zmod(d*e-1)[]
sage: f = x - n
sage: beta = d.log(d*e).n()
sage: beta
0.677720040398063
sage: f.small_roots(X=2^257, beta=beta, epsilon=0.01)
[121943226843816830890632700191787026896637321684690546853196705143296155799045]

Here we are already pushing the limit, since $(ed' - 1)^{0.6777^2} \approx 2^{256.53}$. Going much higher with $e$ will fail. The original method with $\phi(n)$ would allow $e$ to go up to $\approx 2^{512}$ in this example.


How to generate the Keystream from IV+Key in RC4

The length of Key and length of IV bear no relationship with the length of the message.

RC4 is deprecated. The way it was supposed to be used is:

Generate a random IV, wide enough that it will remain unique (e.g. 32 bytes), and emit that as header of the ciphertext since the receiver will need it.
Concatenate Key (limited to 256 minus IV size in bytes) and IV
Initialize the cipher with that (there are 256 steps that cycle on the concatenated Key and IV).
Generate as much output a there is plaintext, and use it as keystream to XOR with plaintext, yielding ciphertext.

But various attacks exist. If for some reason one is locked with that cipher from the past (rather than e.g. ChaCha which is safer, faster, and less RAM-intensive), and nevertheless wants to be secure, it's advisable to at least discard some of the initial keystream (e.g. the first 1024 bytes) in an intermediary step before 4.

And of course if one is locked with a particular protocol, it must be done as in that protocol.

Note: if the key is derived from a passphrase memorized by a user, then it is highly advisable to use some form of stretching for the password-to-key conversion:

The best would be a modern and well parametrized password hash function such as Argon2 or Scrypt.
If not, we can use RC4 itself by using the amount of keystream skipped as the workfactor parameter (e.g. 222 bytes). Also, we need to limit the password length to be sure that there remains room for the IV.

Independently, the character set of the password must be well-defined (e.g. UTF-8).


Clarification on Key exchange approaches in TLS/SSL

are the DH public values exchanged unencrypted?

Yes, that are.  After all, they are "public values"; there's no weakness in exposing them in the clear.

Now, we do have to be careful that they aren't modified in transit (if they can be, then someone can perform a Man-in-the-Middle attack).  We do that by having the server sign its key share (using the private key of its certificate).


Problems with using AES Key as IV in CBC-Mode

CBC mode encrypts as follows:
$$
C_0 = E_K(IV\oplus P_0);\\
C_i = E_K(C_{i-1}\oplus P_i),
$$
where $P_i$ are plaintext blocks and $C_i$ are ciphertext blocks. Traditionally, IV must be random and is published alongside the ciphertext to enable decryption. If it is also published in your case, then this reveals the key and is trivially insecure.

If the $IV=K$ is not attached to the ciphertext, then you get a deterministic (in contrast to probabilistic) encryption  scheme. It has a number of insecure properties, such as

the ciphertext does not change if the same plaintext is encrypted multiple times.
if two plaintexts have the same prefix, then the ciphertexts will have the same property.

Maybe there are others, but these ones are sufficient to avoid using such scheme to protect confidentiality of any reasonable amount of data, except maybe for very short (16 bytes or less) plaintexts.