Why initialize SHA1 with specific buffer?

The initial values to a Merkle–Damgård type hash function are essentially the plaintext to a block cipher, with the input to the hash function becoming the key. The maximum length of the hash is determined by the amount of bits of initial value. Five 32-bit words gives SHA1 a state size and maximum output of 160 bits. In order for an MD type hash function to output a consistent value, the initial values must be constant.

The first 4 values are those used in MD4 and MD5. They are represented in big-endian format. If represented in little-endian, it can be seen it is a simple 4-bit counter starting at 0000, maxing out at 1111, then stepping back in reverse, in groups of 32 bits:

 0111 0110 0101 0100 0011 0010 0001 0000 = LE 0x76543210 = BE 0x67452301
 1111 1110 1101 1100 1011 1010 1001 1000 = LE 0xFEDCBA98 = BE 0xEFCDAB89
 1000 1001 1010 1011 1100 1101 1110 1111 = LE 0x89ABCDEF = BE 0x98BADCFE
 0000 0001 0010 0011 0100 0101 0110 0111 = LE 0x01234567 = BE 0x10325476

The final big-endian value is an incrementing counter from 1100 for odd 4-bit groups, and a decrementing counter from 0011 for even groups.

These are called Nothing Up My Sleeve numbers, and are chosen as a way of proving the constants are not specially chosen, such as to provide a backdoor to the algorithm. As per figlesquidge's comment as to why these are not simply 0 bits, the average hamming weight of the entire set of initial values is 0.5, half the bits are 1 and half are 0.

The round constants for SHA-1 were also chosen not to be "special", but are generated quite differently. They take the square root of a number in binary, then the first 32 bits, including those before the decimal place, become the round constant. This is the same method used to generate the two round constants for MD4.

0x5A827999 = $\sqrt2$
0x6ED9EBA1 = $\sqrt3$
0x8F1BBCDC = $\sqrt5$
0xCA62C1D6 = $\sqrt{10}$

The design criteria for the first 2 round constants was specified in the original MD4 paper as well as the RFC. The initial value choice was never defined nor explained, most likely because of the obviousness of the pattern. The choices of initial values and round constants were not explained in FIPS-180-1 and later revisions. It is interesting that they chose 10 to generate the final round constant rather than 7, as it is not prime.

One possible explanation for the choice of $\sqrt{10}$ instead of $\sqrt7$ might be that $\sqrt{10}$, along with the other three constants, are the only square roots given in the "Tables of Numerical Quantities", Appendix A Table 2 (ocatal representations), in Donald Knuth’s The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, Second Edition (1981), p. 660, which is referenced in the original RFC 1320 to MD4 (on p. 4) as the source for the constants. In the Third Edition (1997) of the book, these are found on page 727.

SHA-2 (256 and 512 bit digests) in comparison uses the fractional component (after the decimal place only) of the square root of sequential primes 2 to 19 for initial values, and the fractional component of the cube roots of sequential primes 2 to 311 for round constants.


Which encryption method supports random reads?

Any block cipher in CTR mode can be used to encrypt and decrypt data in arbitrary order.

Basically, to encrypt something in CTR mode, you use the block cipher to encrypt a simple sequence of values, like (1, 2, 3, 4, 5, etc.), and concatenate the results to produce a pseudorandom bitstream, and then XOR this "keystream" with the data you want to encrypt.  Since you can produce any block in the keystream at any time just by feeding the appropriate counter value into the block cipher, you can easily decrypt the data in any order.

(Yes, you can even decrypt pieces of data smaller than a single cipher block with CTR mode, even down to a single bit.  You do need to compute the keystream block by block, but you don't need an entire block of ciphertext to be able to decrypt it.  If reading the ciphertext is much slower than block cipher encryption, this may be a useful optimization, and you can always cache the keystream block in case you need it again.)

The work needed for CTR mode encryption is basically the same as for decryption, and depends on the block cipher you're using.  If you can find a usable AES implementation for your MCU, I'd recommend using it; it's a standard, widely used and well analyzed cipher.  As they say, nobody ever got fired for using AES.
If AES is too much for your MCU, you may want to look at specialized lightweight block ciphers like PRESENT instead.

Also note that CTR mode does not, by itself, protect message integrity — for that you need authenticated encryption.  However, many modern authenticated encryption modes, such as EAX, GCM and SIV, do essentially consist of CTR mode augmented by a message authentication scheme, and thus support all the features of CTR mode (including random-access decryption) once the data has been authenticated.  The authentication itself, however, normally requires reading and processing all the data, unless you choose to divide it into smaller segments and authenticate each segment separately.

Addendum: As CodesInChaos notes in the comments above, if the "file" you're encrypting might change, such that an attacker could observe several different ciphertexts corresponding to the same position in the file (encrypted with the same key and counter sequence), then CTR mode becomes quite vulnerable to attacks.

The reason is that, like with any other encryption scheme based on XORing the data with a fixed keystream, an attacker who can observe two distinct values encrypted with the same part of the keystream can recover the XOR of the plaintexts simply by XORing the ciphertexts.  If they can guess one of the plaintexts (say, because they know it's all zeros), this immediately reveals the other one.  For more information, see e.g. this earlier question.

That said, if the encryption is only done to transfer the file from the device to the host (i.e. the data is only encrypted "on demand" when it's requested by the host), it may be possible to solve this issue by constantly varying the key and/or the initial counter value, e.g. based on a running message counter or a high-resolution timestamp.

For example, assuming that you file is no longer than 64 GB, you could use the lowest 32 bits of the block cipher input for the counter (i.e. the position of the block in the keystream), the next 64 bits for a timestamp or a message counter (make sure it can never decrease, even if an attacker manipulates messages), and still (assuming a 128-bit block size like for AES) have 32 bits left over e.g. for a per-file unique nonce.  This would ensure that no part of the file is ever encrypted twice with the same keystream.

Also note that it's perfectly OK to apply this scheme as a second layer of encryption to transfer data that's already stored in encrypted form (possibly also using CTR mode, with a different key and/or initial counter value) on the device.  This could afford an extra measure of security against attacks involving physical disassembly of the device and direct reading of the stored data on it.


Is my high school cryptography/steganography science fair project practical?

which cryptographic algorithm and which steganography technique put together will result in the most efficient, secure data?

AES and DES are already a combination of separate algorithms involving multiple steps each.  They are already "put together".

Steganography won't add additional security because of Kerckhoffs’ principles.

  In what way other than encryption time should I measure the 'effectiveness' of the two techniques?

Computation time is not a good indicator of security. If AES and DES are used together, the security will be equal to AES' security by itself.  This is because DES' seed can be guessed faster than brute force - it has been broken.

  Is this a practical project? Can this be executed like a true science fair project

It is not a practical project because neither AES nor DES can be broken using any machine you own, therefore output (no matter how much you massage or analyse it) will always appear as random bits.  This means there will be no way to measure the security provided by combining methods.


Brute forcing ciphertext an offline attack, while attacking the authentication tag (the result of the CMAC-calculation) is an online attack: it requires an active oracle. That is: you can try and break the confidentiality of a message on your own PC network of computers. However, you need to send many ciphertext (including authentication tag) to a receiver to see if a guessed tag is correct or not and an invalid ciphertext is accepted (to test if a message is successfully forged). Generally you only get one oracle, and the speed of this oracle is usually limited (e.g. by networking speeds).

If an authentication tag is not accepted then that doesn't give any information to an attacker if the next message changes. This would for instance be the case if a unique sequence number is included in the messages (although usually the authentication tag is verified earlier, so oracle attacks would be possible). Furthermore, many protocols will break a session and re-establish the session keys if an incorrect authentication tag is received.

In conclusion: attacking an authentication tag is much harder than breaking a cipher, even if the order of the attack is the same. Because of this it makes sense to increase the key size even if the tag size stays the same.

If you need more than 128 bits of security is of course another question; 128 bits seems plenty as long as quantum computers are not available. 256 bit encryption should be considered for messages that require long-term protection.


Key management protocol for end-to-end security on Advanced Metering Infrastructure

In distributed systems it is often bad practice to have "Shared Master Key". If a bad guy breaks in one of your devices he has the most important crypto piece of the system, and you're pretty much done. Rather have one key per device, and these keys are signed by an Authority I would say.


When will a function $f$ be a truly random function?

definition of a truly random function

The question's definition is restricted to truly random functions from $\{0,1\}^{n}$ to itself, but has an easy and common extension to any to two finite sets.

  get some intuition for when a function $g$ will likely be truly random and when not

I like this intuitive definition: a function $g:\mathcal A\to\mathcal B$ is truly random if and only if, for any $x_0\in\mathcal A$, even with knowledge of $g(x_i)$ for all elements $x_i\in\mathcal A-\{x_0\}$, one can't predict $g(x_0)$ better than by a random pick in $\mathcal B$.

Thus to prove that a function is not truly random, one wants to exhibit a particular $x_0$, a particular subset $\{x_1,x_2\dots\}=\mathcal A'\subset\mathcal A$ with $x_0\not\in\mathcal A'$, and a method allowing to predict $g(x_0)$ with probability better than $1/|\mathcal B|$ given the $g(x_i)$ going with each $x_i$.

Hint to prove that $g(x)=f(x)\oplus f(\lnot x)$ is not truly random: one can pick any $x$ for $x_0$ (when we only need a particular one), $\mathcal A'$ can contain a single well-chosen element $x_1$ (when we could pick $|\mathcal A|-1=2^n-1$), and $g(x_1)$ then allows to predict $g(x_0)$ with certainty (when any probability better than $1/|\mathcal B|=2^{-n}$ is good enough), merely by using commutativity of $\oplus$.


It depends on the block cipher in question - specifically its key schedule. Knowing any round key of AES-128 would let you calculate the key, because the schedule is reversible. OTOH, e.g. TEA would retain secrecy of most of the key and might remain secure, because its round keys are small enough parts of the key.

In the case of DES, it is weak enough to be decryptable regardless of any information. However, knowing a round key would make it trivial, since every round key reveals 48/56 key bits, leaving only 8 bits to be brute forced.


Computational requirements for breaking SHA-256?

First of all, are my assumptions above correct? What would the
complexity of the three attacks be? I am also curious what "unit" a
number like $2^{256}$ implies - is it something like floating-point
operations that would be needed to run?

Almost, this number is the number of times the primitive (in this case SHA-256) must be called to break the algorithm (e.g. find a preimage or collision).

I am aware that SHA-256 is deemed secure given today's computational
power. Is it likely that increasing computer capacities (classical,
not quantum computing) will become a threat to this over the next
years?

No, SHA-256 will not be broken because of computational power. When you attack a hash function using brute force, the computation will take millions of years. $2^{128}$ operations is just too large a number.
However, most people expect that SHA-2 will be broken in the next 100 years. That is how the first preimage/collision will be found. What this means (in the case of collisions) is that somebody devises a smart algorithm which can find a collision without needing to execute this large amount of operations. Recently, Marc Stevens et al published an attack on SHA-1 which only needs
$9\,223\,372\,036\,854\,775\,808 \approx 2^{63}$ operations. This number is small enough to be searched through by Google's awesome computing cluster (and consequently the first known SHA-1 collision has been found).


Knowing N and a relationship between the 2 prime numbers(p and q) find p and q generated with RSA


How to generate a large random number from smaller ones?

Let's assume that randInt gives you cryptographically random (independent) numbers in the range $[0, N)$. Then you can generate a larger number by taking two of those, $x_1$ and $x_2$ and adding $x_1 + x_2 \cdot N$ (which is just bit concatenation if $N = 2^n$). That's a random number in the range $[0, N^2)$, assuming the original numbers were random and independent. If $N=2^n$, you can also drop bits off, i.e. take the value modulo some smaller power of two, without introducing biases.

To get a range that isn't a power of two in size, like a prime, you must use a modulus that's sufficiently small, or the low values will be more likely to show up. I.e. you must first overshoot the prime sufficiently, and then take the modulo. A factor of e.g. $2^{128}$ would be sufficient for 128-bit security. (Alternatively, you can use rejection sampling, but you wished to avoid that.)

If the original range isn't a power of two in size, which seems unlikely with a CSPRNG, you would likewise have to overshoot + modulo to get to a power of two range. Or directly to a prime range.

Now, if randInt isn't a CSPRNG, it may have biases that the above procedure compounds. But then, you shouldn't be using it for cryptography.


encrypting data signals using the time variations between two independent coupling functions

I found the paper.

At a glance, this seems to be a solution in search of a problem. Unless I've missed something, there is essentially no attempt in their paper to cryptanalyze such a construct. Nor do they appear to build upon, relate to, or even reference any preexisting concepts in modern cryptography or information theory such as computational indistinguishability or semantic security.

They also highlight some "advantages" of their system that, to someone with moderate familiarity of cryptography, seem pointless. For instance, statements like

  It results in an unbounded number of encryption key possibilities...

are indicators that the authors aren't familiar with the actual threats facing current cryptosystems. The entire space of 256-bit keys will never be enumerated in the lifespan of the universe, assuming our current understanding of information theory and physics are even remotely accurate. Nobody is clamoring for new cryptosystems with arbitrarily-large keys.

In my (admittedly non-expert) opinion, I find it highly implausible that any widely-used cryptosystem will ever be built upon the ideas in this paper.


Quadratic Residues in identification setting

The problem with the protocol isn't specifically that it allows Bob to perform square-roots on his own; it's that it allows Bob to deduce the factorization of $n$ with high probability (and with that, he can perform square-roots).

Here's how Bob would do this:

He selects a random value $0 < r < n$, computes $x = r^2 \bmod n$, and sends $x$ to Alice.
Now, $x$ actually has 4 square roots modulo $n$ (unless $x$ happens not to be relatively prime to $n$; that's improbable).  Alice picks one of the four, and returns that value $y$ to Bob.
Bob now has two values $r$ and $y$ with $r^2 \equiv y^2 (\bmod\  n)$, or in other words, $r^2-y^2 = (r-y)(r+y) = kn$ for some integer $k$ (note: this equation is in the ring of integers, not in the ring of integers modulo $n$).
If $r \ne y$ and $r \ne -y$ (probability 0.5, because $r$ was selected randomly, and $y$ has 4 possible values, 2 of which satisfy one of the relations, and 2 of which satisfy neither), then $(r-y)(r+y)$ is a multiple of $n$, but neither $(r-y)$ nor $(r+y)$ is a multiple of $n$.  Hence, one of $r-y$, $r+y$ must be a multiple of p, and the other must be a multiple of q.

That is, a straight-forward computation of $gcd( n, r+y )$ directly yields one of the prime factors of $n$.

This happens with probability 0.5; if Bob knows how Alice selects which of the four possible square roots (e.g. she always selects the one that is itself a quadratic residue), then he can increase this probability by putting conditions on the $r$ he selects.


Consider a multiplicative group of an order $q$ generated by some $g$. For simplicity, let commitment be $C_1 = g^{L_1}$. Consider a proof of knowledge of $L_1$ committed to at $C_1$. At the first step of an interactive proof, choose some $L_2$ at random and send $C_2 = g^{L_2}$ to the verifying party. Second step, receive a challenge $c$. Third step, send a response $d = c L_1 + L_2 \pmod{q}$. Now verify this response with $g^d=$ something computable by the verifying party. That is, an expression of something that was sent to verifying party before or while running the protocol.


Why does OpenPGP encryption produce different ciphertexts from the same plain text?

OpenPGP is a hybrid cryptosystem. The actual message is encrypted applying a symmetric cipher like AES with a random session key. This session key again is encrypted using a public/private key cryptography algorithm like RSA. This is mostly because symmetric encryption is much faster than public/private key cryptography, especially for large messages. As the session key is generated randomly, the cryptotext is different each time you encrypt something.

Another reason is that OpenPGP includes timestamps in different packets.


Validating a shared secret between two parties, one bit at a time

Assuming that you can run this protocol multiple times, it is completely insecure. Say we are an attacker trying to deduce Alice's secret and that the secret has length $n$.
We can then extract Alice's secret using at most $(n+n^2)/2$ times. Let's call the secret as $s$ and let $s_i$ denote the $i$th bit of $s$.

Our attack hinges on two key observations:
 1. For odd $i$, Alice will just send us $s_i$, if we know the prefix $s_1\|\dots\|s_{i-1}$ and execute the protocol honestly using an $s'$ with the same prefix.
 2. For even $i$, Bob needs to send the bit. If Bob sends the correct bit, Alice's answer will always be $s_{i+1}$ and therefore identical for multiple executions. If Bob sends the wrong bit, Alice's answer is random and thus will differ between two executions with probability $1/2$.

So for $1\le i \le n$ our attack proceeds as follows:

If $i$ is odd, choose a random secret $s'$ such that $s'_1\|\dots\|s'_{i-1} = s_1\|\dots\|s_{i-1}$ and perform the protocol honestly.
Note that by the correctness of the protocol  Alice's message in round $i$ of this execution will be $s_i$. Thus at the end of this execution we have learned $s_{i}$ with probability $1$.
If $i$ is even, choose a random secret $s'$ such that $s'_1\|\dots\|s'_{i} = s_1\|\dots\|s_{i-1}\|0$. Using this $s'$ run at most $n$ executions of the protocol. Let $\bar{s}_j$ denote the bit sent by Alice in round $i+1$ of the $j$th execution. If there are ever $j,j' \in \{1,\dots,n\}$ such that $\bar{s}_j \neq \bar{s}_{j'}$ we can abort and deduce that $s_i=1$. Otherwise, if $\bar{s}_j = \bar{s}_{j'}$ for all $j,j' \in \{1,\dots,n\}$, then we can deduce with probability $1-2^{-n}$ that $s_i=0$ and $s_{i+1}=\bar{s}_j$. So overall, we have learned at least $s_{i}$ with probability at least $1-2^{-n}$.

After at most $(n + n^2)/2$ executions we have thus revealed $s$ with probability at least $(1-2^{-n})^{n/2} > 1-2^{-n/2}$.


Memory-hard operations in work-factor hash functions

The pseudocode you are showing here is not "memory-hard" - one can recreate the long sbox from the short "pass" when needed, by only 512 SHA-512 calls.

These calls are of increasing input length (i.e. need more time), but even this can be cut short by conserving part of the hash state during the loop (as SHA-512 is an iterative hash function and not a random oracle), allowing to calculate the result in $O(n)$ time ($n$ being the output length, in your case 32768).
This shortcut can be removed by appending the new hash result in front instead of at the end (or by another kind of shuffling between the rounds of your loop), but there might be other ones I can't think of right now.

Also, 64 KB of memory is not "very much" - you would need (scalably) many of those S-boxes which all are accessed (and changed) often, to be memory-hard.


Why do Problems for Post-Quantum algorithms have to be NP-Hard?

I am unaware of cryptography that is hard solely assuming that $P\neq NP$, so I believe you are misunderstanding something. I know the story best when it comes to lattices, so I'll discuss why lattices are solely "adjacent" to an $NP$-hard problem.
The story is rather simple, but also technical.
Let $\mathsf{LWE}[n, \sigma, q]$ be the average-case LWE problem in dimension $n$, standard deviation $\sigma$, and moduli $q$.
Regev's quantum worst-case to average-case reduction for LWE states that:
$$\mathsf{SIVP}_{\tilde{O}(nq/\sigma)} \leq \mathsf{LWE}[n, \sigma, q]$$
Where $\mathsf{SIVP}_\gamma$ is the short independent vectors problem (think of it like a generalization of the shortest vector problem to finding $n > 1$ short linearly independent vectors, where $n$ is the dimension of the lattice).
Note that the $\gamma$ here is an approximation factor that is allowed in the problem.
What is the precise complexity of $\mathsf{SIVP}_\gamma$?
This highly depends on the parameter $\gamma$, but the following should suffice for this post.
It is known that $\mathsf{SIVP}_{\tilde{\Omega}(\sqrt{n})}$ is in $\mathsf{AM}\cap co\mathsf{AM}$.
This implies that it is not $\mathsf{NP}$-hard unless the polynomial hierarchy collapses to some finite (it looks like 2nd?) level, which complexity theorists view as being unlikely.
This essentially means that while $\mathsf{SIVP}_\gamma$ is known to be NP-hard for some $\gamma$, the $\gamma$ used in lattice cryptography is such that we view it as extremely unlikely that $\mathsf{SIVP}_\gamma$ will be NP-hard.
Still, for basic protocols one can generally take $\gamma$ to be some small polynomial, so $\mathsf{SIVP}_\gamma$ is "close" to an NP-hard problem, especially as the smallest approximation factor that we have polynomial-time algorithms for is something sub-exponential iirc.
More generally, NP hardness is the wrong thing to look at in cryptography.
What people actually want is some notion of average-case hardness.
In lattice cryptography one can formally connect that with worst-case hardness, but not every area in cryptography has such reductions.
In areas that don't, the particular worst-case hardness of the problem is not very important --- a problem can have some instances that are very hard while still being bad for cryptography, as it may be hard to generate a hard instance.
What is more important is specifying some plausible average-case hard distribution and examining the particular hardness of this.


The solution of insert MAC in a ciphertext without Authenticated Encryption supported

The salt, if used at all for a Key Based Key Derivation Function (KBKDF), may be send in plaintext. There is generally no reason for salts to be kept secret.

As already noted in the comments by SEJPM, there is no direct need for a salt for a KBKDF. You may however well use it to strengthen the security of the KBKDF. The HKDF RFC (section 3.1) nicely explains the reasons why you might want to supply a salt.

Notes:

You could also derive an IV from the KBKDF if you'd use a salt (using another Info parameter, e.g. "IV") - in that case you don't need to send it with the ciphertext;
Generally the authentication tag (HMAC value) is placed at the end of the ciphertext, but that doesn't matter with regards to security.


How does encrypt-then-MAC protect from CCA?

What CCA basically means is that attacker supplies for decryption any ciphertext he/she wants and observes the reaction of the system. This reaction can be used to infer information about plaintext/key. Many dangerous attacks are based on changing some bits in the ciphertext and observing how when and how the system fails. This is often enough to partially or fully recover plaintext or key. What authenticated encryption (particularly encrypt-then-mac approach) basically does is prevent attackers from being able to change ciphertext. Doing so requires recomputing of mac, which by definition can't be done without knowing the mac key, otherwise decryption immediately fails due to incorrect mac, and as the system doesn't know anything about the plaintext at this point, the attacker can't possibly learn anything too.

Attacker's own application is useless in this case, as without the key itself any decryption failure just points to one and only obvious reason - wrong key.


Signature operations may leak the private key; signature verification should be safe?

The authors of the code also wrote:

  WARNING: Vulnerable to timing attacks.

They know their code can leak information thru timing of its operation. Therefore, they rightly wrote:

  Signature operations may leak the private key.
  Signature verification should be safe.

The first sentence is because, due to the aforementioned information leak, the confidentiality of the private key (which must be used to perform a signature, and should be kept secret) could be compromised during a signature generation operation.

The second sentence is because, in a signature verification, the public key is used, and that is not secret. Thus, information leak is much less of an issue, and can't compromise the confidentiality of a key. However, there are rare situations where the signature itself is deemed secret (say, because it can be reused); that might explain the use of "should".


(minisign author here)

As noted by corpsfini, keys encode the Y coordinate. The X coordinate is recovered using the curve equation: X = sqrt((Y^2 - 1) / (d Y^2 + 1)).

The square root has two solutions, so we need to encode the sign of x as well. Since coordinates only require 255 bits, we have a extra bit, used to encode the sign.

X and Y ∈ [0; 2^255-19[, so 16 bytes wouldn't be enough to encode them.


The problem is in the last equation:
$$
Pr[\mathcal{A}^{\{U\}}(1^{\lambda})=1]=Pr[\mathcal{A'}^{\{U\}}(1^{\lambda})=1]
$$

It does not hold because $\mathcal{A}^{\{U\}}$ is the result of $\mathcal{A}'$ using $U$ instead of $F_k$. This is actually equivalent to $F'$ and will be distinguished by $\mathcal{A}'$, so we get
$$
Pr[\mathcal{A}^{\{U\}}(1^{\lambda})=1]=Pr[\mathcal{A'}^{\{F'(U)\}}(1^{\lambda})=1]\neq Pr[\mathcal{A'}^{\{U\}}(1^{\lambda})=1]
$$


What is the practical impact of using System.Random which is not cryptographically random?

You asked for the practical impact, so the answer is that for \$120 I could probably have your entire password database done by tomorrow.

Here is your program, or something similar to it:

using System;
using System.Text;
using System.Security.Cryptography;

class Program {
    static void Main(string[] args) {
        byte[] pwd = new byte[128];
        byte[] salt = Encoding.ASCII.GetBytes("saltsalt");

        var rand = new Random();
        rand.NextBytes(pwd);
        Rfc2898DeriveBytes k = new Rfc2898DeriveBytes(pwd, salt, 1000);
        Console.WriteLine(System.Convert.ToBase64String(k.GetBytes(16)));
    }
}

We should spend a bit of time talking about your salt. I've assumed it's fixed. You'd usually randomly generate it - if you use a single System.Random instance for both the salt and the password then the attack is basically the same. If you're creating two System.Random instances, one after the other, then you're unlikely to gain anything given how the default seed is generated. If your salt is based on an incrementing counter or usernames or something, what I'm about to say only really applies to attacking a single password rather than an entire database. You should still be concerned either way.

I compiled this and ran it on my own machine, and it gave me the key IDWrj6Fd9c4kqJ6A2FHDEg==.

Let's try and break it! System.Random is well-documented: https://docs.microsoft.com/en-us/dotnet/api/system.random.-ctor?view=netframework-4.8. It uses a 32 bit integer key, and in fact if the key is negative the docs tell us that it actually uses the key's absolute value for some reason. Handy! That's only 31 bits! Let's break it with this program:

using System;
using System.Text;
using System.Linq;
using System.Security.Cryptography;

class Program {
    static void Main(string[] args) {
        byte[] target = System.Convert.FromBase64String("IDWrj6Fd9c4kqJ6A2FHDEg==");
        byte[] pwd = new byte[128];
        byte[] salt = Encoding.ASCII.GetBytes("saltsalt");

        for (int i = 0; i < Int32.MaxValue; i++){
            if (i % 1024 == 0) {
                Console.WriteLine(i);
            }
            var rand = new Random(i);
            rand.NextBytes(pwd);
            Rfc2898DeriveBytes k = new Rfc2898DeriveBytes(pwd, salt, 1000);
            if (k.GetBytes(16).SequenceEqual(target)){
                Console.WriteLine("pwnt");
                Console.WriteLine(i);
                Environment.Exit(0);
            }
        }
    }
}

How long will this take to run?

dnSpy is a handy tool for reverse-engineering C# applications, and we can use it to take a look at what the default constructor for System.Random does. Yours might be different, but in mine an unseeded System.Random sets the seed to Environment.TickCount, which is the number of milliseconds that have passed since the computer was booted up. I don't leave my computer running for more than a couple of hours at a time, so Environment.TickCount is probably not going to be any bigger than 36,000,000. Watching the keys go by, I'm trying about 14,336 keys per minute. 36000000/14336 = 2511 minutes to try all the feasible keys, so it should finish within about 40 hours.

40 hours of a crappy C# program on a laptop is not secure at all. Even if you picked your seed better, 2147483648/14336 = 149796 minutes, so about 2,400 hours. I suppose I could spend some time re-writing my trash-tier C# program so that it runs faster - it's definitely really slow and can be improved massively - but I don't care enough about your passwords to do that. It's easier to just run a few thousand instances starting at different seeds for an hour each.

Amazon will sell me CPU hours at around \$0.05 per hour so it'd cost me \$120, plus a bit of time and faff writing the code and getting it on their servers, to crack your entire password database. Probably less, since my laptop is likely slower than their compute nodes.

Most of the time here is spent actually computing the PBKDF2 function. PBKDF2 is pretty great and you should still use it - it's designed to be slow precisely so that attacks like this are inefficient. The \$120 estimate is based on using 1,000 iterations in your PBKDF2, which takes a couple of milliseconds per hash on my machine. You could make this attack cost \$1200 by just tuning that parameter to 10,000 instead, though a determined attacker would still happily pay that to get their hands on your users' data. If you wanted this attack to cost me $1,200,000, you could use 10,000,000 iterations! You'd also be wasting a couple of hours every time you wanted a password. I don't know what your application is doing, but if it's spending all that time computing hashes then it'd probably make more money mining Bitcoin or something.

Basing your password scheme on non-cryptographic random number generator isn't a very good idea. Use this one instead: https://docs.microsoft.com/en-us/dotnet/api/system.security.cryptography.rngcryptoserviceprovider.getbytes?view=netframework-4.8. If you were to instead generate 128 bytes from a CSPRNG, then this kind of brute force would start costing me several quadrillion dollars of compute time, which is a few hundred times the GDP of the entire planet. No organisation has anything close to this level of compute power.


SHA-1 – Why are text containers used for certificates?

The PDF or PostScript is used so that the collision is made very graphic. It is a public relation tool.

Known collision attacks on hash functions like MD5 and SHA-1 have some restrictions: the attacker can choose most of the colliding pair of messages, but the two blocks where interesting things occur are essentially random, and they will differ by only a few bits. The remainder of the colliding messages will be the same for both messages. So, as plain text, these blocks will be definitely non-pretty, and that's where the collision occurs. Thus, a plain ASCII text demonstration of the collision will not be "convincing" except for cryptographers.

Use of PostScript or PDF allows to leverage that small difference into arbitrarily spectacular differences; basically, the attacker can choose two completely different graphical contents for the whole page.

When the first collisions on MD4 were published, Dobbertin made the effort of making a sort-of ASCII text demonstration. His colliding pair consists in:

********************
CONTRACT

At the price of $176,495 Alf Blowfish sells his house to Ann Bonidea. ...

and:

********************
CONTRACT

At the price of $276,495 Alf Blowfish sells his house to Ann Bonidea. ...

in which the "*****" are twenty ugly-looking bytes that the attacker will claim to be there "for security reasons". MD4 is sufficiently broken that Dobbertin could make a demonstration with such mostly ASCII text, but he still had to include bytes that do not map to meaningful ASCII text.


Can you explain Bleichenbacher's CCA attack on PKCS#1 v1.5?

When encrypting something with RSA, using PKCS#1 v1.5, the data that is to be encrypted is first padded, then the padded value is converted into an integer, and the RSA modular exponentiation (with the public exponent) is applied. Upon decryption, the modular exponentiation (with the private exponent) is applied, and then the padding is removed. The core of Bleichenbacher's attack relies on an oracle: the attack works if there is some system, somewhere, which can tell, given a sequence of bytes of the length of an encrypted message, whether decryption would yield something which has the proper padding format or not.

An example would be a SSL/TLS server. In the initial handshake, at some point, the client is supposed to generate a random key (the "pre-master secret"), encrypt it with the server's public key, and send it. The server decrypts the value, obtains the pre-master secret, and then compute from that pre-master secret the keys used for symmetric encryption of the rest of the connection. Using the standard for guidance, the client sends a ClientKeyExchange (which contains the encrypted pre-master secret), then a ChangeCipherSpec, then Finished; this last message is encrypted with the derived symmetric key and its contents are verified by the server.

If the client sends a random sequence of bytes of the right length to the server instead of a properly encrypted pre-master secret, then the server will, most of the time, respond with an error message telling "I tried to decrypt your ClientKeyExchange contents, but this failed, there was not a proper padding in it". However, by pure chance, it may happen that the random string, after applying the modular exponentiation, yields something which really looks like a pre-master secret with correct padding. In that case, the server will not complain about the ClientKeyExchange, but about the Finished message, which will be incorrectly encrypted.

This is the information the attacker wants: whether the sequence of bytes he sent would, upon decryption, look properly padded or not.

Let's see with a bit more technical details. In RSA, let $n$ be the public modulus. Let $M$ be a message to encrypt with $n$ (in the case of SSL, $M$ is the pre-master secret, of length 48 bytes). The PKCS#1 v1.5 padding, for encryption, consists in adding some bytes to the left, so that the total length after padding is equal to that of $n$. For instance, if the server's public key is a 2048-bit RSA key, then $n$ has length 256 bytes, so the padded $M$ should also have length 256 bytes.

A properly padded message $M$ has the following format:

0x00 0x02 [some non-zero bytes] 0x00 [here goes M]

so the sequence of bytes will begin with a byte of value 0, then a byte of value 2, then some bytes which should have random values (but not zero), then a byte of value 0, then $M$ itself. The number of non-zero bytes is adjusted so that the total length is equal to the length of $n$. Upon decryption, the server will look at the first two bytes, and require them to be equal to 0x00 and 0x02, in that order. Then it will scan for the next byte of value 0, thus skipping over all the random non-zero bytes. This way, the padding can be unambiguously removed.

It follows that if the client sends a random string of bytes, then it has probability roughly between $2^{-15}$ and $2^{-17}$ to follow the PKCS#1 padding format (that's the probability that the first two bytes are 0x00 0x02, and that there is at least one byte of value 0 afterwards; exact probability depends on the length and value of $n$).

The attack scenario is the following:

There is a SSL server, which will send distinct error messages depending on whether a proper PKCS#1 padding was found or not. Alternatively, the two cases could be distinguished through some other information leak (e.g. the server takes longer to respond if the padding was correct).
The attacker eavesdropped on a connection, and would like to decrypt it. He observed the ClientKeyExchange, so he saw an encrypted message $c$. He knows that $c = m^e \pmod n$ where $e$ is the public exponent, and $m$ is the padded pre-master secret for that connection. He wants to recover $m$, or at least the pre-master secret which is contained in $m$, because that will allow him to compute the symmetric keys used for the connection.

Then the attacker will initiate many connections to the server. For each connection, the attacker generates a value $s$ and sends, as ClientKeyExchange, a value $c' = cs^e \pmod n$. The server decrypts that, and obtains $m' = (cs^e)^d \pmod n$ ($d$ is the private exponent), which is equal to $ms \pmod n$. Most of the time, this $ms$ value will not be properly padded (it will not begin with 0x00 0x02 or will not contain an extra 0x00). However, with a low but non-negligible probability (once every 30000 to 130000 attempts, roughly), luck will have it that the $ms \pmod n$ value looks padded. If that is the case, then the server's behaviour will inform the attacker of that fact. The attacker then learns that, for this value $s$ (the attacker knows it, since he chose it), then $ms \pmod n$ is in a specific range (the range of integers which begin with 0x00 0x02 when encoded in bytes using big-endian convention).

The rest of the attack is trying again, with carefully chosen random values $s$. Each time the server responds with "that was a proper PKCS#1 padding", this gives some information which helps the attacker narrow his guesses on $m$. After a few million connections in all, the attacker learned enough to pinpoint the exact $m$, yielding the pre-master secret.

See the original article for details; once you know how the RSA padding works, the rest is just maths, which are not too hard.

To prevent this attack, SSL servers do not inform the client about padding woes. If decryption fails because of a bad padding, then the server continues with a random pre-master secret (the true failure will then occur when processing the Finished message).

One may note that the specific weakness of the PKCS#1 v1.5 padding (for encryption) is that it is not very redundant; the random bytes are, indeed, random, without any specifically enforced value. This is what allows a sequence of random bytes to be "properly padded" with a small but not negligible probability. Newer versions of PKCS#1 describe a new padding type, called OAEP, which uses hash function to add a lot of internal redundancy, which makes it extremely improbable that a random string matches the padding format. This prevents Bleichenbacher's attack. Unfortunately, SSL still uses PKCS#1 v1.5.


Different inner and outer hash functions for NIST-recommended HMAC?

You may want to take a look at the original HMAC paper by Bellare, Canetti and Krawczyk (1996), or at the new security proof by Bellare (2006).

As far as I can tell at a glance, there's nothing in either of these proofs that would actually rely on the inner and outer hash functions being the same function, as long as both of them satisfy the appropriate security properties.


Time complexity of looking up in a rainbow table

If we count a single application of a reduction function as 0.5 calculation [...]

That does not seem to be an assumption made in the paper? I would expect the reduction function to take much less time than a hash/cipher, so discounting them completely is a good enough approximation. That gives the value in the paper.

If you count it as 0.5, then it would take $0.5 + 2 + 3.5 +\dots + (t-1+0.5t)$ rather than what you have, since at each step you add 1.5 work for both another hash/cipher and another reduction.

  In contrast, the original method seems to call for $t(t-\frac{1}{2})$ calculations, fewer than the author's $t^2$.

This part I am not sure about. I would think it should be $t(t-1)$, which matches the later text saying that a rainbow table approach takes half the time of the original.


Why TLS uses in-band handshake signalling

IPSec uses IKE for a key agreement between two endpoints. Here the key agreement protocol uses a separate UDP based transport channel. The data from applications is not sent through this UDP port.

Actually, I see two incorrect statements here

IPsec doesn't always use IKE to do key agreement.  Quite often it does, however there are real world implementations where IPsec is used with some other protocol.
Even if IPsec and IKE are used together, sometimes they use the same UDP port.  If they're are using NAT-T (RFC 3947, 3948), then all the traffic (both IKE and IPsec) will go through the same port.

However, to address your question:

  Why TLS designers chose to use same transport layer port for both handshake and application protocol?

I'm not Eric Rescorla, however I suspect they never really considered the possibility of using two separate ports for control and data.  If they had, they would have immediately seen that, for them, using one port was better because a) it simplified things for them, and b) they had no reason not to.

As for the simplified, for one, there's no ambiguity in the control records as to which data channel they're talking about.  In addition, TLS assumes that records flowing in the same direction are delivered in order, hence they don't need to worry about situations where they issue a control record, and then a data record, and the data record arrives first.  If they used different TLS ports, that would be a possibility that would need to be addressed.

  What would be the implications if a TLS like security protocol is designed to run handshake and application protocols to run on different transport layer ports?

There would need to take care about the concerns I mentioned above (not too hard), and they would also have to worry about middle boxes (firewalls, NAT devices) getting confused about the relationship of these two not-obviously-connected TCP flows.


Intuition for random variables in cryptography

We use the random variable to indicate the "by what" part of "the probability of $k$ being output".


Is there any vulnerability if I hmac(key,key)?

This is all useless.

The point of hashing passwords is to prevent a hacker who obtained the database with the hash to retrieve the original password.

With a short pin (assuming 4 digits) a hacker will simply calculate your hmac for all 10000 possible codes. None of your variations will make any significant difference.
A secure hash will hardly help either.


Cryptographic security of PHP mt_rand() function using Mersenne Twister algo

Well, the chief vulnerability is that if an attacker is given a large enough sample of Mersenne Twister output, he can then predict future (and past) outputs.  This is a gross violation of the properties that a cryptographically secure random number generator is supposed to have (where you're supposed to not even be able to tell if the random bit string could have been produced by the RNG in question).

As for how this weakness may be exploited, well, consider if you use the output of the MT as a keystream for a stream cipher (that is, you exclusive-or it with the plaintext to form the ciphertext).  Then, if the user sees an encrypted message, and correctly guesses a part of the plaintext which is 2496 characters long, he can then immediately recover the internal MT state (and decrypt the entire message).  Even worse, if the user has a section of ciphertext 19968 characters long for which he knows that the corresponding plaintext had all MSBits clear (say, he knows that section was standard ASCII), then he can then use that to decrypt the entire message (even though he initially had no idea beyond that what the contents of that section were).

The first weakness (2496 bytes of consecutive outputs allows the attacker to recover the MT state) is fairly straightforward to explain; we examine the last four operations of the MT immediately before the output:

s1 ^= (s1 >> 11);
s1 ^= (s1 << 7) & 0x9d2c5680U;
s1 ^= (s1 << 15) & 0xefc60000U;
return ( s1 ^ (s1 >> 18) );

If we look closely, we see that these operations are all invertible; that is, if we were given a 4 byte output of the MT, we can compute the value s1 had before these operations took place.

Now, what MT does is update its state, and then output its entire state (disguised by the above transformation).  Now, an attacker can invert this transformation, and so directly observe the MT state.  All he needs is 624 words of output (or 2496 bytes), and he has learned the entire state; he can advance the MT forwards (or backwards; the update function is invertible), and generate as much output as he wants.

Now, one possible nit is for this straight-forward approach to work, these 2496 bytes must correspond to one MT reload cycle; that is, start at a multiple of 2496 bytes from the start of the stream).  While this would be easy to work around (if we're given 4991 consecutive bytes of output, then there will be a 2496 byte section that lives entirely within a reload cycle), it turns out that we needn't bother, because it's broken even worse than that.

The second weakness is that, if we can get just about any sample of 19968 bits of output, we can also recover the MT state, and it doesn't matter of all those bits are from the same MT reload cycle, or spread across multiple.  As for how this works, well, when we examine the MT update and disguise functions, we see that they're all linear in GF(2); this means that all outputs are linear functions of the 19968 initial state bits.  Hence, if we get 19968 output bits, we can form 19968 linear equations on the initial state bits, and solve that set of linear equations.  That gives us the initial state, and from that, we can compute everything.  Now, some sets of 19968 linear equations might not turn out to be linearly independent; in practice, all that means is that we might need a couple extra known bits, or just deal us having a couple of different possibilities for initial state; neither of these are significant difficulties for an attacker.

Hence, the bottom line is that Wikipedia is right, Mersenne Twister is not even slightly cryptographically secure, and should not used as if it were.


The NSA created SHA (quickly replaced by SHA-1 to fix a security issue that remained unpublished for years) because they/the US government needed a 160-bit hash function, so that it has 80-bit security against collision-resistance, in particular towards use in the DSA signature system of FIPS 140.

In this usage, a hash functions condenses a possibly large piece of information $m$ (e.g. a 10MB file) into a smaller, easier to manipulate piece of information $h=H(m)$ (20 bytes for SHA-1), wich is what really gets signed. The hash must be collision-resistant, so that an adversary can't come with two distinct messages $m$ and $m'$ with $H(m)=H(m')$, which would allow the adversary to obtain a signature for $m$ from a legitimate signer, and pass it as the signature for $m'$.

SHA-1 uses principles similar to the earlier 128-bit MD5, but with a more regular design. Also it is big-endian, likely because that's customary (to the point of being unstated) in NIST crypto standards including DES/FIPS 43.


Is TEA suitable for encrypting/authenticating many short messages?

The main reason for using encryption is not so much secrecy, but authentication and protection against interference.

In that case, what you want is an authenticated encryption scheme.  While TEA, as a block cipher, may be used to implement such a scheme by using it in some suitable AE mode (such as SIV), there are also a number of dedicated lightweight authenticated encryption schemes that you may wish to look into.
In particular, I'd suggest taking a look at Ascon, which was selected as the primary choice for the use case 1 (lightweight authenticated encryption) in the final round of the CAESAR competition last year.  While not quite as simple as TEA, the reference implementation isn't all that complicated.

Since your message length is fixed and very short, you could obtain a simple authenticated encryption scheme just by using a block cipher with a block size longer than your message length, padding your messages up to the block size e.g. with zero bytes, encrypting the padded message directly with the raw block cipher (i.e. in "ECB mode") and verifying the correctness of the padding after decryption.
However, for this you'd want a block cipher with a block size of (at least) 128 bits (= 16 bytes), which TEA doesn't have.  XXTEA could work, though.
With 4 bytes of padding, the odds of an attacker randomly guessing a valid ciphertext would be 1/232 per attempt, which seems likely to be low enough for your purposes.  This would be a deterministic encryption scheme, so it would leak whether or not two plaintexts are equal, but that shouldn't be an issue for you since your messages include presumably unique timestamps anyway.

As for the security of TEA or other crypto primitives for your purposes, the first thing I'd like to note is that it seems extremely unlikely that anyone would develop and implement a novel cryptanalytic attack just to interfere with your system.  Thus, you should be fine as long as the scheme you're using:

has withstood any serious cryptanalysis at all (i.e. it's not just some random homebrew cipher kludged together by someone with no crypto experience),
has no known practical attacks (i.e. with complexity well under 264 or so operations) with published attack code that someone could just download and run, and
the way you're using it isn't broken in some way that would allow someone to bypass the actual cipher entirely.

In fact, you might be fine even if one or more of the above happened to be false, as long as none of your potential opponents has the skills or motivation to analyze your scheme and develop an attack against it.  But as long as you're using a cipher with no simple practical attacks, and use it correctly, you should be safe even if someone with some crypto skills does decide to try to attack your system.
Honestly, your biggest weakness is likely to be the last point.  That's how most cryptosystems get broken in practice — not by breaking the underlying ciphers or other crypto primitives, but by finding bugs or design flaws in the way they're used.
To give a simple analogy, the strongest lock on your door won't help if you leave a window open or leave the key under your doormat.  With crypto, as with physical security, the whole system is only as secure as its weakest link.  And the weakest link in your system is almost certainly not the block cipher, whether it's TEA or AES.


I am assuming that you wish to consider this for standard encryption tasks, and I am going to ignore the specific reference to AES and talk about general block ciphers (pseudorandom permutations).

The answer is that small block sizes are very problematic. In particular, they break when used for encryption of any reasonable amount of information. I will consider two concrete examples. In CBC mode, security breaks down after $2^{n/2}$ blocks, when $n$ is the block length. This means that you could not encrypt more than $2^8=256$ blocks, which is just 512 bytes. This is due to birthday collisions. However, it's actually worse than this. The probability of having a collision at less than 256 blocks is not so small, and at such small numbers it is very problematic. If you use CTR mode, then once again you have a problem since the nonce/IV has to be unique. Even if you are using this from fresh each time with a new key, and so just use a counter beginning at 0, you still have a problem that you can't encrypt more than $2^{16}$ blocks, which is just 128KB.

Regarding constructing such a small block cipher, this can be done using the techniques from format-preserving encryption. You use a Feistel, but you need many rounds with such a small block (also making it very inefficient). Specifically, you need 24 rounds of Feistel (this is the current recommendation but there is also a concerning lack of clarity regarding the exact security in this case).


How much data can I encrypt with AES before I need to change the key in CBC mode?

The $1/2^{32}$ is an arbitrary figure, based upon one particular value for what counts as an acceptable risk.

You need to decide what is an acceptable risk.  If you think that a $1/2^{32}$ probability of failure is an acceptable risk, then this calculation is relevant to you.  If you think it isn't, then decide what you think is an acceptable risk and re-do the calculation based upon the number you think fits your particular situation.

Keep in mind a $1/2^{32}$ probability of failure is pretty darn small -- in many settings, it may be acceptable.  It's far more likely that the next time you'll get into a car, you'll end up in a car accident: the probability of that is probably much higher than $1/2^{32}$.
Also keep in mind that life is about risk: you can never completely eliminate all risk from your life.  So, decide what is an acceptable risk, then you based upon that you can decide how much data you can encrypt under a single key, using a calculation similar to that one shown here.


Xor can help find bits not yet known, whether most significant or least significant; and help the adversary find more information about both ciphertext and plaintext, especially if a table of potential plain texts or even keys is stored in conjunction with bitwise Xor.

Some reading:

http://www.researchgate.net/publication/2633994_Luby-Rackoff_Ciphers_over_Finite_Algebraic_Structures_or_Why_XOR_is_not_so_Exclusive

Although this has minor typos, the notes on Feistel networks and Xor is excellent:

https://github.com/FredericJacobs/Cryptography-Stanford-Notes/blob/master/crypto-notes.md

Luby-Rackoff, as you may already know, is a key component of the Feistel network and it is not secure in 1,2, or 3 layers. Luby-Rackoff must have a 4 independent layered Feistel network structure from independent seeds to be considered a strong pseudo-random permutation. No less than 3 independent rounds must be used to even be considered a pseudo-random permutation though it is much weaker. Some consider a 3 round Feistel to be a secure pseudo-random function, but 4 rounds proves to be more secure.

No more than 8 corresponding outputs from the 32 pairs of inputs of the Xor should exist.

I suggest learning more about Xor and differential cryptanalysis.

Please focus most on pages 4-7 and 11-16, but the whole article is interesting if you have time:  http://cs.ucsb.edu/~koc/ccs130h/notes/dc1.pdf

It covers the tables and Xor technique in much better detail.


What you are describing is a strange version of OFB mode, using a hash function instead of a block cipher and modular addition instead of XOR to combine the data with the keystream. The algorithm you describe appears vulnerable to known plaintext attacks. A simple tweak to make it more similar to true OFB mode would improve security. OFB mode is a stream cipher mode:

\begin{align*}
O_i = E_K(O_{i-1}) \quad\text{where}\quad O_0 = IV
\end{align*}

The keystream is $O$, so encryption and decryption is implemented as in any stream cipher:

\begin{align*}
C_i &= P_i \oplus O_i\\
P_i &= C_i \oplus O_i
\end{align*}

This technique can be visualized:

The block cipher, $E$, can be replaced with any keyed hash function. The hash function must be keyed and the initial input must be an IV, not a key, otherwise it is vulnerable to a known plaintext attack where an attacker who can derive one of the outputs can use it to calculate the rest of the keystream. Your current construction is $O_i = H(O_{i-1})$ where $O_0 = H(K)$, with multiple blocks of keystream $O$ being used to encrypt a single block of plaintext. If I understand this correctly, this does not resist known plaintext attacks. Instead, you need to use a keyed hash and the first input should be an IV. One of the most common keyed hash constructions is an HMAC:

\begin{align*}
\operatorname{HMAC}_K(m) = H((K \oplus \mathrm{opad}) \mathbin\| H((K \oplus \mathrm{ipad}) \mathbin\| m))
\end{align*}

The $\oplus$ represents the XOR operation. Any operation that can be reversed with the same input can be used for this purpose, not just XOR. In your scenario, a Caesar cipher functions as modular addition, so if I understand what you are describing correctly, it should have similar security to OFB mode, including its pitfalls (short permutation cycles, for example), as long as you replace your hash function with a proper keyed hash like an HMAC.


Understanding an encryption technique algorithm

To be honest, this paper looks like garbage. It refers to Base64 as an "encryption algorithm" in section 2.2. Figures 1 and 2 were
created by a moron. But anyway...

  Consider the sequence for 0 to n-1 values for a source text of size n = pow (p, p) characters.

If $p = 4$, then $n = p^p = 256$ and we'll be working with a block of 256 bytes. But for brevity, I'll consider the simpler case where $p = 3$ and restrict the cipher alphabet to the 26 letters of the alphabet plus the space character.

Presumably the pass phrase will have to be padded to the block size before applying this algorithm, but the paper doesn't describe how to do this. Let's assume we're starting with the 27-character keyphrase THIS IS MY SECRET KEYPHRASE.

  Convert each element of the sequence into a form with base p.

If ' '=000, 'A'=001, 'B'=002 and so on, up to 'Z'=222, we get the following:

202 022 100 201 000 100 201 000 111 221 000 201 012 010 200 012 202 000
102 012 221 121 022 200 001 201 012

  Represent the values of step 2 in a matrix form A of order n x p.

$$A = \begin{bmatrix}
2&0&2&0&2& \dots &0&0&1&1&1\\
2&2&1&0&0& \dots &0&2&0&0&0\\
1&0&2&0&1& \dots &0&1&0&1&2\\\end{bmatrix}$$

  Subtract 1 from each element of A.

$$A = \begin{bmatrix}
1&-1&1&-1&1& \dots &-1&-1&0&0&0\\
1&1&0&-1&-1& \dots &-1&1&-1&-1&-1\\
0&-1&1&-1&0& \dots &-1&0&-1&0&1\\\end{bmatrix}$$

  Consider a random matrix B of size p x p.

This is under-specified. But let's assume the elements of $B$ are all in the range from $0$ to $n-1$:

$$B = \begin{bmatrix}
21&16&5\\
15&23&8\\
3&10&10\\\end{bmatrix}$$

  Multiply the matrix A with B to generate a result matrix R.

$$R = B \times A = \begin{bmatrix}
37&-10&26&-42&5&\dots&-42&-5&-21&-16&-11\\
38&0&23&-46&-8&\dots&-46&8&-31&-23&-15\\
13&-3&13&-23&-7&\dots&-23&7&-20&-10&0\\\end{bmatrix}$$

  Substitute all positive integers of R with +1, negative integers to -1 and zero by 0 using a substitute function.

$$R = \begin{bmatrix}
1&-1&1&-1&1&\dots&-1&-1&-1&-1&-1\\
1&0&1&-1&-1&\dots&-1&1&-1&-1&-1\\
1&-1&1&-1&-1&\dots&-1&1&-1&-1&0\\\end{bmatrix}$$

Wait a minute; if $p > 3$, then isn't matrix $R$ going to consist mostly of ones? Maybe $B$ should also include negative values? Who knows?

  Increment each element of R by 1.

$$R = \begin{bmatrix}
2&0&2&0&2&\dots&0&0&0&0&0\\
2&1&2&0&0&\dots&0&2&0&0&0\\
2&0&2&0&0&\dots&0&2&0&0&1\\\end{bmatrix}$$

  Convert each row of R, from the base p to decimal to generate the key sequence set.

This can't be right. Although $p=3$ in this example, the elements of $R$ consist of the values 0, 1 and 2 for any value of $p$. However, according to the encryption algorithm discussed later in the paper, we're supposed to end up with a set of $n$ values. So I guess we just replace each group of $p$ elements in $R$ with the result of interpreting them as digits in base $p$:

$$K = \begin{bmatrix}
20&8&18&20&0&18&11&9&0\\
23&1&18&2&0&18&2&20&0\\
20&2&18&8&6&18&2&20&1\\\end{bmatrix}$$

When flattened into a string of characters from the cipher alphabet, this is the result:

THRT RKI WARB RBT TBRHFRBTA

I'll probably lose the will to live if I start wading through the encryption algorithm, so I'll stop here.


The difference between encrypted hash and a digital signed one is twofold:

the key to be used for signature generation is the private key, so technically it is not encryption;
the padding scheme is different for both situations.

The use of the wrong key is already enough to not talk about encryption as explained in my Q/A here.

In the case of PKCS#1 v1.5, both encryption and signature generation are often referred to by the same name. However, both use a rather different scheme for the padding of the content (the plaintext message for encryption and the hash for signature generation).  For RSA v1.5, RSA encryption is called RSAES-PKCS-v1_5 and uses the EME-PKCS1-v1_5 encoding scheme. Signature generation is called RSASSA-PKCS-v1_5 and it uses the EMSA-PKCS1-v1_5 encoding method. Note that these names have only been introduced in version 2.0 from the specification.

The main issue is that the padding for encryption was designed to add a random component to the padding. This is required because otherwise identical messages would result in identical ciphertext, leaking information to anybody seeing both ciphertext. As it is random padding, it cannot be validated. On the other hand, signature generation uses a known padding which can be validated. This is important because you would want the unpadding to fail when verifying the signature in case it has been tampered with.

So using the wrong padding scheme means that the security premises of the RSA mode and padding are not valid anymore. This is one more reason why signature generation should not be thought of as encryption of a hash value. Both use the RSA problem to be secure. Practically speaking only the modular exponentiation is identical for both.


Why are cryptography algorithms not exported to certain countries?

Re: "So why limit the export?"

The laws you're talking about are generally part of the laws that control the export of weapons and of dual-use goods. Dual-use goods are things that can be used both for a military and for a civil purpose… cryptography is such a dual-use good.

In fact, the classification as dual-use good is logic when you think about the fact that cryptography was born out of military needs hundreds of years ago.

In the recent decades since World War II, many governments (including the U.S. and its NATO allies) have regulated the export of cryptography for national security considerations. The cold-war era didn't really lift paranoia and security worries of countries worldwide. As late as 1997, NSA officials in the US were concerned that the widespread use of strong encryption could void their ability to provide SIGINT (signal intelligence) regarding foreign entities… including terrorist groups operating internationally.

It's just since the development and public release of asymmetric key techniques and the Data Encryption Standard (DES) in the 1970s, and later the rise of the Internet, combined with the willingness of some to risk and resist prosecution, that eventually made the policy of regulating cryptography impossible to enforce. As a result, it was being relaxed in the late 1990s by the US. Several countries (but not all of them) followed their lead.

Yet, up till today, most countries have unpublished cryptographic protocols and algorithms in place that are considered top secret and are only known to and used by military intelligence and alike institutions.

Re: "…wouldn't the export of such compromised algorithms have helped to unravel secrets?"

From a civilian point of view, that indeed would make sense… and we would make my cipher public according to Kerckhoffs's principle. But you need to consider the question from the viewpoint of a state or country. If you use an algorithm to encrypt and decrypt Top Secret information which - according to your security classification - could endanger your state/country as soon as anyone gets his/her hands on that information, would you publish it?

After all, if you put your military crypto in the hands of the crowd, the crowd (including every adversary) might be able to find a flaw in your crypto. The crowd would most probably tell you by publishing successful attacks all over the internet, but your adversary would most certainly keep his mouth shut to be sure you're not aware he/she is reading everything you've encrypted.

Remember WW2, where the UK could read Enigma messages from a certain point on. They didn't tell the Germans about that for a good reason. Today, a state/country that is able to successfully attack and decrypt another state's/country's crypto would not tell anyone either.

The reasons are simple:

it is an "attack" and therefore it could cause diplomatic issues (up to a war).
the attacking state would lose the advantage of being able to read the attacked state's/country's message without them knowing about it.

No state/country will ever risk a war or risk losing a strategic advantage. And on the other side of the coin, no state/country will ever risk losing the secrecy of it's most valuable, top secret information.

If you dive a bit into the history of diplomacy, secrecy and war, you'll soon discover that states/countries always consider ignoring Kerckhoffs's principle a small price to be paid when it adds another layer of security (through obscurity).

The reason is that — from a military point of view — every layer of security (no matter how small) adds security. Sometimes, the smallest layer of security represents the fine line between life and death.

And for the same reasons, no other state will ever rely on another's crypto to protect it's Top Secret information. Yet, note that doesn't mean the cryptos by NSA and others don't contain backdoors or planned weaknesses in case an adversary should use that crypto. A nation will (most of the time) make sure there is a way to access encrypted information under worst case scenarios… especially when that nation defines such a scenario different than another state (or a regular civilian).


What is the importance of the $r$ and $c$ values for the Sponge Construction?

Keccak is Sponge-based hash function:

[Image taken from the official sponge page]

It has a large internal state, and iterates this with a permutation (that for theoretical proofs we model as an ideal permutation).

The total state of Keccak is $s=r+c$ bits.  Because the user can only ever read from or input data into the $r$-section of this (the 'rate component of the state'), a user cannot directly modify the capacity component of the state.  It turns out that the security of the construction boils down to avoiding internal collision on the capacity component (which is $c$-bits wide). That is, we require that the capacity component of the state never takes the same values twice and due to the birthday bound, this happens after around $2^{c/2}$ blocks.

So, for provable security, we need $c$ to be suitably large. However, the input and output is always at rate $r$.


Are there any standards of multi-prime RSA key generation?

Multi-prime RSA (also known as RSA-MP) is supported by PKCS#1v2. This standard supports a public key $(n,e)$ where the modulus $n$ is the product of $u≥2$ distinct odd primes: $n=\prod_{i=1}^u{r_i}$, with $1<e<n$ and $\gcd(r_i-1,e)=1$ (implying $e$ odd). The private exponent $d$ is such that $1<d<n$, and $e⋅d≡1\pmod{\operatorname{lcm}_{i=1}^u(r_i-1)}$. No other requirement on $(n,e,d)$ is given by PKCS#1v2. RSA-MP is $u>2$. Make $u=2$, $p=r_1$, $q=r_2$, and you are back to RSA in PKCS#1v1.

I know no standard about generation of RSA-MP key. However, for advice on the question of the bit size of $n$ and the number of factors $u$, one recommendable paper is Unbelievable Security: Matching AES security using public key systems, by Arjen K. Lenstra. See in particular the synthetic table giving $u:⌈\log_2\min(r_i)⌉$ for a given security level (in bits, with 2K3DES 95-bit), on a given year (with that parameter accounting for the author's evaluation of improvements on the algorithms, but not Moore's law), and according to two models.

Corrected: Following that size advice even at the 2K3DES level (for any entry starting Y2010), adding about $32/u$ bits per year to account for Moore's law (previously forgot that!), and choosing primes of one key randomly, my opinion is there's no need to worry about factorization attacks on that key till the Y2030 limit of that table. Notice that my endorsement assume that an adversary has no significant interest in factoring a single random key among extremely many.

I also like the short and graphical Multi-prime RSA trade offs, although it is restricted to 2048-bit modulus.

The main things to consider regarding $\log_2n$, $\log_2r_i$, and $u$, are:

$n$ should be large enough that GNFS factorization is not to fear. Considerations are just the same for regular RSA and RSA-MP, since the multiplicity $u$ of factors, or their size $\log_2r_i$, does not influence the expected run time of GNFS; only $\log_2n$ matters.
Each $r_i$ should be large enough that $n$ is safe from factorization by known algorithms primarily influenced by the size of a factor extracted (rather than the size of the composite to factor), in particular ECM (among such algorithms, ECM is the most likely to factor one particular key). In regular RSA, it is customary to choose the two primes of equal (or nearly equal) size: this makes it overwhelmingly likely that GNFS subsumes all other known factorization algorithms, including ECM, by a large factor. However, that does not hold for RSA-MP; and while finding one $r_i$ does not by itself make it possible to forge signatures or decipher, it must still be considered a fatal disaster, for GNFS can then tackle the factorization of the composite $n/r_i$ at greatly reduced cost. Therefore, it is customary to choose the minimum size of a factor based on estimation of the running time of ECM (considered a function of $\log_2r_i$, often ignoring the relatively marginal influence of $\log_2n$).
Then the best choice of $u$ is ${\log_2n}\over{\log_2r_i}$, rounded in some direction.

For this, I trust the aforementioned Unbelievable Security.

Details on the choice should take into account that typically $⌈\log_2n⌉$ is prescribed, in which case we'll probably use $\log_2r_i\approx ⌈\log_2n⌉/u$; if not, there is often little or no performance cost in rounding up $⌈\log_2r_i⌉$ up to the next multiple of a word size, like 32 or 64 bits, then use $log_2n\approx ⌈\log_2r_i⌉⋅u$.

It is customary that key generation standards for RSA key pairs add extra requirements in addition to those in PKCS#1v2. FIPS 186-3, a widely accepted standard, has the following requirements in section B.3.1; I'm trying my best to give the rationale:

The public exponent $e$ shall verify $2^{16}<e<2^{256}$. The lower bound is here because some attacks on poor RSA-based schemes are often easier when $e$ is small; the higher bound is for interoperability of public-key operations.
The bit size of $n$, $nlen=⌈\log_2n⌉$, should be 1024, 2048, or 3072 (note: in appendix B.3.1 of FIPS 186-3, the are references to 1024-bit, 2048-bit and 3072-bit primes; that shall be understood as the bit size of $n$, although that is composite). The limited choice maximize the critical interoperability of public keys; the lower bound also enforces a baseline security (according to NIST Special Publication 800-131A, for signature generation, 1024-bit is acceptable through 2010, deprecated from 2011 through 2013, and disallowed after 2013); the lack of 4096-bit or more is seen by some as an indication that ECDSA is the way to go.
The prime factors $p$, $q$ of $n$ shall be in range $[2^{(nlen-1)/2},2^{nlen/2}]$; this is primarily to ease interoperability of private keys across implementation.
$|p–q|>2^{nlen/2–100}$; this is a legacy of ANSI X9.31, where AFAIK it was introduced as a simple way to repel the rhetorical argument "but even Pierre de Fermat knew a factorization algorithm that could defeat RSA".
Primes $p$ and $q$ shall be chosen at random using the same algorithm (with $e$ an input), chosen among a few approved algorithms, falling into two main categories (random primes, and random primes with condition, with subdivisions depending on if the primes are probable or provable primes). This avoids poor algorithms, prevents optimizations of $d$, $dP$, $dQ$ giving questionable security, and eases validation of implementation, even allowing Known Answer Tests.
These approved algorithms are such that for $p$ of 512-bit, $p-1$ (resp. $p+1$) shall have a prime factor $p_1$ (resp. $p_2$) of more than 100 bits; same for $q$; if a similar condition is used (that's optional) for $p$ of 1024-bit (resp. 1536-bit), that should be more than 140 (resp. 170) bits. These requirements are intended to give insurance against Pollard's $p-1$ and William's $p+1$ factoring algorithm.
These approved algorithms come with a maximum size of the primes $p_1$ and $p_2$ discussed in (6.) AFAIK this just precludes choosing these primes $p_1$ and $p_2$ so big that the choice of primes $p$ is reduced to a point where this becomes an issue.

If I had to propose an adaptation of FIPS 186-3 for generating RSA-MP keys, it could be:

Unchanged (though personally I would choose $e=2^{16}+1$; and if you ask, I'd ease the lower bound to $e=3$, with no security impact when good schemes are used; but  that's independent of RSA-MP).
$nlen=⌈\log_2n⌉$ among 1024, 2048 or 3072 for full interoperability with FIPS-based signature verification devices; or changed to $1024≤nlen≤16384$ with $nlen≡0\pmod{64}$ on condition of agreement with potential signature verifiers, for more flexibility and future-openness. Recommendations on $nlen$ and $u$ based on the Unbelievable Security reference above, although with $u≤nlen/512$ no matter what.
Adapted to $2^{64⋅⌊(nlen/64+i−1)/u⌋-1/u}<r_i<2^{64⋅⌊(nlen/64+i−1)/u⌋}$. This ensures $⌈\log_2r_i⌉≡0\pmod{64}$, $⌈\log_2\prod_{i=1}^u{r_i}⌉=nlen$, and at most two different $⌈\log_2r_i⌉$.
Replaced by a test that any two $r_i$ differ in at least one of their 100 high-order bits (more in order to catch faults than for fear of Fermat factoring).
Kept for algorithms in the "random primes with condition" categories, with only the parameters of the approved algorithms adapted; see justification in (6.) below.
Kept, with the requirement that $⌈\log_2p_1⌉$ and $⌈\log_2p_2⌉$ are more than $60+5⋅⌈\log_2p⌉/64$. This linearly scales the value 100 and 140 in FIPS 186-3, and removes the option to ignore that for $⌈\log_2p⌉>1024$ by using an algorithm in the "random prime" category. My opinion is that this requirement makes sense in the context of RSA-MP: a rational adversary content with factoring any of many modulus (rather than factoring a particular modulus) should not start to use ECM on one or a few modulus; but rather should first try Pollard's p-1 on all the modulus, as the ECM strategy has a markedly lesser chance of success for a given effort (argument: Pollard's p-1 is used with great benefit by state-of-the-art factoring programs such as gmp-ecm; also see this related answer).
Kept; this really is just not changing the approved algorithms.


Is a symmetric encryption key derivable using the input and the output?

For example when I encrypt message A with key K and it outputs B, can somehow A and B be put together, so it will output K?

Except for encryption messages where you are specifically restricted to use a specifc key K only once (e.g. OTP), then no, it is infeasible to recover K from A and B.

This is a fairly fundamental requirement on encryption methods (known as "Known Plaintext"); that is, given a plaintext message and the corresponding ciphertext (or more generally, a huge number of messages and ciphertexts, all encrypted with the same key), that is still no help in decrypting another ciphertext (also encrypted with the same key) - being able to recover the key from a plaintext and ciphertext would violate this.

Actually, we put even tougher requirements on encryption methods.  We allow the attacker to pick the messages to be encrypted ("Chosen Plaintext"), and also allow the attacker to submit his own ciphertexts (and see how they are decrypted), "Chosen Ciphertext".

An encryption method is generally not considered secure unless it is secure against all these attack scenarios.


One good reason not to use RSAES-OAEP for signature is because as it stands, it can't do signature! RSAES-OAEP performs encryption of a message (of limited length) with optional label into a cryptogram, and decryption thereof. There is no way to turn some RSAES-OAEP black box into a signing machine.

OK, we could define an RSA signature scheme with a signature procedure that

hashes the message $M$ to be signed into $H$
applies OAEP padding on $H$ rather than $M$, with lHash (the hash of) some fixed constant, perhaps the 01 changed to some other non-zero byte, and as usual seed randomness as wide as the hash, and PS just enough zeroes to fill-in
applies the RSA private key function $x\to x^d\bmod N$

and the signature verification procedure matching that. I do not know that this was studied, or that we have a security reduction proving that if this signature scheme can be broken, then we can can break one of its components. I won't hazard into trying to guess in what framework such reduction could be made, and how quantitative it could be.

And why bother? The above signature scheme has no clear advantage over RSASSA-PSS, which has security reductions[*], is accepted by security authorities, and widely used. In particular, there is no grounds for fear about patents when using PSS signature, and there seldom was any (in my non-lawyer opinion and from the relative comfort of Europe on the legal uncertainty standpoint); quoting PKCS#1 v2.2 appendix D on intellectual property considerations:

  The PSS signature scheme is described in U.S. Patent 6,266,771, which expired on July 24, 2009, and U.S. Patent 7,036,014, which expired on April 25, 2010, and was held by the University of California. The PSS signature scheme is specified in IEEE P1363a-2004. Prior to the finalization of this standard, the University of California provided a letter to the IEEE P1363 working group stating that if the PSS signature scheme is included in an IEEE standard, “the University of California will, when that standard is
  adopted, FREELY license any conforming implementation of PSS as a technique for achieving a digital signature with appendix”.

[*] I vaguely recall debate about if PSS security reductions are quantitatively satisfactory for practically used modulus size and other parameters, but fail to locate a source.


Behavior of AES-CTR with 128-bit nonce and possible overflow

NIST SP 800-38A ("Recommendation for Block Cipher Modes of Operation Methods and Techniques "), Appendix B states that "The standard incrementing function takes
[x]m and returns [x+1 mod 2^m]" (my formatting, they used typesetting to show exponents).  Section B.1 goes into more detail about recommendations for the CTR mode incrementing function.

Regarding standards and compliance (which usually force portability), I couldn't really say.  And even if it was standardized to be done that way, that doesn't mean there aren't non-compliant implementations, and it doesn't mean all implementations are bug-free.

So, I guess my best answer to you is that while most implementations probably do that (wrap around like an unsigned number), and you can test it with different platforms, I don't think you can count on it, and I don't think you can scream if a vendor /changes/ this later to behave differently.  I'm not sure there is anything worded strongly enough that you can point to that would back up a complaint.

Edited to add:  The NIST document is interesting reading.  For recommendations on the incrementing function, (here I'm paraphrasing / summarizing), it basically says the incrementing function needn't necessarily increment w/ wrap, it simply must provide all 2^n unique values for an n-bit counter.  So for example, an LFSR or LCG could also be used.


Using IV buffer after altered inside a Rijndael CBC Encryption/Decryption process as IV for next message?

I assume you mean that the CBC-mode encryption and decryption process would 'update' the "output IV" will be identical to the most recent ciphertext block.  This isn't obvious from your question; for example, the diagrams you show don't show any "output IV" being generated at all.

Now, for your specific questions:

  Does this "Output IV" holds information that can have private key or plain data value inferred from?

Well, obviously not; this "output IV" is just a part of the ciphertext that (we assume) that the attacker sees already.

  Is using the IV in such a way, which can keep both sides of a Rijndael secured communication link sync data (IV) up to date without the need of sending the IV over communication (Although it is not secret), is a known and used approach?

Well, techinically yes, this approach is known and in use; for example, TLS 1.0 uses it (except they maintain separate IVs and keys in the different directions; one reason for that is so that if the two sides send messages at the same time, both encryptors don't try to update their internal states to reflect the most recent message they've seen (which would differ) at the same time - you may want to consider that).

However, there's an issue that you don't ask (but should have)

  Is there any known weaknesses that can occur because of this?

The answer to this is "Yes; if an attacker can convince one of the two sides to send a message of his choosing, he can use that ability to test the decryption of another message block".  With TLS, this is known as the BEAST attack; it would be considered wise to design your encryption system to avoid it.

In addition, I have some questions for you:

What sort of integrity protection are you designing in your protocol?  That is, if the attacker can modify an encrypted message, what advantage can he gain?  What provisions do you have in your protocol that would limit it?
More fundamentally, why are you designing your own encryption protocol?  Encryption protocols have subtle problems (for example, this BEAST attack, which is not at all obvious); is there a specific reason you have decided not to use a known good design which avoids the obvious problems?
How does the two sides get their shared secret key?  Now, this may appear to be off-topic for 'how to encrypt', however it's fraught with even more landmines than designing your own encryption protocol.


Looking For Additively Homomorphic Encryption

This probably doesn't actually qualify as leveled-homomorphic, since it doesn't extend nicely.

For integers $n$ and positive integers $m$, define $\operatorname{smod}$ ("signed mod" or "symmetric-ish mod")

by $\;\;\;\;\; (q\hspace{-0.04 in}\cdot \hspace{-0.04 in}n)+r \: \operatorname{smod} \: m \;\; = \;\; r \;\;\;\;\;$ for integers $r$ such that $\;\; -(m\hspace{.02 in}/2) < r \leq m\hspace{.02 in}/2 \;\;\;$.

(B and $m$ are  positive integers; B is a parameter, and vertical bars represent absolute value.)

The following is an encryption scheme that is significantly-additively-homomorphic over $\: \mathbb{Z}\hspace{.02 in}/m\mathbb{Z} \:$:

the secret/private key is a natural number $s$ that is coprime to $m$, and each reduction value is generated as $m \cdot e + s \cdot r$, where $e$ is a random element of {-B,-(B-1),...,B-1,B} and $r$ is a random element of a somewhat-large range of positive integers.

The decryption of a ciphertext $\:$ctext$\:$ is $\;\;($ctext $\operatorname{smod} s) \operatorname{mod} m \;\;\;$.

The secret/private key-holder can encrypt by outputting  $m \cdot e + s \cdot r + $ plaintext $ \operatorname{smod} m$, where $e$ is a random element of {-B,-(B-1),...,B-1,B} and $r$ is a random element of a somewhat-large range of positive integers.
The "noise" of such a ciphertext is at most $\:($B$\cdot \hspace{.02 in}m)+\big|$plaintext $\operatorname{smod} m\big|\;$.

Anyone with a large-enough set of reduction values can encrypt by sampling a subset $S$ of the reduction values such that $S$ does not have too many elements, choosing a non-zero integer $a_s$ for each element $s$ of $S$, and outputting
$\sum_{r\in S}s\cdot a_s+$ plaintext.
The "noise" of such a ciphertext is at most $|S|\cdot $B$ \cdot m + |$ plaintext $\operatorname{smod} m |$.

Homomorphing is done by applying the same integer linear combination to the ciphertexts as is desired on the plain texts.
The "noise"s of the resulting ciphertexts are at most $\sum_{\text{ctext}}\text{ctext}$'s noise $\cdot |\text{ctext}$'s coefficients$|$.

The reduction of a ciphertext $\text{ctext}$ by a reduction value $r$ is $\text{ctext} \operatorname{smod} r \;$.  The "noise" of such a reduced ciphertext is at most $\text{ctext}$'s noise $+$ B$\cdot m \cdot \lceil \frac{\text{ctext}}{r}-\frac{1}{2} \rceil$

As long as the upper bound on noise given by the relevant [[sentence about noise] in the previous paragraph] is less than $s/2$, decryption of the outputted ciphertext will yield the right plaintext.


Understanding the q-SDH Problem (on elliptic curves)

The goal of the problem as you've described it is to find any $x$ along with $\frac{1}{\beta + x} g_1$.

There's no real reason it's in the denominator. That's just the definition of the problem. If you believe the assumption that this problem is hard, then you believe that finding those values (where $x, \beta$ are in the denominator) is hard to compute.

As for why it's hard: we don't know that it's hard, it's just an assumption (as one comment pointed out, it's definitely not harder than the discrete log problem).


The formula at the heart of RSA is:

$$x^{\lambda(n)} = 1 \pmod n$$

where $\lambda$ is the Carmichael function. In the case of two-prime RSA it's $\operatorname{lcm} (p - 1, q-1)$.

$$m^{k \cdot \lambda(n)+1} = m \pmod n$$

We choose $d$ such that $e\cdot d = 1 \pmod {\lambda(n)}$. If $\operatorname{GCD}(e,\lambda(n)) = 1$ then there is exactly one solution in the interval $0 \leq d < \lambda(n)$ but you can construct infinitely many solutions outside this interval by adding $k \cdot \lambda(n)$.

(There are some complications when $\operatorname{GCD}(x,n)\neq 1$, which I'll ignore, since it'll still work in that case)


Recommendation for lightweight algorithm for partial message encryption

It's trivial to code your own wrapper function if you really want to use such API. Here is a Python-inspired pseudo code:

def mywrapper(data, offset, encspecs):
    subdata = data[0:offset]
    ciphertext = whatever_enc_function(subdata, encspecs)
    return ciphertext

encspecs = ...
plaintext = "...etc"
ciphertxt = mywrapper(plaintext, offset, encspecs)
cipher_plain_mixed = ciphertxt + plaintext[offset:]

But either way, it's not an algorithmic/methodology problem as much as it is an implementation.

Side note: I sense that you are about to allow for replay attacks, or other similar ones. Make sure to include a unique initialization vector (e.g. a simple counter or timestamp) that is always different, so that you never (extremely rarely) get same cipher again even when the content plaintext is repeated. This prevents an attacker from fraudulently re-sending a previously captured block of encrypted data.


Decryption of Alternating Step Generator

Stream ciphers have a key and IV to initialize. One can design the Alternating Step Generator (ASG) to have key and IV together, though, classically is has only the key ( not IV, IVs's are not secret!).
Now, let have an ASG cipher with the key $k$. When you set the key, and clock the ASG, it will output a key-stream $S$. It is up to the designer to how to use this key-stream like they can discard the first 1000 bits (Yes, it was so common to discards initial bits of a stream cipher).
Let $S_i$ be the key-stream sequence ( i.e. bits of $S$ ). Then given a plaintext $P$ with the bit sequence $P_i$ we form the $C_i$ as
$$C_i = P_i \oplus S_i$$
This is the encryption
Now, if you want to decrypt, initialize the ASG with the same key again!. It will produce the same key-stream $S_i$ since there is no randomization, it is deterministic and must be.
Now we can recover the plaintext bits as
$$C_i  \oplus S_i = (P_i \oplus S_i) \oplus S_i = P_i$$
As you can see we execute the same operation $\oplus$ for encryption and decryption. This is the beauty, simplicity, and the power of the $\oplus$

simple : no complicated operation for encryption and decryption, same circuit.
power : $\text{non-random} \oplus \text{random} = \text{random}$
beauty : (opinion based) a simple, reversible operation that can secure the messages!


Addressing some of your questions:-

  a secure implementation of a PRNG had to be blocking

A CSPRNG is the cryptographically secure version of a PRNG.  Given a good and unknown (to any attackers) seed, then the CSPRNG can run effectively for ever. ChaCha20 or something based around AES can generate oodlebytes of output.

It's a semantic distinction,but you could say that such CSPRNGs should block at initialisation. They should not output anything unless seeded correctly with adequate entropy.  And since unknown entropy is sometimes difficult to acquire, there might be a delay before the CSPRNG kicks off. Acquisition of 128 or 256 bits of unknown entropy can be lengthy for some implementations such as IoT devices without on board TRNGs.

Reseeding can be useful   however, especially in the case of a desktop computer /server.  Such devices allow other processes to execute alongside the CSPRNG. There are currently 263 running alongside my /dev/urandom device. Anyone of them could be spying on me.  Regular reseeding is an attempt to mitigate a potential compromise of the inner state of the CSPRNG.  If the RNG is running on an IoT fridge in your kitchen, such reseeding is not really necessary.

  ...how to reseed? Every minute? Every Hour?

Well this is the trick.  It will depend on your environment.  The CSPRNG Fortuna uses a horribly convoluted, variable timed reseeding and pooling mechanism. A Quantis quantum key distribution system might re-key the conventional side every few minutes. This answer gives the default reseed rate of /dev/urandom as 1 minute.  I see no reason why an IoT wine cooler has to reseed at all between power cycles. I don't think that anyone can give you a meaningful reseed period. A piece of advice might be that if you have access to some form of TRNG, you might as well capitalise on it as often as possible.

Although   consider that in cryptography rather than simulation, the exact random stream is often closely related to a key and/or IV.   Simply swapping out the CSPRNG's inner state after a protocol has been established will suddenly break the session.  The protocol will have to be re-established. This adds complexity and computational /network overhead and also applies to OpenSSL. Your session would terminate.

As for further reading, this forum of course.  There's much debate under the entropy and CSPRNG tags.


Use the genpkey command:

openssl genpkey -algorithm x25519

or, for edwards25519:

openssl genpkey -algorithm ed25519

This requires a recent OpenSSL version.


Is frequency analysis a useful tool against encryption by multiplication?

Frequency analysis would work on average quite poorly on ciphertext of the proposed cipher. How exactly depends a lot on the value of the key: for some weak keys likes 1, 3, 30, 30000.. it works essentially as well as for any mono-alphabetic cipher. For 103, it still works well. For any key, given enough (lots of) ciphertext, it could still distinguish the ciphertext from random.

Frequency analysis is NOT the right tool to attack the proposed cipher. It is much easier to find the key $k=911$ by trying small factors $k$ of $c=65147470365890912071546411$ (in ascending order) and keeping the one (or those very few) such that $c/k$ has all digits in its base-100 form in range $[1\dots26]$. That attack would not work well for a huge key purposely constructed as the product of many small factors. However, I guess refinements are possible.

An even more devastating problem occurs when a key is reused for different ciphertexts: we can compute the GCD of the ciphertexts, that will be a multiple of the key, and the key itself with few ciphertexts (sometime 2 or 3, growing only slightly with size of the parameters).

Therefore, the cipher is weak and has no practical interest.


Getting 88bytes cipher output from 48bytes input in AES

I don't think it's useful spending time on trying to understand that paper, but if you look at the screenshots and compare to their "character counts", you see that they are counting base64 characters and including the padding characters in the count.

That means "88 characters" could be one IV + three blocks of AES output (512 bits in base 64 = 85.33 + 2.67 padding).


Why use RSA-2048 for plaintext when AES-256 is much more secure?

AES is symmetric encryption.  Both sides must have the same secret key.
RSA is asymmetric encryption.  Each side has a public and private key.  You share your public key so that others can encrypt a message such that only you can read it (with your private key)

There are situations where the key exchange for AES isn't reasonable.  For those situations, we use asymmetric encryption methods like RSA.


Are asymptotic lower bounds relevant to cryptography?

Just because a lower bound has been shown does not necessarily make the problem good for crypto. For example, approximation algorithms or probabilistic algorithms could be used to break the system.

That said, I would imagine that a lower-bound could strengthen the argument for a particular system. So, it would seem that a lower bound is neither necessary nor sufficient, but would have it's benefits.


SHA1 collisions and the impact for ECDSA signatures

The problem is that, imagine you sign a message $m$ using ECDSA and SHA-1 as hash algorithm. If an attacker manages to find a message $m'$ such as SHA-1$(m)$ = SHA-1$(m')$ then the computed signature for $m$ will be valid for $m'$.

So the attacker can substitute $m$ for $m'$ while keeping the same signature value. The receiver who will try to validate the signature won't be able to tell the difference.

[UPDATE]
Let's explain it in details:

So when signing a message $m$ using ECDSA algorithm with SHA-1 hash function, according to wikipedia, it goes this way:

We compute $e =$ SHA-1$(m)$
Calculate $r = x_1\,\bmod\,n$ (where $(x_1, y_1) = k \times G$, $k$ is a random integer from $[1, n-1]$ and $n$ is the order of the elliptic curve)
Calculate $s = k^{-1}(z + r d_A)\,\bmod\,n$ (where $d_A$ is the private key signature and $z$ the $L_n$ leftmost bits of $e$)
The signature is the pair $(r,s)$

So if an attacker finds a message $m'$ as SHA-1$(m')$ = SHA-1$(m)$ then $e' =$ SHA-1$(m') = e$ and then $z' = z$.
So the signature $(r,s)$ will be valid for the message $m'$ even if the attacker doesn't know the private key $d_A$ because all computations have been done for him.

Note that in this case the attacker needs a valid signature and to find a second pre-image to forge a signature.

An interesting comment from Ilmari Karonen:

  There are practical scenarios where both $m$ and $m'$ may be
  controlled by the attacker, in which case a collision attack suffices.
  For example, the MD5 collision attack was used to forge SSL
  certificates by getting an established CA to sign an innocent-looking
  certificate, and then replacing it with another certificate with the
  same MD5 hash, but far higher privileges.