Difference between somewhat homomorphic encryption and leveled homomorphic encryption?

Let $\mathcal{C}$ be the set of allowed binary circuits.

Then, a $\mathcal{C}$-evaluation scheme $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Eval}, \mathsf{Dec})$ that has (i) correct decryption and (ii) correct evaluation is called a somewhat homomorphic encryption scheme (SHE).

A $\mathcal{C}$-evaluation scheme $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Eval}, \mathsf{Dec})$ is called a levelled homomorphic scheme if it has (i) correct decryption, (ii) correct evaluation, (iii) takes an auxiliary input $d$ to $\mathsf{Gen}$ which specifies the maximum depth of circuits that can be evaluated, (iv) is compact, and finally requires that the length of the output of $\mathsf{Eval}$ does not depend on $d$.

As you can see, levelled homorphic scheme is an "extended" form of SHE. However, if you allow any circuits with depth at most $d$ in $\mathcal{C}$, then you have a levelled fully homomorphic scheme.

If you want to go a step further, there is also $i$-hop and $\infty$-hop correctness for schemes building on top of SHE/[levelled] [fully] homomorphic schemes.

Now let's come to your questions: bounded depth for levelled homomorphic encryption as well as the difference between both should be clear now. For the degree of the polynomial $p$, maybe you were referring to compactness, since it restricts the output of $\mathsf{Eval}$ to at most $p(\lambda)$ bits, where $\lambda$ is the security parameter. I don't know your definition of strong here, therefore I leave it open to you to choose the "better one".

The following paper may help you further in your questions: A Guide to Fully Homomorphic Encryption


You would need (at least) 3 pairs of vectors in order to determine the 3*3 matrix.


/dev/urandom itself is an acceptable crypto-quality (P)RNG. Therefore it can't hurt security to call it as often as you want. Assuming that /dev/urandom operates correctly (i.e. returns bit that cannot be predicted), the probability for an observer to correctly predict the bits generated by drbgFromSeed decreases (very slowly) with the number of generated bits.

You could, in fact, read from /dev/urandom and never use a DRBG internally. There are reasons not to do that, but they aren't security:

The most common reason to avoid reading /dev/urandom too often is performance.
You may prefer to use a know PRNG internally and keep outside sources as strictly entropy injection. This would make your application portable to platforms that don't provide a usable PRNG, and you have to make do with something else (e.g. downloaded or pre-seeded entropy).
Using your own DRBG implementation (or a known good one) can help if you need to demonstrate the security of your application.
Maybe you need the determinism property at some point — but then you're better off using an explicit KDF.

What you need to be extremely careful of is never using the same DRBG state more than once. Discarding a DRBG state is fine. The DRBG state has an affine type (your syntax looks like Haskell, beware that without a monad to enforce linearity, the mistake of reusing a DRBG state is a lot more likely than in an imperative language).


From the paper, $f$ is a pseudo-random function that produces a result of $s$ bits.

You can think of the master key as a vector of $r$ values each $s$ bits long and for pedagogical purposes I'm sure the trapdoor for $w$ could be thought of as the result of hashing the concatenation of each key value $k$ with the word $w$.


Does this ECIES scheme make MAC redundant?

From the standpoint of integrity and proof of origin, signature is a superset of MAC, with the tremendous operational benefit that no secret is required for verification (drawbacks include larger size, slower generation, and typically slower verification with the possible exception of RSA/Rabin signature). Thus the poly1305 MAC in theory is redundant. From the standpoint of down-to-earth IT security (not cryptography), it may still be useful by making it harder to exploit software bugs in the code for decryption and whatever manipulates the result of decryption until signature verification.

But from the standpoint of confidentiality, a huge mistake is made: signing then enciphering without enciphering the signature! A guess of the plaintext can be checked. For example, if the plaintext is a name from the public class roll, poof goes secrecy!


It's hard to say from that out-of-context statement.  It may be that they were talking about signatures with obsolete padding schemes (such as ISO 9796-1), or possibly just raw RSA (zero padding, which is even worse); it is possible with these padding, if you observe enough signatures, you could come up with a forgery.

On the other hand, there is no known weakness if you generate RSA signatures using a modern padding scheme, either PKCS #1.5 (which, I suppose, is a bit hard to call modern) or PSS.


Is double encryption really a bad idea? Are meet-in-the-middle attacks practical at all?

meet-in-the-middle attacks rely on storing the results in a map

Only the naive version of MitM does.

The impractical memory requirement (size and accesses) of naive MitM can be greatly lowered with a relatively modest increase in other computation costs, and the calculation distributed to independent devices. The reference paper is Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, 1999). It covers MitM in section 5.3.

That's also discussed in this question.

  Is double-encryption a stupid idea

Largely so, because of MitM with such improvements. In the case of AES, using AES-256 is a much better idea than double AES-128: it foils MitM, and is faster.

  Is it true that ECC can be broken with $\mathcal{O}(\sqrt{n})$ complexity?

Yes, that's the cost of solving the Discrete Logarithm in a general cyclic group of order $n$, including defined using point addition on an Elliptic Curve. The reference method is Pollard's rho. That is seldom identified to MitM (as the question does), but there are similarities. Not coincidentally, parallel Pollard's rho is described in section 5.1 of the above paper.


One standard solution is described in the following research paper:

Robust discretization, with an application to graphical passwords.  Jean-Camille Birget and Dawei Hong and Nasir Memon.  eprint 2003/168.

That paper shows how to deal with the problem that the user's second point might be close to, but not exactly the same as, their original point.  In other words.... exactly your problem.

There might be more recent work on this problem.  You could do a literature search, starting from the above paper (e.g., looking at other papers that cite it) to see whether there are other better solutions.


cryptographically good random elliptic curves?

No, not all curves are created equal. For one thing, the number of points on an elliptic curve defined over $\mathbf{F}_p$ varies in the interval $[p+1-2\sqrt{p},p+1+2\sqrt{p}]$ (Hasse's Inequality). There are also weak instances which must be avoided, the most catastrophic being when the number of points on the curve is exactly equal to $p$ (anomalous curves) or to $p+1$ (supersingular curves).


On randomness related terminology clarification

Where would it come from, and how would you measure it? If we had $P(x_i = 0, x_i = 1) = 0.5 \pm 0.0$, that would be mathematical perfection given a large enough sample. We believe that ChaCha is a fairly decent cryptographic random number generator. Yet see the abridged ent output from a pass over a 2GB sample from /dev/urandom:-
 Arithmetic mean value of data bytes is 127.5018 (127.5 = random)

It's 0.0018 $(\approx 2^{-9})$ out from the expected value . That's because it's random. And that's expected too. And consider that we are considering infinitesimally small biases of the order of $2^{-64} - 2^{128}$. I use the 128 value in some of my designs. Bigger sample? And due to large data sets necessary (or new maths), we don't know the output biases of our current cryptographic primitives. If any, theoretically. I tried to find out, but no satisfactory answer was presented.
2.
Clearly hash functions can extract randomness as you've seen in your opening link. I've shown how to do it.
3.
There is lots of intuition, but unfortunately I have to leave that for the more mathematically capable. I just build this stuff. Others understand the basic theories. All I can do is highlight the lemma and it's usage.
It is predicated on min.entropy ($H_\infty$). And this is a measure allowing for auto-correlation in the raw input data. Since we build with it, we can set the final bias ($\epsilon$) ourselves. So it's possible to go silly with $\epsilon \approx 2^{-10,000}$ if you believe that hash functions are entirely unbiased (as per the prior linked question). But as you see, nevertheless it would still be biased. A little. Maybe.

Auto-correlation $(R)$ also has the same issues in measurement as does bias. It's a continuous statistical metric so again the user has to decide the degree before stating that it exists or doesn't. Typically $R \le 10^{-3}(physicists); p > 0.001 (NIST); p > 0.01 (RRR)$ but those  are anecdotal thresholds which influence the bias measure and $H_\infty$.
Interesting (Daniel) this also directly affects von Neumann extraction. vN is predicated on a totally uncorrelated stream, otherwise auto-correlations can propagate to the output. By virtue of the above paragraph, we can't prove when $R = 0.0$ with sufficient certainty to celebrate $\epsilon_{vN} = 0.0$.
I'm not suggesting that IID data doesn't exist. It's just that proving it with 100% certainty, rather than say 95%/$3 \sigma$ is difficult. MY ent test from above had $R = 0.000009$. But not zero.


I am a little bit confused. How are these keys reconciled?

Since this question is more or less specific to the ring signature system. I will assume you are talking about ring signatures as proposed by Rivest, Shamir and Tauman in 2001.

I took the liberty to reorder your questions a bit.

  Does knowing the public key mean knowing the owner of the private key?

Rivest et al. use standard RSA or Rabin keys, so every private key has an associated public key, just like in classical public key cryptography.

  How can a receiver know who signed the message?

They cannot know; this is the whole point of ring signatures! The only thing that the receiver learns, is that the signature was crafted by one in the ring: $\{p_1, p_2,\dots, p_n\}$. The receiver can verify that the signature was generated by one of the associated private keys, without figuring out which one it was.

  When validating the message, does the receiver try each public key one
  by one?

  If the receiver has to conduct an exhaustive search, does it mean the
  receiver knows the exact public key used to validate the signed
  message?

The receiver does not try each and every public key once; they combine all public keys in the ring to verify the integrity of the signature.

They get combined in a ring equation:

$$
C_{k,v}(y_1,y_2,\dots,y_n)=v
$$

where $y_i$ is the result of a public key operation with public key $p_i$. This equation is constructed as such, that the signer needs access to at least one private key to make it satisfied.

Let me know if you want me to go more in detail here. I got to this question while studying ring signatures myself :-)


Are EdDSA algorithms encoded by ASN.1 DER standards?

An EdDSA signature is a sequence of bytes encoded according to the EdDSA paper or its extension to more curves, or according to RFC 8032, which should be treated as opaque by callers.

In particular, for an instance of EdDSA on a curve $E$ over a field $\mathbb F_p$ of order $p < 2^{b-1}$:

A public key is a $b$-bit bit string $n \mathbin\| \underline y$ encoding a point $(x, y) \in E$, where $n$ is 1 if $x$ is ‘negative’ and 0 if not, and $\underline y$ is the little-endian encoding of the least nonnegative integer residue of $y \in \mathbb F_p$.  Here ‘negative’ means $\underline x$ is lexicographically larger than $\underline{-x}$.
A signature is a $2b$-bit string $\underline R \mathbin\| \underline s$ encoding a point $R \in E$ like a public key, and a $b$-bit integer $s$ in little-endian encoding $\underline s$.

There is no ASN.1 formatting involved here.  Forget ASN.1, and forget ECDSA.  They are evil things.


It means that the adversary can perform whatever (PPT) computation it wants based on all the information it has (namely, the corrupted party's input, the adversary's auxiliary input, and the value received from the trusted party) and output the result of that computation.


This is a common abstraction throughout theoretical crypto that is borrowed from complexity theory.  It is a formalization of the idea that an adversary is only allowed to attack a primitive (PRF, PRP, etc.) by observing its "input/output behavior."

Formally, adversaries are (often implicitly) thought of as Turing machines, circuit families, or whatever formal model of computation you like.  And when we say that an adversary is given "oracle access" to, say, $F_K(\cdot)$, we mean that it has a special state that it can enter, where it provides some $x$ and then obtains $F_K(x)$.  Note that the adversary is given complete freedom to choose the $x$: It can repeat the same $x$, query at random $x$, or choose the $x$ with some structure.

You can formalize this with Turing machines by having a special oracle tape and state that "magically" overwrites $x$ with $F_K(x)$, or with circuit families you can think of these queries as special $F_K$-gates, or if your adversary is expressed in the C programming language then it could have the ability to call a function from a library that
computes $F_K(\cdot)$.  The details of the formalization are rarely important to crypto.

Beware the subtlety where in definitions like PRF security, the adversary always "knows" the $F$ that it is attacking, due to the order of quantifiers.  In those definitions, the adversary is given input/output access to a function that is either $F_K(\cdot)$ (for a "known" $F$ but "unknown" random key $K$), or to an "unknown" random function with the same
domain and range.


In RSA, rationale for prime $p$ with $p-1$ having prime factor $u$ with $u-1$ having large prime factor?

This issue, and its history, was discussed at length in Silverman and Rivest. The relevant passage here is in Section 6, which I quote:

  In 1977 Simmons and Norris [53] discussed the following "cycling" or
  "superencryption" attack on the RSA cryptosystem: given a ciphertext
  C, consider decrypting it by repeatedly encrypting it with the same
  public key used to produce it in the first place, until the message
  appears. Thus, one looks for a fixed point of the transformation of
  the plaintext under modular exponentiation. Since the encryption
  operation effects a permutation of $\mathbb{Z}_n =  \{0,1,\ldots,n-1\}$, the message can eventually be obtained in this
  manner. Rivest [46] responds to their concern by (a) showing that the
  odds of success are minuscule if the n is the product of two
  $p^{--}$-strong primes, and (b) arguing that this attack is really a
  factoring algorithm in disguise, and should be compared with other
  factoring attacks.


ElGamal on elliptic curves attack model (CPA,CCA1,CCA2)?

In Tsiounis and Yung's proof of the IND-CPA semantic security of El Gamal, the only assumption made is that the decisional Diffie-Hellman problem is hard. The proof transfers easily to any group where the decisional Diffie-Hellman problem is hard, including we believe (non-pairing-friendly) elliptic curve groups.
Similarly all El Gamal instantiations are trivially CCA2 attackable (given a ciphertext $(rG,rA+M)$, request a decryption of (for example) $(2rG,2(rA+M))$ to recover $2M$ and hence $M$.
As far as I know the semantic security of any instance of IND-CPA secure El Gamal under CCA1 is an open problem.
On the pairing-friendly elliptic curve point, note that for such curves there is a means of checking whether a given El Gamal encryption is an encryption of a hypothetical message e.g. to check that $(P,Q)=(rG,rA+M)$ compute the pairing of $P$ and $A$ with the pairing of $G$ and $Q-M$. If the equality of the pairing holds, then so does the equality of the encryptions. This is because the decisional Diffie-Hellman problem is soluble in these groups.


This principle is commonplace, it is a key derivation from a shared secret. The academic thing to do is to use a Key Derivation Function or a MAC where hash of a concatenation is used, perhaps
$$\operatorname{HMAC-Hash}\;[\;\text{Key}=\text{(EC)DH Shared Secret},\,\text{Message}=\text{Counter}\;]$$

We call the output a derived key, and it can be a one-use key.

I would not call it a One Time Pad key, even if it is used only once to mask some payload with XOR, because the usual assumption is that a One Time Pad (key) is truly random, and this is only pseudo-random.


How to produce a ternary value (3-face "dice roll") digest from a message?

Take the output $H$ of $\operatorname{SHA-256(M)}$ or any other hash of $b$ bits. Count the number $u$ of bits set in $H$ and output $u\bmod3$. This is optimally close to unbiased in $\{0,1,2\}$, for an ideal hash and the requirement to deterministically output a value for any $M$.
Counting the number of bits set can be fast. Sometimes there's even an instruction or compiler intrinsic for that. This popcount instruction was nicknamed NSA instruction on the (unverified) rumor it was added to mainframe computers subsided by the US government to help in some form of cryptanalysis based on Hamming distance.
There are equally good alternatives. E.g.: take all 32-bit words of the hash, add them (the total can require 35 bits), then reduce modulo $3$. Or: take all words of the hash reduced modulo $3$, add the results, reduce modulo $3$.

Argument: if we take a uniformly random integer $v$ in $[0,2^b)$ and reduce it modulo $n$, we obtain as $b$ grows a nearly uniformly random number in $[0,n)$, slightly biased towards $0$. With $n=3$, and $b$ even, $0$ has probability $\frac13+\frac1{3\,2^{b-1}}$, and both $1$ and $2$ have probability $\frac13-\frac1{3\,2^b}$. This bias is undetectable for $b\ge128$, and can't be lowered.
Noticing that $2^j\bmod3$ is $1$ for even $j$, and $2$ for odd $j$, we can compute $v\bmod3$ quickly from the binary expression of $v$, by counting the even-weight bits that are set in $v$, subtracting the number of odd-weight bits that are set in $v$, and reducing modulo $3$.
We'd get the same result by complementing the $\left\lfloor\frac b2\right\rfloor$ odd-weight bits, counting all the bits set, subtracting $\left\lfloor\frac b2\right\rfloor$, and reducing modulo $3$.
In our case, the polarity of the bits in $H$ is immaterial, thus we do not need to complement the odd-weight bits, and an offset is immaterial (it only changes the slightly favored outcome), thus we can remove the final subtract. And we reached the first paragraph's method.


Concrete evidence for the asymptotics of $\lambda_1(\Lambda^\perp(A))$?

The first inequality at the bottom of page 3 of the paper is false. For example, Conway and Thompson proved the existence of "self-dual" $n$-dimensional lattices $L$ (i.e., $L^* = L$) where $\lambda_1(L) = \lambda_1(L^*) = \Omega(\sqrt{n})$, hence $\eta_{2^{-n}}(L) = O(1)$ but $\tilde{bl}(L) \geq \lambda_1(L) = \Omega(\sqrt{n})$.

The statement and proof of Conway and Thompson's result can be found as Theorem 9.5 in https://www.springer.com/us/book/9783642883323 .


Should signature verification work using two different RSA libraries?

Yes, RSA signature generation and verification should work identically on different libraries. PKCS#1 - the dominant standard for signature generation and verification - has a complete and formal description of how the configuration / input is transformed into the output.

This includes:

the key specifications (and possible encoding);
the hashing;
the padding and hash indicators;
the modular exponentiation;
the transformation into octets of the result.

There are test vectors available from NIST as well, so it is possible to (partially) verify the correctness of an implementation against well known test vectors.

That doesn't mean that there may not be differences in implementation between libraries, so some libraries:

require a key in a specific format (and error handling if the format is incorrect is not always up to par);
require CRT (Chinese Remainder Theorem) parameters for a key;
require a pre-calculated hash value, some libraries an initialized hash function and some libraries just need an indication of the hash function (and some just assume a specific hash function, often SHA-1);
offer implicit character encoding for when the input is a text string (this may also be implicit for the programming language / runtime);
allow for online calculation of the hash / signature by offering update / final functionality  or streaming;
implicitly or explicitly perform the choice of the padding mode (PKCS#1, PSS, ISO 9797, RAW, etc.);
offer to encode or even implicitly encode the result into a text string.

Less common, but still possible is the way bytes are ordered for lower level functions. You may also have to configure implementation specific parameters, such as a random number generator for protecting the implementation or performing PSS signature generation. PSS may also require parameters - a second hash function for instance - for Mask Generation Function (MGF-1).

These are all design choices that may influence the outcome of the signature generation or verification. So a developer still needs to study the API to known what to expect, despite the well written PKCS#1 standard.

Fortunately, once the algorithm works it is unlikely to fail unless you manage to bugger up the character encoding of the message or the encoding / decoding of the signature.

It seems you got stuck on (3). Double calculation of the hash is a common mistake. Note that PKCS#1 signature describes the signing of messages and includes the hashing within the signature generation description, so having the signature also generate the hash is common among cryptographic APIs.


The question's definition is OK, and must not be changed by adding "for all $k$" as considered.

The quantity $\operatorname{Pr}[E(k,m_0)=c]$ is the probability that $m_0$ encrypted by $E$ under key $k$ is $c$, where $k$ is taken as uniformly distributed over the set $K$ of possible keys. The nature of $k$ is told well enough by

  Consider a probabilistic experiment in which the random variable $k$ is uniformly distributed over $K$.

The equality $\operatorname{Pr}[E(k,m_0)=c]\,=\,\operatorname{Pr}[E(k,m_1)=c]$ is about two probabilities being equal. These probabilities are real numbers between $0$ and $1$, that are a proportion of $k$ in $K$ verifying the bracketed property. These probability are computed independently.

In other words, for finite $K$, the property tells that for any choice of $m_0$ , $m_1$ , and $c$ , there are as many $k$ in the (non-empty) set $K$ such that $E(k,m_0)=c$ , as there are $k$ in $K$ such that $E(k,m_1)=c$ .

Addition per comment: In the definition's $\operatorname{Pr}[E(k,m_0)=c]\,=\,\operatorname{Pr}[E(k,m_1)=c]$ , variable $k$ has the same meaning on both sides, but takes independent values for separate evaluation of the two probabilities over the hypothesized distribution of $k$ in $K$ . We know this because $k$ is not fixed, rather we are told $k$ has a certain distribution, hence that must be the distribution used to compute the probability. Some would write $$\operatorname{Pr}_{k\in K}[E(k,m_0)=c]\,=\,\operatorname{Pr}_{k\in K}[E(k,m_1)=c]$$
with $\operatorname{Pr}_{k\in K}[\dots]$ to be understood/read as probability for $k$ uniformly random in $K$ that $\dots$

If we changed the question's

  $\forall m_0\in M$ , $\forall m_1\in M$ , $\forall c\in C$ , $\ \operatorname{Pr}[E(k,m_0)=c]\,=\,\operatorname{Pr}[E(k,m_1)=c]$

into

  $\forall k\in K$ , $\forall m_0\in M$ , $\forall m_1\in M$ , $\forall c\in C$ , $\ \operatorname{Pr}[E(k,m_0)=c]\,=\,\operatorname{Pr}[E(k,m_1)=c]$

then the meaning would change radically. The value $k$ would be fixed (and the same on both sides of the equality) when computing the probabilities, which would be without a relevant variable. $\operatorname{Pr}[E(k,m_0)=c]$ would be either $1$ or $0$ depending on if $E(k,m_0)=c$ or not for the particular value of $(k,m_0,m_1,c)$ considered (same for $\operatorname{Pr}[E(k,m_1)=c]$ ). In the end, the whole property would mean: the choice of $m$ does not influence $E(k,m)$ for any value of $k$. If decryption is possible (and $C$ and $K$ are non-empty), this implies that the set $M$ has at most a single element, which is dull.


How would you name and/or describe this algorithm?

I don't think there is a name for this special kind of property, but it is a clear hint for polyalphabetic substitution ciphers.
It is a special kind of polyalphabetic substitution cipher. The first alphabet is a normal random key, while each successive alphabet is generated by a one-character right shift of the previous alphabet. As a result there are as many alphabets as there are characters in the plaintext (or cipher text) alphabet.


Is battery usage an important parameter for mobile based key exchange protocol?

The Kungpisdan Et al. paper you cite does make mention of battery powered devices with "low-computational capabilities" in section 2.2 "Mobile Payment – Problems and Limitations" although they do not describe exactly why they feel this is a limitation leaving the reader to infer the obvious 'the battery might go flat and make the user unhappy' or 'it's too slow'

But it seems they think it's very important as it is the whole motivation for the protocol they describe.

Modern 'smart phones' perform many many key exchanges, encryption, decryption, signing and so on all day every day. I'm not sure I see the problem.

You SHOULD NOT degrade the security of a system to save a few micro-amps of power.

Even embedded systems that are required to run for many years off a single battery sill use the best possible security. For example LoRaWAN uses authenticated AES with 128 bits keys.

Just to clarify my statement that battery conservation is "the whole motivation" for the protocol that was my opinion. They do also mention data costs and "wireless networks also have limitations on low bandwidth and poor reliability". Firstly protocols, be they security related or not, should be designed to be reliable on the principle that all networks are inherently unreliable be they on your phone or PC. So far as the cost is concerned the customer has already committed to downloading 100's of KB for the privilege of purchasing something via their smart phone so can probably sink the costs of using the existing secure payment service. The consumer is never going to know if they are using SET or SET/A+ or care.

The origional SET/A protocol was published in 1998 and at that time all of the above concerns were valid. Not so in 2015 when SET/A+ was proposed.


Why are access tokens so long in general?

One way of producing a secure token is to sample 256 bits of entropy and encode that into a usable character set (often base64). This will get you the shortest secure token. But by design, this token will be completely opaque - that is, it contains no information so that any use of it will require a lookup into a database.
There are all sorts of engineering trade-offs that you might want to make, balancing a longer token against making them easier to use or validate. For instance, you might want to augment your random token from which you can extract information about: the account id, the customer's region (for geographic sharding), expiration time, etc. These will result in longer tokens, but there is a very low cost associated with slightly longer tokens.


You missed some additional steps and your assumption to pass the username as plain text is not completely right. The whole authentication is done with HTTP headers containing binary messages as Base64.

What you see in step 3 is the negotiation message including host and NT domain in a documented format.

Next the server will respond with a message containing the “challenge” which is a random 8 Byte number. The client will add its own 8 byte random to flummox rogue servers.

To get authenticated the client has to send the encrypted challenge, knows as the response. The encryption is done using 56-bit DES with it’s MD4 hashed password as key.

The server compares the encrypted challenge with one he created the same way with the password known or passed it to a domain controller for verification.

So the password itself is never transferred.

A more detailed description see NTLM Authentication Scheme for HTTP or at MSDN.


Which attacks can be avoided by the use of OFB instead of ECB?

OFB is a mode of operation to ensure confidentiality of messages a) longer than the block size of the encryption algorithm, and b) that can be re-broadcast. The motivation for these kinds of modes it to avoid the weaknesses that come from using plain ECB mode.

To be precise, the typical attack on ECB mode involves analyzing the ciphertext and looking for repeated blocks. Repeated ciphertext blocks mean repeated plaintext blocks, and knowing about repeated plaintext can help the attacker analyze the captured ciphertext. (Meaning that ECB is not semantically secure.) In some cases, this is enough for the attacker to learn all, or almost all, of the plaintext. OFB mode prevents this from happening by using randomized encryption to ensure that repeated plaintext within the message does not cause repeated ciphertext.

OFB is resistant to ciphertext errors in that if the ciphertext has bits modified in error, only the bits of the plaintext that directly correspond to the ciphertext are modified.

Because it OFB mode works like a stream cipher, it has the typical weakness that allows known plaintext to be easily modified by an attacker. (Ie, if OFB mode produces a keystream $K$, then the ciphertext $C$ is defined as $C_i := P_i \oplus K_i$, so if $P_i$ is known to the attacker then so is $K_i$, so they can create a new ciphertext $C'_i := P'_i \oplus K_i$ where $P'_i := P_i \oplus X$ and $X$ is a value chosen to produce the desired modified plaintext $P'_i$.) But since message confidentiality (the goal of OFB) does not encompass message integrity, this is not necessarily a big deal.


So my guess is that the 32bit implementation returns different output than the 8bit implementation (the original).
  Can you correct me ? or at least explain why it is still equal ?

Of course, it's equal.  The AES function (for a specific plaintext, key) is well defined; and if you generate any other result, you're not doing AES correctly.

Of course, while processing, the implementation may decide to lay things out in a different order than what you might naively expect; as long as it generates the same final output, all is well (and, in fact, that is what they did)

  It seems that the shift rows in the 32bit implementation is shift columns instead.

No, in their implementation, they decided to lay the 4x4 matrix in memory so that a 32 bit value contains the 4 bytes in a specific row (and not a column).  That is, the matrix is 'transposed' compared to the representation you would normally expect.  This means that a 'shift row' operation involves rotate operations within the individual 32 bit values (or three of them; the top one remains unchanged), and that the 'mix columns' operation involves logical operations over all 4 32 bit row values.

They did that because doing that made things somewhat more efficient for them than the alternative ordering.  As long as they handle the plaintext->matrix, the matrix->ciphertext operations correctly, and the transpose the key schedule bytes appropriately, everything works precisely as expected.  At every point, the bytes in their transposed state are precisely the same model as the corresponding bytes in the (nontransposed) AES state.


Is my block cipher ready for the real world if it passes all AESAVS tests?

Based on my reading of that document, it looks like it only covers Rijndael (aka "AES"). Moreover, I would say that the AESAVS test the correctness of your implementation, but not the security.
From the linked document:

1 Introduction
This document specifies the procedures involved in validating implementations of the Advanced Encryption Standard (AES) algorithm in FIPS 197 : Advanced Encryption
Standard 1. ... This publication ... includes the specifications for the three categories of tests that make up the AESAVS, i.e., the Known Answer Test (KAT), the Multi-block Message Test (MMT), and the Monte Carlo Test (MCT).

So these tests will show that your implementation produces the correct output for a given input. They do not make any claim about whether your implementation is robust to timing attacks, or power analysis attacks, or really, any kind of attack.

So, as to

is it fit for purpose and real world use cases?

That depends, does your purpose include being secure (in addition to being correct)?


Are additional PGP subkeys still needed for smartcards?

Or is this measure included in the tutorial for historical reasons (as
  smartcards seem to only support storing RSA keys)?

While it is true that most (all?) OpenPGP compliant smart cards only support RSA, the likely reason for generating the keys in the tutorial was to show you how to generate keys and / or push them onto the card which is useful information in by itself.

  I don't know if, from the security point of view, there are reasons
  against putting your "master" key on a smartcard.

There's nothing technically stopping you from putting your master key on your smart card. However when you lose the card, this master key, which has all sorts of hard-worked-for trust signatures is now gone. This certainly isn't something you want to risk usually (which is why better HSMs offer a way to backup keys). So you usually generate the master key in software, store it away safely and redundantly and maybe push a copy onto the card.

  Do I really need to generate new subkeys for the smartcard?

No. While it's strongly advisable from a security standpoint to only have your keys on your card (so they're actually protected by the hardware and not by the software storage or the hardware) it is not mandatory.
Let's just assume that you have a software key shared between a mobile device and a computer. Let's further assume the mobile device is running iOS which is fairly good security-wise and the computer is running Windows 7 (which is less good security-wise). If you push your keys off the Windows PC an attacker would have to compromise your locked-down mobile device or the card which is both harder than compromising your Windows installation, so there you've gained some security.

  But even if, wouldn't it be enough to generate one second subkey for
  signing instead of two new subkeys?

The interesting property of master keys is not that they can sign (S) stuff, but rather that they can certify (C) other keys to be belonging to you which as far as I know is exclusive to the master key in a set of keys.


Is there any point to encrypting a file if it's transferred via ssh?

If you had a system like this:

\begin{equation}
  \text{you} \longleftrightarrow \text{your network} \longleftrightarrow \text{shared host} \longleftrightarrow \text{friend's network} \longleftrightarrow \text{friend}
\end{equation}

Your use of ssh defends against an eavesdropper or forger on your network.
Your friend's use of ssh—if your friend is using ssh instead of, oh, I dunno, rlogin or rcp—defends against an eavesdropper or forger on your friend's network.
The use of gpg with a password transmitted out-of-band to encrypt the file defends against an eavesdropper—but not a forger!—on the shared host.

Why no defense against a forger on the shared host?  Nobody bothered to teach OpenPGP about symmetric authenticated encryption.  You could use the scrypt(1) utility instead, which does use authenticated encryption.

How could there possibly be an eavesdropper on the shared host?  The eavesdropper might come in the form of the administrator of the VPS you're using for your shared host, who has access to the raw disk.  The eavesdropper might come in the form of an automatic backup system which persists the file much longer than you intended.

But, on a more careful reading of the first eleven words you actually wrote, I see that you actually have a system like this:

\begin{equation}
  \text{your machine} \longleftrightarrow \text{internet} \longleftrightarrow \text{friend's machine}
\end{equation}

Conceivably you might have different applications and daemons running with different privileges, and your user account on your friend's machine might be more vulnerable than your friend's user account.

But there's not much else that gpg adds beyond (a) a hedge against bugs in ssh or breakthroughs in breaking DH (like a network eavesdropper with a quantum computer) that don't apply to your out-of-band channel, and (b) a usability nightmare.


Is SHA512 less secure than SSHA512?

Hashing passwords plainly with SHA512 is indeed less secure than using SSHA512. But note that this doesn't imply that using SSHA512 is actually a good / secure method for hashing your passwords.

The reason for the inequality is simple:

$$\operatorname{SSHA512}(\text{pw},\text{salt})=\operatorname{SHA512}(\text{pw}\parallel \text{salt})\parallel \text{salt}$$

So as you can see it's a case of a single iteration of SHA-512 paired with some basic salting. Salting is a good thing as it (among other things) thwarts rainbow-tables but of course a modern GPU (like the Tesla V100 or with nearly the same speed the RTX 2080 Ti) achieves about 1.8GH/s per card. That is $1.8\cdot 10^9$ SHA512 evaluations per second and per card. Also note that for about 25 USD/hr you can rent 8 of these on AWS which gives you about 2.1 TH/USD, that is an attacker can try about $2\ 000\ 000\ 000\ 000$ password hashes for a single US-Dollar. So if the user has any even remotely weak password, it's a matter of a few USD to break it.

The more modern approach is then to use Argon2 or bcrypt instead which perform much worse on GPUs.


How do I get the equivalent strength of an ECC key?

The security level of an elliptic curve group is approximately $\log_2{0.886\sqrt{2^n}}$. You can use this to approximate the security level of a $n$-bit key, eg:

$\log_2{0.886\sqrt{2^{571}}} = 285.32537860389294$

The real computation (at least for curves over a finite field defined by a prime $p$) is $ \log_2{\sqrt{\pi/4}\sqrt{ℓ}} $, where $ℓ$ is the order (number of points) of the subgroup of points on the curve generated by the public base point. The size of $p$ determines the upper bound of $ℓ$, though it is not exactly the upper bound itself, it's generally pretty close. So for example, Curve25519 has an $ℓ$ of about $2^{252}$, so:

$ \log_2{\sqrt{\pi/4}\sqrt{2^{252}}} = 125.82537860389293 $

Our approximation based on the ECC key size gets us pretty close to this:

$\log_2{0.886\sqrt{2^{256}}} = 127.82537860389293 $

As otus notes below, Koblitz curves are slightly different.

The strength of any ECC key is bound to the strength of the underlying curve and domain parameters, and in general all the valid keypairs generated for a specific curve should have the same size/strength. There are some points that are invalid and should not be used, but your ECC implementation should handle that for you.

More info on determining the runtime of Pollard's Rho and thus the theoretical security level of various curves at SafeCurves: http://safecurves.cr.yp.to/rho.html


How to find the encoding of an RSA public key?

The first step is to check how much data we have. That gives an idea of the size of the public modulus: although it is possible to compress an RSA public modulus $N$ to less bits than its bitlength $\lceil\log_2(N-1)\rceil$, this is uncommon; and most RSA public key formats are larger than the public modulus, and only much larger for digital certificates. Here, excluding the 0x prefix (meaning hexadecimal in many computer languages), the given is 276-character uppercase hex; that probably is hex, coding 138 bytes or 1104 bits, which suggests a 1024-bit RSA public key (the next lowest common size, and also one of the lowest common size).

Next is to confirm this; guess the endianness; and locate the public modulus $N$. The data coding $N$ typically is visually random-like (here, pointing towards the end of the data blob). As a quick test we can use that the low-order bit is set; and the hypothesized bitlength (if exact, which is typical) gives us another bit set. When we have an hypothesis on the location and coding of $N$, we can check it with an often-sufficiently-selective test: the public modulus is a composite with no factor quickly found. With a factoring program that finds factors less than $b$, odds that an incorrect odd guess pass this test are less than
$$\epsilon(b)=\prod_{p\text{ prime, }2<p<b}{p-1\over p}$$
That's residual odds below 5.1% to wrongly conclude that a guessed encoding is correct if we only check for at-most-32-bit factors, and perhaps less than a percent for the program I use, gmp-ecm (todo: justify); this is often good enough (especially if we have several examples).

Our data seems to use little-endian byte ordering, transformed to hex using big-endian ordering of the two characters of each hex byte. With that convention, the last 256 characters "170D3375..85B30EE6" would be a 1024-bit (128-byte) public modulus of 0xE60EB385..75330D17, which passes the above test. No other simple ordering that I checked does.

Immediately before that is "01000100", which by the same convention decodes to 0x00010001 and would be the common public exponent $e=65537=2^{(2^4)}+1=F_4$ (the fourth Fermat number).

Immediately before that is "00040000", which by the same convention decodes to 0x00000400, and that would be 1024, the conjectured bit length of the modulus (with $e$ always on 32 bits, as in early Windows CryptoAPI, explaining why there is no length for $e$).

The "52534131" immediately before matches "RSA1" in ASCII, and that could be a format indicator.

Searching for that string, it comes that Microsoft used that as a magic number for RSA keys, followed by bitlen and pubexp on 32-bit (strongly reinforcing the credibility of the above three educated guesses) in a RSAPUBKEY:

typedef struct _RSAPUBKEY {
  DWORD magic;
  DWORD bitlen;
  DWORD pubexp;
} RSAPUBKEY;

[contributed by CodesInChaos]: The first 8 bytes are a PUBLICKEYSTRUC:

typedef struct _PUBLICKEYSTRUC {
  BYTE   bType;    // 0x06 = PUBLICKEYBLOB -- The key is a public key.
  BYTE   bVersion; // 0x02
  WORD   reserved; // 0x0000
  ALG_ID aiKeyAlg; // 0x0000a400 = CALG_RSA_KEYX -- RSA public key exchange algorithm.
} BLOBHEADER, PUBLICKEYSTRUC;

[contributed by Maarten Bodewes]: The overall structure is a PUBLICKEYBLOB:

PUBLICKEYSTRUC  publickeystruc;
RSAPUBKEY       rsapubkey;
BYTE            modulus[rsapubkey.bitlen/8];

Note: The above formula for the size of the modulus field can only be valid if bitlen is a multiple of 8; and then it is prudent and customary to use only multiples of 64, or even 128 for good measure.


Can AES be considered as Perfectly Secure?

AES is not provably secure, for the simple reason that there is no security proof for it. We suspect that AES is secure in practice, but there is no proof of that.


Is using derived keys for HKDF + AES-GCM safe

By itself, this is fine. Running a KDF with two different inputs generates uncorrelated sequences: knowing the output of HKDF(K1, L) doesn't give any information about the output of HKDF(K2, L) unless K1 = K2.

However, as a system design, this is fragile. What if one day someone decides that they need a new version of this format, and they decide to flip the last bit of key?

Given the constraint that you can only change the key input to HKDF, if key has a fixed size, I would append a suffix to key to indicate the format version. Version 0 uses an empty suffix, version 1 will use the 4-byte suffix {0x00, 0x00, 0x00, 0x01}, etc.

If there is an additional constraint that key has to remain the same size, I would run it through a KDF first. To avoid running into potential trouble with related keys, key should still only be used for a single purpose, which is as the key input to HKDF. Use a label that cannot possibly be equal to any valid value for info.

key' <- HKDF-Expand(key, "not a possible prefix of info; version 1")
(_, key1) <- HKDF-Expand(key, info)
(_, key2) <- HKDF-Expand(key', info)


Is there a way to bound linear complexity of a sequence less than its period

My question is at which $n$ should we stop computing $a_i$? Assuming the sequence is periodic with period $N$ at which n should we stop the search for the coefficients in the recurrence relation above so that the relation will be valid for all subsequent longer sequences until the full period?

If the sequence is periodic then the linear complexity of the sequence will not change after some point. Remember, an LFSR with length $L$ can produce a periodic sequence at most length $2^L-1$ if the minimal polynomial is maximal.
But the Berlakamp-Massay algorithm cannot detect the period, it must process all inputs. It works interactively such that it updates the internals if a new bit cannot match the output, i.e. there is a discrepancy. Once the period is reached it will not update the internals but the algorithm can only be modified to output the last modified internal distance.
If you know the period, you can stop the Berlakamp-Massay after processing $N$ bits. The reason can be seen as in the next extreme example. Consider the periodic sequence where in the period it has 99-zero followed by 1.
$$\overbrace{\underbrace{\texttt{000}\cdots\texttt{000}}_{99 \text{ times}}\texttt{1}}^{\text{ the preiod}}\, \underbrace{\texttt{000}\cdots\texttt{000}}_{99 \text{ times}}\texttt{1}\cdots  \underbrace{\texttt{000}\cdots\texttt{000}}_{99 \text{ times}}\texttt{1}\cdots$$
The linear complexity of this sequence is 100. Therefore you have to process all of the period to find the linear complexity of the sequence.

The definition doesn't seem to give any clear idea of computation of linear complexity. Even the Berlekamp Massey algorithm doesn't say at what $n$ less than $N$ to stop

Because it is designed to produce the LFSR that produces the given sequence, nothing more. As said before it must process all of the inputs.
If you want to find the period use period finding algorithm like Z-algorithm


How to apply encryption on sensitive data exchange?

This is the answer I can come up with after more investigation and comments above:

All boxes have a shared public/private key pair with the private key protected with a passphrase.
The software tool will have the same public key but not the private key.
The software tool also has a symmetrical key.
There is a server in a secure network that has the shared public/private keys. The server also has the symmetrical key.
When someone with the right to decrypt wants to decrypt a file using the tool they will connect to the secure network via VPN and the tool will send a request for the file to be decrypted. The request is encrypted with the symmetrical key. The server decrypts the request and then the file and re-encrypts just with the symmetrical key.
The symmetrical key can be changed every so often.
Instead of the symmetrical key we could use a second public/private key pair.


Would it be better to use HKDF or SCrypt for deriving a child key?

SCrypt is a Password Based Key Derivation Function or PBKDF. In general you don't need such a function if your input is already a key. In that case you need a Key Based Key Derivation Function - a KBKDF.

Currently the best KBKDF is probably HKDF. This can take a key (e.g. the public key), info (e.g. $i$ or the hash over $i$) and possibly a salt. As it is based on HMAC, there is little need to perform any hashing in advance (so using a specific encoding of $i$ would suffice).

For key material where the bits are fully random you may also just use HKDF-Expand (the first part of HKDF, HKDF-Extract just compresses the random bits in the key material in case they are not well distributed).


Security of AES after key expansion 4-MB with ECB and CBC

A videostream should probably not be encrypted with either ECB or CBC.

ECB is insecure for almost anything and it should not / can not be used to turn a block cipher in a secure cipher. This is clearly shown even in the Wikipedia description of the mode: find the penguin.

CBC is secure to keep data confidential. It is, however, susceptible to padding oracle attacks when not used correctly - especially in real time communication. It also doesn't allow e.g. caching of the key stream or parallel encryption, so the performance may be subpar as well. And although it does support seeking, it does require the user to retrieve the ciphertext block before the one that needs decryption.

This is why commonly CTR mode is used instead. Sometimes CTR mode is used in combination with a MAC to offer fast authentication and integrity of the ciphertext. , e.g. GCM mode. GCM mode, however, does undo some of the benefits of CTR mode.

However, probably the most common methods of wrapping a stream is to perform TLS. It does have some overhead, but at least well reviewed implementations exists. It depends if it fits your need.

The amount of tries to get to the key will always be in the neighborhood of $2^{127}$ tries for a (largely) unbroken cipher such as AES. The key is protected by the block cipher itself, rather than the mode of operation.

However, the security of the key only is only part of the security of the cipher. It is perfectly possible for a mode of operation to leak information on the plaintext even if the key is kept perfectly secure. The ECB penguin is a prime example of that. Another is CTR mode with a repeated IV, which turns the cipher into a "many-time pad".


Discrete logarithm with 2 solutions? A clarification request

The powers of $2$ modulo 11;
\begin{array}{c|rrrrrrrrrrrrrrrr}
x&  1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ \hline
2 ^x \bmod 11&  2& 4& 8& 5& 10& 9& 7& 3& 6& 1
 \end{array}
We don't need the above 10 due to the Little Fermat Theorem; for a prime $p$ and $p\not| a$ then
$$a^{p-1} \equiv 1 \pmod p$$ We can use this theorem as
$$a^x \equiv  a^{x \bmod{p-1}} \pmod p$$
Therefore your friend's power $12$ is equal to $2$; $12 \equiv 2 \pmod{10}$. In power;
$$ 2^{12} = 2^{12 \bmod{10}} = 2^2 = 4 \bmod 11.$$

A little theory;
The non-zero elements of modulus $11$ form a cyclic multiplicative group. The order of the group is given by $\varphi(p) = p-1$ where $\varphi$ is the Euler's totient function, so it has order $10$.
By the Lagrange theorem, the order of the subgroups must divide the order of the group. The converse, in general, is not true, that is for a divisor of the order of the group, there may not be a subgroup.
$2$ is a multiplicative generator, $\langle 2 \rangle = \mathbb{Z}_{11}^*$ and we can see this in the above table. Besides, $3$ is not a generator, since $\langle 3 \rangle = \{1,3,4,5,9\}$, with $1=3^5,3=3^1,4 = 3^4,5 = 3^3,9 =3^3$. As we can see, the order of $3$ is $ord(3)=5 | 10$.
What about order 2? It is generated by $\langle 10 \rangle = \{1,10\}$. The reason is $10 = -1 \bmod 11$
Note that for a prime $p$ forms a field $\mathbb{F}_{p}$ (also written as $GF(P)$) with integer addition and multiplication.


Decrypting only message product - is it possible?

What's wrong with the obvious solution:

Each party creates a public-private key pair.
The public key is the combination of all public keys.
Encryption is done in a nested fashion to all public keys.
Decryption is done sequentially by all holders of key shares.

If some special property of a symmetric sharing scheme is desired replace the last two with
3. Encryption is done by creating shares according to the symmetric scheme and encrypting each share with a different public key
4. Decryption is performed just as in whatever symmetric sharing scheme was desired

Of course the size of the public key is linear in the number of shares. This is just the obvious solution not a great one.


I just saw this question now. There is no reference implementation of the 2-party threshold ECDSA protocol since this was joint work with Unbound Tech (previously Dyadic Security), and they did the implementation. In general, I am a strong proponent of open source, and all pure academic work that I do is published with open source code (see https://github.com/cryptobiu). However, in some cases, research is carried out in collaboration with industry, and where they do the implementation it is limited by them. I believe that this is a reasonable balance.

Note that Unbound Tech does have a commercial offering using this for protecting cryptocurrencies (but at the level of enterprises, and not individual wallets).


Design properties of the Rijndael finite field?

For security of ECC, the choice of the irreducible polynomial is unimportant, because all finite fields with the same cardinal are isomorphic to each other (and the isomorphisms are easy to compute); this is why we can say "the finite field $GF(2^{163})$" even though there are many irreducible polynomials of degree $163$ over $GF(2)$. So the algebraic structure of an elliptic curve is not impacted by the actual field choice (of course, the curve is described with an equation $Y^2+XY=X^3+aX^2+b$ for two given constants $a$ and $b$, and those constants are represented with a given choice for the field; but using another field and applying the isomorphism on $a$ and $b$ yields another curve with the same structure). In practice, we use polynomials which promote implementation efficiency, i.e. polynomials with very low Hamming weight ($3$ if possible, $5$ otherwise), and where the non-zero coefficients are of the smallest possible degree (to make post-multiplication modular reduction easier).

For the Rijndael S-Box, things are not as simple. In the original Rijndael specification, there are some explanations on the design rationale, which were not copied into the final FIPS 197 standard. The S-Box is treated page 26; the use of an inverse in $GF(2^8)$ comes from a 1994 article by Nyberg, as providing good defense against differential cryptanalysis. To this inverse, Daemen and Rijmen added the so-called "affine mapping" which is meant to mask the algebraic structure of the said multiplicative inverse. All details are not given, so presumably they tried many polynomials (there are 30 irreducible polynomials of degree 8 over $GF(2)$, 16 of which being primitive) and many possible affine mappings, "measured" resistance to differential and linear cryptanalysis, and kept the best candidate.

Daemen and Rijmen published a book on the design of Rijndael (I have not read it).


What's the entropy of the output for Tiger Encryption?

Tiger is a 192-bit cryptographic message digest (hash function).

A design goal of an ideal hash function is to distribute the input entropy evenly over the message digest.

If an input string of 40 bytes with 28 bytes (224 bits) of entropy is hashed by Tiger, the resultant 192-bit string will have at most 192 bits, since the output cannot have more entropy than its size.

If the input string has 28 bits of entropy, the resultant 192-bit string will have at most 28 bits, since the output cannot have more entropy than the input.

A hash function is not encryption.


SHA1 calculation for millions of strings having common prefix

Yes, you can save effort, if the common prefix is at least one 512-bit block.

Speaking mathematically: For a padded message $m = m_1 \mathbin\| m_2 \mathbin\| \cdots \mathbin\| m_\ell$ of $\ell$ 512-bit blocks, $$\operatorname{SHA1}(m) = f(\cdots f(f(\mathit{iv}, m_1), m_2) \cdots, m_\ell),$$ where $f$ is SHA-1's internal compression function.  For example, suppose you have a pair of two-block messages $m_1 \mathbin\| m_2$ and $m_1 \mathbin\| m_2'$ with a common prefix $m_1$ and distinct suffixes $m_2$ and $m_2'$.  Then

\begin{align}
  \operatorname{SHA1}(m_1 \mathbin\| m_2) &= f(f(\mathit{iv}, m_1), m_2), \\
  \operatorname{SHA1}(m_1 \mathbin\| m_2') &= f(f(\mathit{iv}, m_1), m_2'),
\end{align}

which share the common subexpression $f(\mathit{iv}, m_1)$.  If you precompute $h_0 = f(\mathit{iv}, m_1)$, then you can more quickly compute $\operatorname{SHA1}(m_1 \mathbin\| m_2) = f(h_0, m_2)$ and $\operatorname{SHA1}(m_1 \mathbin\| m_2') = f(h_0, m_2')$.

Speaking programmatically: Most implementations of SHA-1 support an init/update/final API.  For example, to hash the string hello world with OpenSSL's API you might write:

SHA_CTX ctx;
unsigned char h[20];

SHA1_Init(&ctx);
SHA1_Update(&ctx, "hello", 5);
SHA1_Update(&ctx, " ", 1);
SHA1_Update(&ctx, "world", 5);
SHA1_Final(h, &ctx);

The state of the SHA-1 computation, including buffering to split messages into blocks, is stored in the SHA_CTX object.  In some cases, like in OpenSSL, you can copy the context in order to save any effort that had already been done to hash what you've fed into it so far:

SHA_CTX ctx, ctx0, ctx1;
unsigned char h0[20], h1[20];

SHA1_Init(&ctx);
SHA1_Update(&ctx, "Once before a console dreary, while I programmed, weak and weary", 64);

ctx0 = ctx;
SHA1_Update(&ctx0, "\nOver many a curious program which did TECO's buffer fill...", 60);
SHA1_Final(h0, &ctx0);

ctx1 = ctx;
SHA1_Update(&ctx1, "\nO vermin yak urea's pro-Grammy itched dt casbah fur fell...", 60);
SHA1_Final(h1, &ctx1);

The resulting hashes are

h0 = b2b36d39d4431b3a57b7c30630bbbde9553b50ae
h1 = 2a0dae0548307b4ef33c0f1fedd7cbad2c32d5d8


Interpreting the Hash type in a TLS ciphersuite

Does this always refer to SHA1

Yes, within TLS ciphersuites, an unadorned "SHA" means SHA-1.  The oldest of these ciphersuite names predate any of the SHA2 hashes (and so if they use them, they'll explicitly list the size, e.g. SHA256), and SHA-0 is never used.

From the Glossary (appendix B) in RFC 5248: TLS 1.2:

  SHA

  The Secure Hash Algorithm [SHS] is defined in FIPS PUB 180-2.  It
        produces a 20-byte output.  Note that all references to SHA
        (without a numerical suffix) actually use the modified SHA-1
        algorithm


It should be proven in any presentation of RSA that, with a correct public modulus $N$, public exponent $e$ and private exponent $d$, all integers $m \in \{0,1,\dots,N-1\}$ satisfy
$$\left(m^e\bmod N\right)^d\bmod N = m.$$
So it is only possible for a number to "not encrypt or decrypt correctly" when it is not in $\{0,1,\dots,N-1\}$. Moreover, this necessary condition is obviously also sufficient, because the result of a $\bmod N$ operation will be in this set, so if $m$ is outside it, it can't possibly equal the result of the above computation.


It is a permutation not in the sense that it permutes the bit positions of the given input, but in the sense that it is a one-to-one correspondence from a set (of bitstrings) to the same set, as defined in that paper:

2. Terminology …
Let $F^n$ be the set of all ${2^n}^{2^n}$ functions mapping
$\{0,1\}^n$ into $\{0,1\}^n$… Let $P^n\subset F^n$ be the set of such
functions that are permutations, i.e., they are 1-1 onto functions.


How RSA is implemented by authentication protocols?

Sender encrypts the message with private key and sends his/her public key and the receiver decrypts by using sender's public key and vice versa.

No, you cannot encrypt (for confidentiality) using a private key; anybody with the public key can decrypt after all.

  Now how this is RSA or AES? Because the message should be encrypted by receiver's public key so that receiver can only decrypt it.

What you are looking for is signature generation, which is different from encryption. For RSA it uses a cryptographic hash and different padding mechanisms. The "only" thing that is similar is that it uses modular exponentiation. Both encryption and signature generation depends on the RSA problem for security, and the RSA primitive is nothing but modular exponentiation (after a rather complex key pair generation).

The unfortunate thing is that because encryption and signature generation is so similar, the authors of PKCS#1 called it "encryption of the hash value using the private key". They somewhat rectified that mistake in v2.0 of their specification, but then it was too late.

AES doesn't take any part in signature generation. It is mainly used for encryption, including hybrid crypto-systems where RSA and AES are often combined to encrypt larger messages. It is not used or designed for hashing.

  But here sender's public key is sent and receiver could decrypt the message by that public key.

Well, if you perform modular exponentiation with the public key then you get the value that was input to the modular exponentiation with the private key. This contains the hash value (in some form). This is the base principle behind RSA signature generation and verification - the padding is just there to provide additional protection against attacks.

There is another misunderstanding here: the public key cannot just be "send", it must be trusted by the party that is doing the verification. Otherwise you may get send the wrong key, and you would perform verification of a signature that could be generated by anybody.

Establishing trust in a public key is the reason behind public key infrastructures. The certificate store in your browser is part of a PKI called PKIX as it relies on X.509 encoded certificates and the technology surrounding it. PGP's "web-of-trust" is another, less hierarchical PKI.

  If this is true, then any one in the network who can get cipher and public key can decrypt the message, because the cipher is meant to be decrypted by the same public key.

Correct, but we don't care. Because keeping the message confidential is not the goal. It is about proving that you have access to the private key so you can sign some session specific data. It needs to be session specific, otherwise an adversary can use an old signature to authenticate (a so called replay attack).


Is gfcombinefs - a filesystem for n-of-m Shamir secret sharing - fundamentally read-only?

I am the author of gfcombinefs.

Instead of sharing your actual secret, I would suggest secret-sharing an immutable, securely-random bytestring, and using that bytestring as a symmetric encryption key. That way, you can use any standard encryption mechanism to change and re-encrypt your actual secret. That's what I now do instead of using gfcombinefs - I use the gfcombine tool to reconstitute a symmetric encryption key on a ramfs, and use it to decrypt an encrypted volume. This means I have the freedom to change the secret keys that are on the encrypted volume, back up the encrypted volume, and so on without needing to re-share anything (which is very inconvenient if you have written some of the shares to external media stored in a separate location, or to paper).

  In these circumstances, I do not really understand why writing to a Shamir filesystem would fundamentally be unsupported?

Three reasons:

I didn't need it when I wrote gfcombinefs, and I didn't implement what I didn't need :-)
I haven't done the mathematics to prove whether it would be safe
I would guess (although I have no proof for this assertion) that making it safe would require having all the shares online and modifiable at the same time

Another commenter wrote:

  AFAICT, it should be safe against attackers who only get one look at the shares, but it might leak information if the attacker can observe the same n′< n shares before and after the change

You are welcome to do whatever you want with gfcombinefs (bearing in mind that it has absolutely no warranty, and I never actually did a proper release of it). However, if it was my secret being shared, I would not be comfortable with doing this until I had a security model, and a mathematical proof that the proposed scheme met the security model.

I wrote a mathematical proof that libgfshare had the properties I believed it did (https://sources.debian.net/src/libgfshare/2.0.0-2/doc/theory.tex/) before starting to use libgfshare for anything I valued. I would suggest doing the same if you use it differently.


Parallel authentication of encrypted data. What AE type to choose?

Use AES-OCB.  It is patented, but now has a free license for any non-military software use.  Unlike most other CAESAR candidates, OCB has been scrutinized for a while now, and meets all of your criteria other than 6 (assuming you have a good AES implementation).

If the patent is simply too much for you, then use a heavily scrutinized patent-free tweakable block cipher like Threefish in a patent-free mode like Tweakable Authenticated Encryption (TAE) mode.

But, as CodesInChaos points out, you should also break up the message into several pieces and authenticate each piece independently, so you don't waste all day downloading 100 Terabytes that you have to throw away because a single MAC tag at the end doesn't match.  Remember, there are other ways to attack you than just message forgery or breach of privacy - maybe a hacker would be satisfied just wasting your time.


Where can I find a description of the SHA-0 hash algorithm?

The reference on SHA(-0) is FIPS 180 (archived scan) of 1993 May 11. The standard itself is referenced on the NIST website, but that links to another scan lacking page 1 and the one before, thus foreword, abstract, explanation... There's also this text draft of 1992 January 22 (also here with less indication on origin).

The Proposal for Change of that into SHA-1 was published on 1994 July 11 and is online at the Federal Register with partially garbled text, including for the security-critical change:

  In Section 7 of [1] (page 9), the line which reads
      (b) For t=16 to 79 let Wt = Wt-3 XOR Wt-8 XOR Wt-14 XOR Wt-16.
  is to be replaced by
      (b) For t=16 to 79 let Wt = S1(Wt-3 XOR Wt-8 XOR Wt-14 XOR Wt-16).
  where S1 is a left circular shift by one bit as defined in Section
  3 of [1] (page 6), namely S1(X) = (X << 1) v (X >> 31).

Note: What's kept of the original PfC has messed-up sub/superscripts (a modern web artifact), and misses the closing parenthesis on the modified expression for Wt (possibly an omission in the original).
This is was a technical change in the design, critical for improved security, rather than a correction of a typographical error as could be understood by casual reading of the PfC. This change was introduced without rationale, and initially without ensuing changes in the test vectors. It is thus reasonable to suspect that it was intentionally sneaked quietly, with knowledge that the original was not as secure as intended against educated collision attacks.

The revised document is FIPS 180-1 of 1995 April 17, referenced on the NIST website (with a link to an external scan of the actual document).

Changing source code for SHA-1 into one for SHA(-0) is easy: just remove the one-bit rotations of a 32-bit word of the 512-bit message block. For example, in the reference implementation of RFC 6234, change

W[t] = SHA1_ROTL(1, W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]);

to

W[t] =          (   W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]);


No, Paillier is not commutative.

Your proposal for doing oblivious decryption is almost correct. Multiplication in the ciphertext domain is addition in the plaintext domain, so $E(pk, m+r) = E(pk, m) \cdot E(pk, r)$. Given $m+r$ in a finite group, Bob cannot figure out $m$ as long as $r$ is only ever used once.


For your example protocol with RSA-exchange in both directions, combining both keys to one protects against some weaknesses:

By combining the random numbers from both sides, the result is really random,
even if one of them has a weak or compromised randomness source.
If one of the private keys is compromised, in your protocol the attacker can
read all the data flowing to its owner. If we combine the random data by XOR
with the other random data to derive the session key, the resulting key is
still unknown to an attacker, and she can't read anything.

Of course, for the actual encryption (and authentication, i.e. a MAC key), you should then use not this combined master secret directly, but derive different keys for the different purposes from it. This avoids some replay attacks.


There is no difference in this context. XOR is sometimes called "carryless addition" because one bit addition mod 2 is identical to the one bit XOR operation. Multiplication is also carryless in this context.


Why do we use addition and multiplication in GMW protocol

Any efficiently computable function can be represented by a circuit containing XOR gates and AND gates - AND gates alone would not suffice (but NAND gates would). The standard practice in secure computation is to use this {XOR, AND} basis to represent functions, since evaluating a XOR is often very cheap (it only involves cheap local operations, and no communication).

In GMW, a 1-out-of-4 OT is used to evaluate the AND gates (as I said above, XOR gates only require local computation - i.e., XORing the corresponding shares). This is the standard OT, i.e., not Rabin OT: the sender has 4 messages $(m_i)_{i\leq 4}$, and the receiver with input $j \in \{1,2,3,4\}$ learns $m_j$ without learning anything else; $j$ remains hidden to the sender.

(note that such an OT can be constructed from the Rabin OT, and conversely, Rabin OT can be constructed from this standard OT - so although their functionality differ, they are essentially "equivalent" in terms of what they allow to do).


Curve25519's Y coordinate of Basepoint origin

Over the field $\mathbb Z/(2^{255} - 19)\mathbb Z$, Curve25519 is the Montgomery curve $$v^2 = u^3 + 486662 u^2 + u,$$ and edwards25519 is the twisted Edwards curve $$-x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2.$$  The curves correspond by the birational map

\begin{gather}
  x = \sqrt{-486664} \frac{u}{v}, \quad
  y = \frac{u - 1}{u + 1}; \\
  u = \frac{y + 1}{y - 1}, \quad
  v = \sqrt{-486664} \frac{u}{x}.
\end{gather}

The standard base point $P$ for the X25519 Diffie–Hellman function has $u(P) = 9$; the $v$ coordinate is not significant because X25519 works exclusively with $u$ coordinates, so there are two possible points, $P = (9, \pm \sqrt{9^3 + 486662\cdot 9^2 + 9})$.  The choice of $u(P)$ is arbitrary as long as it corresponds to a point of large prime order—it can't affect security—but was made to be the smallest such integer.  The standard base point $Q$ for Ed25519 signature was chosen to correspond to one of the possible choices for $P$, so $$y(Q) = \frac{u(P) - 1}{u(P) + 1} = \frac{9 - 1}{9 + 1} = 4/5;$$ then the $x$ coordinate of $Q$ was chosen arbitrarily from the two options.


Does using a slow-hash on the output of an asymmetric key-exchange

  offer any more protection in a quantum-computing era?

No. $\:$ A quantum attacker would simply find seed even if you didn't use "a slow-hash on" it.

  Is the algorithm (greatly) diminished, or completely broken?

The algorithm will still be completely broken by quantum attacks. $\:$ Furthermore, your simplified

protocol would just have one more link (scrypt) that could potentially be broken by classical attacks.


Can multiplication of two primes be seen as a strong cipher?

This answer is supplementary to the one provided by Mikero.

Assuming that the $\operatorname{map}$ and $\operatorname{kdf}$ functions are properly randomized and provide appropriate output (e.g. large enough to be non-repeating), then no two ciphertexts will share common factors. So being able to use $\operatorname{gcd}$ to break ciphertexts is not applicable in the basic form of the proposal.

  I see this would be very similar to OTP; and can it be seen secure considering the idea is almost the same (and assuming factorization is hard)

Emphasizing the point raised by Mikero: This is not a one-time pad, as it lacks information-theoretic security.

An efficient algorithm for factoring can recover $p_1$ from $p_1 p_2$ and compute $M$ by inverting the $\operatorname{map}$ function.

An adversary that knows or can guess $M$ can recover $p_2$ from the ciphertext by computing $p_1 = \operatorname{kdf}(\text{IV}_1, M)$ and then $p_2 = \frac{p_1 p_2}{p_1}$. Since each $p_2$ is randomized, this should not help them to decrypt other ciphertexts that they do not already know the plaintext of. However, it would allow them to mount an attack on $\operatorname{kdf}$.

  Intuitively I can speculate, it might pave some way for some commutative and homomorphic properties as well...

It is conceivable that the ability to meaningfully multiply ciphertexts could be worked into the scheme. However, it would require a very clever $\operatorname{map}$ function - one which would also need to preserve the multiplication operator on it's own outputs.

The ability to add ciphertexts together appears to be barred by the requirement for each "key factor" ($p_2$) to be different. Something like $p_1 p_2 + p_3 p_4$ will not let you decrypt to $p_1 + p_3$ by dividing by $p_2$ and/or $p_4$

As for commutativity, decryption could be commutative, but encryption can't successfully be performed as such.

For decryption: $$\frac{p_1 p_2 p_3}{p_2} = p_1 p_3\\\frac{p_1 p_3}{p_3} = p_1\\\frac{p_1 p_2 p_3}{p_3} = p_1 p_2\\\frac{p_1 p_2}{p_2} = p_1$$

Clearly, the sequence of factors that you divide by has no influence on the output.

However, for encryption, let's try the Three-pass Protocol (one of the things you might want a commutative cipher for): $$c_0 = p_1 p_2\\c_1 = c_0 p_3 = p_1 p_2 p_3\\c_2 = \frac{c_1}{p_2} = \frac{p_1 p_2 p_3}{p_2} = p_1 p_3\\p^{'}_1 = \frac{c_2}{p_3} = \frac{p_1 p_3}{p_3}$$

An attacker who has seen $c_0$ and $c_1$ can compute $\operatorname{gcd}(c_0, c_1)$ to recover $p_3$. When they obtain $c_2$, they can then recover $p_1$ by dividing by $p_3$.

This demonstrates that the proposal does not provide a secure commutative cipher.


It would depend on the hash function if this is more or less secure. If the hash is broken and allows collisions then the scheme is decidedly less secure.

For instance, if you'd use MD5 for the HMAC then you'd still be secure, as HMAC(k, m) doesn't rely on collision resistance of the underlying hash function. However HMAC(k, MD5(m)) certainly does rely on it. So this latter scheme would be considered broken: an attacker can come up with m and m' that would be verified by the same HMAC if H(m) = H(m') after all.

If - on the other hand - a secure hash function is used then it should be secure. Hash functions  are often stacked on top of each other, e.g. in a Merkle tree. That's a known good application of hash functions and I don't think that there is anything wrong with that.

I don't see how length extension attacks would apply to HMAC(k, H(m)). The key is not used in the hash calculation over the message, after all.

The security strength of the combination of HMAC and hash would very likely depend mostly on the hash. For sure, if HMAC uses SHA-256 and the hash uses SHA-256 then the security provided would top at 128 bits due to the collision resistance of the hash. Generally this would not pose an issue if the hash is strong enough, so I almost forgot to mention it.

Using SHA-512 or SHA3-512 instead of a weaker hash function may make a lot of sense...


Authentication of data using XOR and a secure function

It can be.

Suppose $y_i = F_K(1 \mathbin\| i \mathbin\| x_i)$ and $t = \alpha \oplus F_K(0 \mathbin\| n)$ is the authentication tag, for some PRF $F_K$ and per-message nonce $n$.  The security of this structure is called XMACC and analyzed by Bellare, Guérin, and Rogaway, ‘XOR MACs: New Methods for Message Authentication Using Finite Pseudorandom Functions’, Proceedings of CRYPTO '95, Springer LNCS 963, 1995.

Suppose $y_i = x_i {K_0}^{i + 1}$ and $t = \alpha + K_1$ with arithmetic in $\operatorname{GF}(2^{128})$, where $K_0, K_1 \in \operatorname{GF}(2^{128})$ are uniform random, and $K_1$ is only ever used once.  This is the structure of GHASH, which is used by AES-GCM in Carter–Wegman mode with $K_0 = \operatorname{AES}_K(0)$ and $K_1 = \operatorname{AES}_K(n)$ for a per-message nonce $n$.


Is there a standard prefix random padding scheme?

I know of no standard like that and also doubt it exists.

It would have similar disadvantages as random padding at the end, which is no longer in use: subliminal channel, consumption of randomness which may be expensive. Additionally, it would require knowing the message length in advance, which is a practical limitation.


what does differential privacy (in machine learning) promise or guarantee?

Model inversion attacks are, by definition, impossible if the model generation process is $\epsilon$-differentially private for a sufficiently small $\epsilon$: differential privacy guarantees that if your original data was completely different, you would not be able to tell the difference just by looking at the model. Your data is effectively indiscernible from noise.

That said, the strength of the guarantee depends on the value of $\epsilon$, you can read a short explanation of that on this other question. If $\epsilon$ is very large, model inversion attacks might be successful in retrieving noisy or probabilistic information. I'm not aware of any attempt to experimentally verify for which parameters of $\epsilon$ it starts becoming a problem.


Can we efficiently factor if we are given a Pocklington certificate of one of the prime factors?

Can we efficiently factor n?

Sure can, at least with that formulation of Pocklington's theorem.  From the certificate, we can obtain values $a_i, p_i$ with $a_i^{p_i} - 1 \equiv 0 \pmod p$, (where $p$ is the prime factor that the certificate applies to).

So, if we compute $a_i^{p_i} - 1 \bmod n$ (where $n = pq$), we know that that is 0 modulo $p$, but is extremely unlikely to be 0 modulo $q$ (the other prime factor).  So, compute the gcd of that and $n$, and that's the factor $p$.

On the other hand, if you go to the formulation on Wikipedia, instead of the listed criteria 4, we have $a^{n-1} \equiv 1 \pmod n$.  Of course, knowing a value $a$ that meets that criteria leaks nothing, as (assuming $n$ is prime) any $a$ that's between 1 and $n-1$ will meet that criteria.

If you create a certificate based on that, then it may be possible to factor, but that would depend on how the prime was generated (e.g. if the large factor $r$ of $p$ was not that much smaller than $p$, then it is easy; if it is just slightly larger than $\sqrt{p}$, then you need to hope that $(p-1)/r$ happens to be smooth (which is unlikely).


This is a fairly clear cut mathematical distinction and not really phraseology nor semantics, especially in the sciences.

Implausible ~= Unlikely

Go back 10 years and consider the SHA-1 hash function.  Reversing this function is (was) hard and therefore very unlikely.  Today this has been kinda achieved in being able to generate collisions, but at great computational expense.  This has started us on a path where perhaps tomorrow Google might improve on the technique and allow SHA-1 reversal on mobile phone level computational power.  Or to only need the computational power of the iPhone10 when it starts selling.  This fate befell MD5.

Similarly, Ivan Verykleverkov might be working in his Moscow University dorm room today at improving Shor's Algorithm.  If the Verykleverkov Algorithm allows easy factorisation of primes on non quantum machines, RSA encryption and Blum Blum Shub random number generators become useless cryptographically overnight.

The theme here is something that is unlikely now does not preclude it (on a logical or mathematical basis) from becoming likely tomorrow.

Impossible = Impossible

Decrypting a properly applied One Time Pad (OTP) encryption is impossible.  If the pad was generated using true entropy, there is no mathematical solution to reversal.  The only solution is brute force attack leading to many possible alternative solutions.  Contextual and semiotic analysis may ween some out (as implausible) but you'll still be left with many plain texts each of equal validity.  This perfect secrecy is the OTP's draw and reason for all the related questions on this forum.

So in summary, one means the cryptography is currently secure but might be broken with future scientific advances whilst the other is mathematically proven to be secure for all time.


Why didn't people redesign the key scheduling algorithm of DES to use longer keys instead of using 3-DES?

Same as the reason of why not switching to AES (or any other 80+ key bits algorithms available at the time).

Because we want to reuse whatever "hardware" (chip design) resources available to do the blockcipher calculation, and re-designing the key schedule would prevent us from doing so since the existing hardware cannot compute the new key schedule.


Is predictable ciphertext/plaintext bad?

Yes, if your ciphertext is repetitive, that's bad.

We can't really say how bad, since you haven't told us enough about your cryptosystem.  It could be because you're using AES in ECB mode, which is kind of bad.  Or it could be e.g. because you're using AES in CTR mode with a fixed IV, which would be worse.  Or, in principle, you might be using a deterministic authenticated encryption mode like SIV without a nonce, which would be almost OK (although, for a chat application, even the minimal information leakage of nonce-less SIV would seem undesirable).

But, in any case, a modern semantically secure encryption scheme should never produce repetitive ciphertext, not even if the plaintext repeats.  If yours does, it's a sign that you're using AES wrong somehow.

As a corollary, as long as the encryption method you're using is resistant to chosen-plaintext attacks (which turns out to be equivalent to semantic security), it does not matter what the plaintext is or how many times it's repeated, not even if the attacker gets to choose the plaintext.

Most standard AES modes of operation (with the exception of ECB) are provably secure against chosen-plaintext attacks, as long as the AES block cipher itself is not broken and as long as they're used correctly — i.e. the IV / nonce is chosen appropriately for the mode, and never reused, and the maximum amount of data encrypted with a single key is not exceeded (not that a typical chat application is likely to come anywhere close to doing that).

(However, if an attacker can intercept and manipulate the encrypted messages (and/or inject their own fake messages into the communication), they may be able to modify the messages in transit and to carry out chosen-ciphertext attacks, which the classical non-authenticated modes of operation like CBC, CFB, OFB and CTR are not resistant to.  To protect yourself against such attacks, you either need to combine them with a message authentication code, or use an authenticated encryption mode that, in effect, has the encryption  and authentication parts combined into a single standardized bundle.)


why it should strictly be bijective instead of injective or surjective?

Actually, it is injective and it is surjective; the term bijective just means that it satisfies both the properties of injectivity and surjectivity.

Injective does not mean that there is a 'skip' (that's "not surjective"); instead, it states that no two different inputs give the same output; that is, if $a \ne b$, then $F(a) \ne F(b)$.  This follows immediately from the reversibility (invertibility) of the function; if we did have two different inputs that gave the same output, then we couldn't invert the output to get the input.

Similarly, surjective doesn't mean 'has collisions' (that's "not injective"), instead, it states that every output is possible, that is, for every $x$, there is an $a$ with $F(a)=x$.  This can be shown by noting that the size of the input and the size of the output are the same, and that they are both finite.  As each output has a unique input, then by the pigeon hole principle, every output is possible (because every input is possible).

The above conversation was about functions; now, FFX is a keyed function.  What this means is that FFX, with a fixed key, is a bijective function (because it is both injective and surjective).


Using a hash (like SHA-256) vs AES as the source for pseudo-random values in Feistel network?

A Feistel network is a way of constructing an invertible permutation from a (possibly non-invertible) function. If the function used is pseudorandom and has a large domain, then 3-4 rounds yields a pseudorandom permutation (3 rounds suffice if the adversary can only ask "compute" queries, and 4 rounds are needed if the adversary can ask "invert" queries). This is the famous Luby-Rackoff result. In the format-preserving constructions, more rounds are needed since the domain of the function can be small and this means that collisions are likely, etc.

In any case, these constructions can use ANY pseudorandom function. Thus, AES truncated to the appropriate output length is fine. HMAC is also very reasonably considered a pseudorandom function. Is plain SHA256 a pseudorandom function? Well, it depends exactly on what you do. If you compute $F_K(x) = SHA256(K || x)$ then this is certainly not pseudorandom due to extension attacks (given $F_K(x)$ it is possible to compute $F_K(x||y)$ for some $y$). However, if you know that you are only using a fixed length, or you encode that length, then it's a reasonable assumption. Personally, I prefer the HMAC assumption if you wish to base yourself on a hash function. However, I think that AES is the best choice (it's also much faster...).


Well, we start with a small definition of XOR for bit strings larger than zero bits. $x$ and $y$ are bit strings with the lenght $n$ and $x_{k}$ denoting the $k^{th}$ bit (from $0$ to $lenght - 1$). $||$ represents concatenation and $\oplus$ means XOR. So we get:
  $$  x \oplus y = ((x_{0} \oplus y_{0}) || (x_{1} \oplus y_{1}) || ... || (x_{n-1} \oplus y_{n-1})) $$
Our function $T$ just returns the first 4 bits from a 6 bit string (or an arbitrarily large bit string longer or equal to 4 bits, it doesn't really matter), so we can write it as:
  $$ T(b) = (b_{0} || b_{1} || b_{2} || b_{3}) $$

Now we want to show that $T(x \oplus y) = T(x) \oplus T(y)$

How could we do that? Maybe we could insert the different definitions of our functions and see where it goes from there..?

(That's maybe not the most optimal way to answer this question, but (I think...) it works.)


No it does not affect the parity bits.

The plaintext or ciphertext doesn't have any parity bits specified. The application key is just a input to the cipher, which is a Pseudo Random Permutation. Permutation means a 1:1 mapping from plaintext - including parity bits - to the ciphertext. If you perform the permutation in the opposite direction the plaintext - again including the parity bits - will be restored.

The same goes if the master key is used within a specific mode of operation for the block cipher; the 1:1 relationship between plaintext and ciphertext will be maintained.

Note that as the ciphertext doesn't have any parity bits, the parity of the ciphertext is completely random; the parity of the plaintext is not mirrored in the parity of the ciphertext in any way. That also means that if you perform key derivation with the master key that you need to explicitly set the parity afterwards.

Note that some libraries do not actually validate the parity bits. It's better to set them none-the-less.


Cut through mode for TLS AES-CBC / SHA ciphersuite

Am I missing something ?

Well, the first obvious question to ask, even before "can I?" is "should I?".

It would appear, from a security standpoint, doing TLS in a cut-through mode would have security issues, and so it's not clear that it should be attempted, even if you could.

Suppose you did; you implemented a way to receive a partial TLS record, and send the partial decrypted plaintext record to the receiver.

Then, what an attacker could do is send a TLS record claiming to be a 16k byte encrypted record, and then send segments containing the first 15k of ciphertext of his choosing; if won't be able to come up with a matching HMAC; he might decide not to send that at all.

Your implementation will decrypt the 15k of ciphertext and forward it along.  It'll then either receive an HMAC that doesn't match, or time out; it doesn't matter, as the receiver has received his 15k of bogus plaintext.

And, if you say "the attacker has no control over what his ciphertext will decrypt to, and so it's not that critical of an attack", well, that's wrong.  By pasting in ciphertexts from previous records, and/or flipping well chosen bits (which will garble one plaintext block, but flip the corresponding bits of another plaintext block), the attacker has quite a bit of flexibility.

This isn't a concern with TLS as it was designed, as the entire decrypted record is never forwarded to the application until the HMAC validates; you're breaking that assumption.


Can we sign and encrypt with RSA keys of both sender and receiver?

As pointed in comment

"encrypt" with sender's private key is improper terminology; the proper term is sign. I took the liberty to fix that common error in the question. If we used anything else than trapdoor-permutation-based public-key cryptography (RSA, Rabin for the most), "encrypt" with sender's private key would be plain unintelligible.
It's assumed $n_r>n_s$ so that $c_1<n_r$, which is necessary to get $\widetilde{c_1}=c_1$. Thus the technique won't "work" with 100% reliability in both directions unless we take some precaution.

Also, the issue of padding is ignored. And more broadly the security goals are not stated.
Issue 2 can be solved in a number of ways:

The best is to use separate keys for signature and encryption, with a maximum $n$ for the first applied (signature in the question) lower than the minimum for the second. That abides to the time-proven security design principle: one usage, one key. It also avoids the embarrassment of ending up with $c_2=m$ when the sender is the receiver, something an adversary might induce.
Another option is to force all $n$ to share the same bit size and many high order bits (say 512, which become a fixed public arbitrary constant). That insures $c_1<n_r$ with overwhelming probability. It does not solve the send-to-self issue.
Yet another is to require all $n$ to have the same bit size, restrict to (say) even $m$, and use $c_2\gets\min\bigl(c_1,n_s-c_1)^{e_r}\bmod n_r$. On decryption, we'll end up with either $m=\widetilde{c_2}$ or $m=n_s-\widetilde{c_2}$, and the parity of $m$ allows to determine which (wince $n_s$ is odd). That does not solve the send-to-self issue.
A small variant of the above forces $m<n_s/2$ (typically by requiring $m$ to fit into two bits less than any $n$), which also allows recovery of $m$.

On the aforementioned padding issue: both RSA encryption and signing require redundancy for security; plus encryption requires random padding (or non-guessable plaintext) in what's processed with textbook RSA encryption. That can be solved by:

pad $m$ with randomness and redundancy
sign with textbook RSA using private key $(n_s,e_s)$ [in it's instance for signature, if distinct from encryption]
encrypt with textbook RSA using public key $(n_r,e_r)$ [in it's instance for encryption].

Proper checking of the redundancy on decryption insures integrity and protects against decryption padding oracle attacks.
Encrypt-then-Sign works as well, and is used in the RSA-based authentication protocol¹ between (pan-)European Digital Tachograph and it's Smart Cards. It uses the $\min$ and even padded message trick.

¹ Designed circa the end of the 20th century, I wish I knew exactly by who. A modern variant would use RSAES-OAEP padding and the $m<n/2$ trick, or best separate encryption and signature keys. It would also use public moduli much larger than 1024-bit, but I was instrumental in not increasing that value (see this) late in the project and causing yet another launch delay. I don't regret that bet: roads would have been rather less than more safe from drivers lacking sleep or over-speeding if Europe had waited 2048-bit RSA gizmos to be available to enforce something better than the old recording disc. As predicted, fraud on the new system ended up focusing elsewhere: pulling the power fuse during part of a long drive (pretending the battery was disconnected to avoid vehicle theft or fire risk to explain the record of that incident), using a magnet on the motion sensor (as an alternate way to stop recording while driving), unscrewing the real motion sensor and stimulating it artificially (to lower the recorded speed), somewhat getting the calibration factors off (to the same effect), drivers getting hold of two cards (doubling their driving allowance), plain not introducing their card, or purposely using old trucks (without the new Digital Tachograph mandated).


Polynomial division hardware implementation

The method you describe is called the "pencil and paper algorithm" and is well described in Knuth's Book, Semi-Numerical Algorithm II.

In fact the number of steps can be easily determined by the size of operands. If Dividend D, is m-bit and Divisor d, is n-bit, then the Quotient q, will be (m-n+1)-bit, and the remainder in case of binary division will be at most (n-1)-bit.

Under these conditions, the algorithm il like that follow:

Shift the divisor (m-n)-bit left (this is called Normalization step by Knuth), We use some registers to be initiated by the operand
Reg_D <-- D: init with D, used as an Accumulator,
Reg_d <-- d: init with divisor $2^{m-n}$d; remains unchanged during all the process iteration,
Reg_q <-- 0: init with Operand 0,

for k from (m-n) DownTo 0, Do:
   - Reg_q <-- 2.Reg_q;  //Shift Reg_q 1-bit Left (or equivalently q = 2.q)
   - Reg_D = Reg_D XOR Reg_d;   //... XORing(Reg_D, Reg_d):
   - q_k=MSB(Reg_D); //Get the bit which represent the partial bit of quotient.
   - Reg_q = Reg_q + q_k; //... Inject bit q_k in Reg_q, or
   - if( !k)
           Reg_D = 2.Reg_D;  //... Shift  1-bit Left D excepted for last step!
End For;

NB: Observe:

The Remainder is contained in  Reg_D,
To obtain the quotient, Complement the content of Reg_q.

To optimise the process, in case of multiple division with the same divisor you can try two methods described by Knuth:

Normalization of the Divisor,
Precomputation tables.

Good Luck for your project.


Authenticated and encrypted radio communications (Non-Internet or TCP/IP)

Public-key cryptography has only one advantage in the topology of the question (central server): it allows initial setup across a channel assumed secure from an integrity standpoint only (rather than also confidentiality). But public-key cryptography comes with complexity and performance issues; assuming ability to securely inject a secret key in slave devices, and the slave devices tailored to a single central server, plain old secret-key cryptography seems a good choice.

That would be with a master secret key in the central server, with each slave device assigned an ID and a "diversified" secret key derived from the master secret key and device ID, using some Key Derivation Function (HMAC will do nicely). These long-term keys can then be used to derive session keys, much like long-term public/private key pairs are used to derive session keys. Upon initiating communication with a device giving its ID, the central server can quickly find the slave device's secret key, by applying the KDF.


Can it be proven that my home-brewed hash function is not LESS secure than a known good hash function it leverages?

Yes, standard reduction proofs usually do the trick.

Reductions proofs usually work this way: Assume you can break property X of the new primitive, show how this capability (when used as black-box oracle) can be used to break property Y (with X=Y being allowed) on the old / standard primitive. Because property Y holds for the old primitive, you know also know property X holds for the new one by contraposition.

Concretely, you usually want at least collision resistance and preimage resistance.

So let's do an example with collision resistance:
Let $g(x)=f(x)\parallel h(x)$ with $f,g$ being collision resistant. We want to show that $g$ is collision resistant. Assume we have a collision on $g$, that is we know $x\neq x'$ such that $g(x)=g(x')$. Now by construction this means that $f(x)\parallel h(x)=f(x')\parallel h(x')$. Assuming $f$ has a fixed output length (as is usual with hashes), this means that $f(x)=f(x')$ needs to hold, but because we assumed $f$ to be collision resistant, this is clearly impossible and thus $g$ is collision resistant if $f$ is (actually $g$ is collision resistant if at least one of $f,h$ is, but this is about the basic principle).

As for $b(x):=g(x\parallel b_1(x))$, this is obviously collision resistant if $g$ is. Assume we knew $x\neq x'$ such that $b(x)=b(x')$, then we have $g(x\parallel b_1(x))=g(x'\parallel b_1(x'))$ but up to naming this is equivalent to saying $g(y)=g(y')$ which is a collision on $g$ if $y\neq y'$. Now because $y=x\parallel b_1(x)$ and $y'=x'\parallel b_1(x)$ with $x\neq x'$, clearly these are inequal because the leading part(s) consisting of $x$ and $x'$ are unequal. Thus we have constructed a collision on $g$ from a collision on $b$ and because $g$ is assumed to be collision resistant, this means that $b$ is as well.


Instead of sending a set of random values, send a key for a PRF

It depends very much on what you require from the random values that are sent. If they need to be random (pseudorandom) then sending the key is a problem. However, if you just need unpredictability, then this may be enough. Bottom line, there is no one answer. It depends on the protocol and requirements, and often is only apparent when doing a formal security proof.