OTT service using FPE Would it be possible to create an Over-The-Top communication utility that will encrypt voice using format preserving encryption (voice clear-text to audio encrypted stream) and send that over an existing channel (e.g. Skype/ Cellular)?

I was wondering if the FPE could be made to take such a form that the compression algorithms used in VoIP would not be able to compress and would be forced to send all the analog signal (the encrypted voice message).

As I understand the voice compression algorithms work by cutting off sounds over a certain frequency, so if the encrypted "sound" would be 100% in the "don't truncate" part of the sound spectrum the voice codec would have no way of compressing and default to send the entire thing.

The answer depends on how you would layer the encryption on top of the existing protocol.

If you implemented your own Skype client, you could deal with compression issues yourself. That might allow you to use format preserving encryption, perhaps on the compressed data stream and not the audio itself.
However, you would need to be careful – speech compression is very lossy and concentrates the few bits it uses on where they are needed. You'd need to make sure patterns of speech would not be visible as higher bitrate bursts.

If you let Skype deal with compression, you likely couldn't use format preserving encryption due to compression artifacts. Instead, you'd need to use a lower bitrate encrypted channel that gets encoded as audio, probably together with some kind of error correction.
Again, you'd need a constant bitrate to hide the encrypted information fully, so some extra buffering would likely be needed to make efficient use of what's available. If the bitrate isn't enough, you might need to use a video call as the data channel for encrypted audio.

I'm unsure if the former would be an option over cellular, if the compression is done in hardware outside your control, or if the data gets recompressed en route.

As I understand the voice compression algorithms work by cutting off sounds over a certain frequency, so if the encrypted "sound" would be 100% in the "don't truncate" part of the sound spectrum the voice codec would have no way of compressing and default to send the entire thing.

That's not an accurate picture of how (modern) speech compression works. Instead, like most other lossy compression it also quantizes the information so that it is inaccurate compared to the original, but close enough for a human. Some frequencies are weighted higher and some lower, but all essentially lose information (unless the signal is very low bandwidth). Going into more detail is off topic here, but you can start from Wikipedia if you are interested.
Could you essentially invert the compression process and push the data into forms where it's retained? Maybe. That would be a very complex way to get 1. above without implementing the actual client.


If a key is used to encrypt that same key, is the computational cost to brute force it decreased? If a key $d$ is used to encrypt a message $m$ that is identical to the key $d$, resulting in a cipher $c$

$c = \text{Encrypt}(m, d) = \text{Encrypt}(d, d)$

is the computational cost to brute force $d$ lower than if the key $d \ne m$ ?

Depends on the encryption scheme.

In the IND-CPA (or even IND-CCA) security game, the adversary is not given the secret key $d$ (obviously) and hence cannot ask for $\mathrm{Enc}(d,d)$.

In other words: an encryption scheme where $\mathrm{Enc}(d,d) = d$ for all keys $d$ can still be IND-CPA(/CCA) secure (but they'd be completely useless for your scenario).


Where can I find useful data for cryptography/coding theory? When implementing cryptographic/coding theory algorithms one need to use data like big prime numbers, numbers in $Z_n$ and their inverses, irreducible polynomials in $Z_n[x]$ and so on...

While sometimes it is easy to write a simple program to get simple examples of these it's handy to have a list with some non-trivial examples. Do you know where can I find such data?

Generating prime integers and computing things modulo integers is easy with a programming language which features support for big integers. I usually use Java: it includes java.math.BigInteger, with which one can:

generate prime integers of any length;
do all basic operations, including modular reduction (mod() method);
compute modular inverses (modInverse());
compute modular exponentiations (modPow()).

For irreducible polynomials, things are more complex: Java does not offer a generic method for testing irreducibility of polynomials (or, for that matter, anything related to polynomials). I do have my own library but it is not generally available (I implemented it for a customer). However, my friend Google points out that this library appears to be fairly complete in that area.


Non-interactive proof of value in MPC Does it exist? Specifically using Shamir secret sharing based MPC and looking for a (non-)interactive way to prove that the secret value is valid. A value is valid if it is part of a set for example $[0,1] \in \mathbb Z $ or non-negative, or at least that it is the secret key of some other value. For example if $s$ is the secret and $h=a^s \bmod p$ is the encrypted message and I distribute $s$ using secret sharing, can I prove to the receivers that the shared value is indeed the $s$ value used in $h$?

Here is the simpler method I can think of: let's assume some PKI has been setup, so that there is a known public key $\mathsf{pk}_i$ for each receiver $R_i$. Then, the share sender can simply broadcast a list $c_i = \mathsf{Enc}_{\mathsf{pk}_i}(s_i)$ to everyone, where $\mathsf{Enc}$ is some encryption scheme and the $s_i$ form the secret shares of the secret $s$. This allows each receiver $R_i$ to retrieve his share (and only his share), but also adds a public value that binds the share sender to each share - this is necessary if you want to prove anything.

Then, the share sender can use any standard NIZK proof system to prove the following NP statement:
$\{\exists (r_1, s_1, \cdots, r_n, s_n): \forall i\leq n, c_i = \mathsf{Enc}_{\mathsf{pk}_i}(s_i;r_i)  \wedge F(\mathsf{Reconstruct}(s_1, \cdots, s_n)) = 1\}$,

where $\mathsf{Reconstruct}$ is the reconstruction algorithm of the sharing scheme you are using, and $F$ is the function that checks whatever you want to check about the secret $s$ (e.g. $F$ could return 1 if and only if its input is a bit, if you want to check that $s\in \{0,1\}$).

Depending on the encryption scheme used, the secret sharing scheme used, and the function $F$, the NIZK will be more or less complex - but it is always theoretically feasible to build such a proof (under a variety of standard cryptographic assumptions) since it is an NP statement, and we have NIZK proofs for any NP statement.

If you want the NIZK to be efficient, you'll need to use algebraic and compatible schemes - typically, something like the additive variant of ElGamal for the encryption scheme, with a group of prime order $p$, and a secret sharing over $\mathbb{F}_p$. For example, proving that $n$ ElGamal ciphertexts encrypt additive shares (modulo $p$) of a bit can be done relatively efficiently with existing techniques for NIZKs (it's a relatively simple extension of a Schnorr Sigma protocol, plus the usual Fiat-Shamir heuristic - or a Groth-Sahai proof in case you don't want to rely on heuristics).


Choosing good parameter for Lenstra's elliptic curve factorization In Wikipedia, there is an article explaining Lenstra's factorization algorithm. As far as I got it, we choose some $e \in \mathbb{N}$ and a point $P$ on the curve and then calculate $eP$. While calculating, we must invert elements, and if that does not work, we are rewarded with a factorization.

So far, so good. Now, Wikipedia (and some other books) suggest that $e=B!$ for some small $B \in \mathbb{N}$. Can someone please explain why this is so good? Also, why is there a relation in the choice of $B$ to Pollard's $p-1$ algorithm?

It becomes clear once you understand what $p-1$ and ECM are doing. I'll start with $p-1$, since it is simpler.

Suppose the number you want to factor, $n$, is the product of two primes: $p$ and $q$. If we knew $p-1$, we could get $p$ from $n$ by doing

$$
\gcd(a^{p-1} - 1 \bmod n, n) = p.
$$

This works because by working modulo $n$, we're working "in parallel" modulo $p$ and modulo $q$. And modulo $p$, we get $a^{p-1} - 1 = 0 \bmod p$ (for nonzero $a$) by Fermat's little theorem. So $a^{p-1} - 1 \bmod n$ is going to be 0 modulo $p$, but not modulo $q$, and the $\gcd$ gives us a factorization of $n$.

However, we don't really know $p-1$ — if we did, we wouldn't be looking for $p$ — and that puts a dent in our plans. There is an alternative route, however: if we can find a multiple of $p-1$, that works too:
$$
a^{k(p-1)} - 1 \bmod p \equiv (a^{p-1})^k - 1 \bmod p \equiv 1^k - 1 \bmod p = 0 \bmod p.
$$

So what Pollard's $p-1$ does is select an exponent that is likely to contain every single factor of $p-1$. An easy way to do this, that works as long as $p-1$ only has small-ish factors, is simply to make the exponent the product of all primes: $2\cdot3\cdot5\cdot7\ldots\cdot B_1$, where $B_1$ is our upper bound. This, however, misses power-of-prime factors, such as $2^2$ or $3^5$. So another exponent that catches everything is the factorial of $B_1$: that one is certain to catch every possible factor up to $B_1$!

Some observations about $p-1$ leads us to ECM. $p-1$ is the order of the group formed by the integers modulo $p$, denoted by $\mathbb{F}_p$. Further, if the order of $\mathbb{F}_p$ only has small factors, we can find $p$ by the aforementioned exponentiation. It turns out this generalizes to other mathematical groups. In particular, the group of points in an elliptic curve modulo $p$ is parameterized by two additional numbers $a$ and $b$:

$$
E_{a,b} = \{ (x, y) : y^2 = x^3 + a x + b \pmod{p} \}
$$

Each curve (parameterized by a and b) modulo $p$ has an order ($\#E$, analogous to $p-1$ above) in the range
$$
p + 1 - 2\sqrt{p} < \#E < p + 1 + 2\sqrt{p}.
$$
Further, for each order in that interval, there is an $(a,b)$ tuple that yields it.

Suppose we pick a random elliptic curve $E_{a,b}$, and run it modulo $n$ (again, "in parallel" in both $p$ and $q$). Picking a random point in the curve, $P$, and multiplying it by $\#E$ results in the point at infinity (the elliptic curve analogous of 0):

$$
\#E\cdot P = \infty
$$

This special point, usually represented as $(0,1)$, triggers divisions by $0 \bmod p$ but not $\bmod~q$, and that nets us a factor. The logic for picking the exponent is the same as $p-1$: every prime and prime power up to $B_1$, and hope for a hit.

Besides the factorial, another good way to pick the exponent is the lowest common multiple of every integer up to $B_1$; this yields every prime power lower than $B_1$, and is much smaller than the factorial of $B_1$.


How "Resending Message Attack" works? In the second chapter of Bruce Schneier's book Applied Cryptography, 2nd Edition, 1996, we find this in section 2.7.1 Resending the Message as a Receipt:

Consider an implementation of this protocol, with the additional feature of
confirmation messages. Whenever Bob receives a message, he returns it as a
confirmation of receipt.

1. Alice signs a message with her private key, encrypts it with Bob’s public key,
and sends it to Bob.

EB(SA(M))

2. Bob decrypts the message with his private key and verifies the signature with
Alice’s public key, thereby verifying that Alice signed the message and
recovering the message.

VA(DB(EB(SA(M)))) = M

3. Bob signs the message with his private key, encrypts it with Alice’s public
key, and sends it back to Alice.

EA(SB(M))

4. Alice decrypts the message with her private key and verifies the signature
with Bob’s public key. If the resultant message is the same one she sent to Bob,
she knows that Bob received the message accurately.

Assume that Mallory is a legitimate system user with his own public and private
key. Now, let’s watch as he reads Bob’s mail. First, he records Alice’s message to
Bob in step (1). Then, at some later time, he sends that message to Bob, claiming
that it came from him (Mallory). Bob thinks that it is a legitimate message from
Mallory, so he decrypts the message with his private key and then tries to verify
Mallory’s signature by decrypting it with Mallory’s public key. The resultant
message, which is pure gibberish, is:

EM(DB(EB(DA(M)))) = EM(DA(M)) [1]

Even so, Bob goes on with the protocol and sends Mallory a receipt:

EM(DB(EM(DA(M)))) [2]

Now, all Mallory has to do is decrypt the message with his private key, encrypt it
with Bob’s public key, decrypt it again with his private key, and encrypt it with
Alice’s public key. Voilà! Mallory has M.

The message that Mallory recorded is:
EB(SA(M))

But why the DA in formula [1] and [2]

I think if Mallory want to 'steal' the origin message M, he should do the following steps:

Mallory receive the encrypted message as a confirmation of receipt from Bob :
EM(SB(VM(DB(EB(SA(M)))))) = EM(SB(VM(SA(M)))) = X
Then Mallory have to decrypt X with his private key : DM(X) = SB(VM(SA(M))) = X1
And then verifies X1 with Bob's public key : VB(X1) = VM(SA(M)) = X2
And then encrypt X2 with his private key EM(X2) = SA(M) = X3
finally, verifies X3 with Alice's public key VA(SA(M)) = M

Can any one point out my mistake?

I think what Bruce has done is to use Sign and Decrypt interchangeably, he has done same for Validate and Encrypt. I think it is because - to sign a message - Alice uses her private key. Now in terms of encryption / decryption, a private key is used to decrypt the message and a public key is used to encrypt the message.

So instead of saying:

Vm(Db(Eb(Sa(M)))) = Vm(Sa(M))

he is saying:

Em(Db(Eb(Da(M)))) = Em(Da(M))

Which I believe is same thing on implementation level.

So OP is correct, author has used different terms without specifying they are same. This is mentioned it in the next paragraph.


How can one detect if a hash function doesn't have a full image? Suppose we have a hash function $H: \{0,1\}^* \mapsto \{0,1\}^n$, that doesn't get all the $n$ length

bitstrings as a value for any input, but is otherwise secure. Can that fact be detected?

For example, let $H$ be a secure $n$-bit hash function. You are given a black box function $F$ and told it's either $H$ or $H\hspace{-0.04 in}\circ \hspace{-0.04 in}H$, the latter of which lacks an expected ~37% ($1/e$) of the image when $n$ is large.

Can you determine which it is without knowing $H$? In a tractable time,

when $n$ is large enough for $H$ to have collision resistance?

No, you can't tell whether $H$ has a full image or not in a reasonable amount of time, if $n$ is large (say, $n\ge 160$).  Distinguishing the case where its image is of size $2^n$ vs of size $2^n-1$ would require on the order of $2^n$ evaluations of $H$, which is infeasible for normal values of $n$.

No, you can't distinguish $H$ from $H \circ H$ in a reasonable amount of time, if $n$ is large (say $n\ge 160$) and you have no information on $H$.  Distinguishing the two requires on the order of $2^{n/2}$ evaluations of the black box ($F$), which is infeasible for normal values of $n$.

The technical fine print:
I am assuming you are asking about generic attacks, i.e., black-box attacks, where we can only evaluate the function at points of our choice but are not given any information about its internal structure.
If you know the internal structure of $H$, you might be able to prove something, but this requires more than a black-box attack (more than simply evaluating $H$ on some values of your choice and looking at the output).  For instance, it is easy to distinguish $\text{SHA256}$ from $\text{SHA256} \circ \text{SHA256}$ in a single query, for trivial reasons: send the input x to your black box, and if you get back 2d7116..81, you're dealing with $\text{SHA256}$, otherwise you're dealing with $\text{SHA256} \circ \text{SHA256}$.  But this is not the kind of attack you are talking about.


Encrypting current time using 3DES as a signature I came across a peculiar system for generating "signatures" ("signatures" is within quotes because this is a bad use of 3DES) in the wild.

It works as follows: a symmetric key is generated and used to encrypt the current time using 3DES, in CBC mode with 8 zero valued bytes as an IV. The resulting signature is used like a session token - the server will decrypt the signature and check if the time is within some bound.

Is it possible to forge a signature?

Probably Not

Simplifying the discussion, one-block CBC with a null initialization vector reduces the mode to ECB.

Seeing that most time stamps are less than or equal to 8 bytes, only one block should be used (maybe two if there is a padding scheme).

There currently aren't any known algorithms for ECB forgery (as far as I'm aware), so I'd say it's unlikely.

However, this scheme could theoretically be susceptible to a brute-force attack.

If the time window were one day, the search space would only be about 48 bits (2^16 seconds being roughly one day).

Practically, this is an unrealistic attack, (and requires the server to ingest approximately 2.25 Petabytes of data), but it's feasible within an order of magnitude, which is not usually desirable.


Besides binary, decimal, hex, oct, are there encryption algorithms based on exotic/other numbering systems? We all know there is Base 10, Base 16, etc. Are there encryption algorithms out there based on different or unique Base-N numbering systems?

There's FF1 and FF3, which are Format Preserving Encryption methods that can use an arbitrary base internally.  This can be useful, for example, if you are encrypting a fixed length alphanumeric field, it would make sense to use base 36 (radix=36) or base 62 (if upper and lower cases are distinguished).


Encrypting AES cipher text with fully homomorphic encryption Suppose I run a fully homomorphic encryption scheme (FHE) on a cipher text c, generated by running AES on plain text m and get c' as the output.

What would the output be if decryption of AES is run on c'? Would the decryption of c' using AES key result in a cipher text that decrypts to m if the decryption function of the FHE was applied?

No, this won't happen. You can't change the order of operations. For that to happen, you'd have to homomorphically compute the decryption function of AES on the encrypted ciphertext c'.


Imposibility of bias-resistant coin tossing (Cleve'86) and its connection to modern notion of fairness in Secure Multiparty Computation In modern Secure Multi-party Computation (SMPC) protocols (informally) the notion of Fairness and Guaranteed Output Delivery (GOD) is defined as follows:
Fairness: If the adversary gets the output of the protocol, every honest party should get the output as well.
GOD: Honest parties should always get the output independent of adversarial behavior.
As I understand the seminal paper of Cleve'86, it proves that bias-resistant two party coin tossing protocol is not possible in honest minority setting. In particular, Cleve86 shows
that if the honest party decides to output when the adversary aborts, then there exists an
adversarial strategy where the output will not be equivalent to the output of the ideal coin tossing protocol.
What bothers me is that several paper cites Cleve86 and state that it is not possible to have fair (modern notion of fairness) protocol in 2PC. I am not able to connect Cleve86 result to current notion of fairness we talk about it Secure MPC protocols. Specifically, Cleve86 do not say anything about whether the adversary (whenever it aborts) gets any information about the output of the protocol or not.
Consider a protocol where honest party do not produce an output whenever the adversary decides to abort. Is this protocol not fair (with modern notion of fairness)? In my understanding, Cleve86 result is not applicable to this scenario.

First, I'll discuss Cleve's result really quickly, as there's a natural generalization of it which may be useful for your understanding.
Let $X\sim\mathcal{D}$ be some random variable.
A common notion in sampling random variables is rejection sampling. You have some predicate (function which returns true or false) $\phi$, and you want to sample $X\sim\mathcal{D}$ such that $\phi(X)$ holds.
This is to say that you want to sample $X\sim\mathcal{D}$ from the conditional distribution $X\sim\mathcal{D}\mid \phi(X) = \mathsf{true}$.
You can do this by continuing to sample $X\sim\mathcal{D}$ until you get one where $\phi(X)$ holds. This takes roughly $1/\Pr_{X\sim\mathcal{D}}[\phi(X) = \mathsf{true}]$ samples (so predicates that hold with low probability require "more samples", as you'd expect).
Cleve's result is just noting that an adversary can do this in an interactive protocol via aborting the computation.
Say you have an interactive protocol where each round a single person talks (you can let them broadcast things if you want), and there are $k$ rounds.
Then in the $(k-1)$th round, there's a single participant (call them $P$) who will not hear anything from other participants during the rest of protocol. They already know what their result will be.
To show that fair coinflipping is impossible, you just need to argue that $P$ can rejection-sample on their output value until it is whatever they want it to be, so they can fix the mutually-shared random variable (at the end of the computation) to be whatever they want (but the lower-probability the result they want to occur is, the more aborts they need to do).
To show that fair computation is impossible, you just need to argue that $P$ already knows their value, and via aborting the protocol can withhold relevant information from the other parties in the protocol.
So the two results (impossibility of unbiased randomness generation in interactive protocols, and impossibility of fair computations) come from slightly different arguments, but both of them rely on the existence of one person who is "done with the computation but still needs to talk to other people so they can finish the computation", which is intrinsic to interactive protocols of this form.


Is Commitment Scheme with hash function is a perfectly hiding scheme? If I use a hash function to construct the commitment scheme, can I say it is perfectly hiding?

$m$ is the message
$r$ is a random value

In commit stage,
$$ c = C(m, r)$$

In reveal stage, by revealing $r$ and verify
$$c = C(m, r)$$

Because there is $m'$ and $r'$ exist for $$C(m, r) = C(m', r')$$
So it is perfectly hiding, and it can open it both ways, so it is computationally binding.

Am I correct?

No, the proposed commitment scheme is not perfectly hiding. Depending on what you require from the hash function, it may not be hiding at all.

If you only require collision resistance (which would be the standard security property of a hash function) you cannot prove the construction even computationally hiding. This is because a collision resistant hash function may leak some limited information about its input. E.g., it might leak the first bit of its input which immediately breaks hiding.

However, the construction you're looking at is a folklore commitment scheme in the Random Oracle Model, where $C$ is modeled as a random oracle. In this case, the construction is computationally hiding, but it is not perfectly hiding.
The reason is the following: While you observation that, due to compression, there must exist some $m',r'$ such that $C(m,r)=C(m',r')$ this is not sufficient.

Perfect hiding would require that for any $m'$ there exists an $r'$, such that $C(m,r)=C(m',r')$. And this is generally not the case (and indeed unlikely) for a random function.


How does the MOV attack work? What exactly is the MOV attack, how does it actually work, and what is it used for?

It's explained briefly here and I'd like to know what it is more / what is it fully used for.

Most cryptosystems based on elliptic curves can be broken if you can solve the discrete logarithm problem, that is, given the point $P$ and $rP$, find the integer $r$.

The MOV attack uses a bilinear pairing, which (roughly speaking) is a function $e$ that maps two points in an elliptic curve $E(\mathbb{F}_q)$ to a element in the finite field $\mathbb{F}_{q^k}$, where $k$ is the embedding degree associated with the curve. The bilinearity means that $e(rP,sQ) = e(P,Q)^{rs}$ for points $P, Q$. Therefore, if you want to compute the discrete logarithm of $rP$, you can instead compute $u = e(P,Q)$ and $v = e(rP,Q)$ for any $Q$. Due to bilinearity, we have that $v = e(P,Q)^r = u^r$. Now you can solve the discrete logarithm in $\mathbb{F}_{q^k}$ (given $u^r$ and $u$, find $r$) in order to solve the discrete logarithm in the elliptic curve!

Usually, the embedding degree $k$ is very large (the same size as $q$), therefore transfering the discrete logarithm to $\mathbb{F}_{q^k}$ won't help you. But for some curves the embedding degree is small enough (specially supersingular curves, where $k <= 6$), and this enables the MOV attack. For example, a curve with a 256-bit $q$ usually offers 128 bits of security (i.e. can be attacked using $2^{128}$ steps); but if it has an embedding degree $2$, then we can map the discrete logarithm to the field $\mathbb{F}_{q^2}$ which offers only 60 bits of security.

In practice the attack can be simply avoided by not using curves with small embedding degree; standardized curves are safe. Since pairings also have many constructive applications, it is possible to carefully choose curves where the cost of attacking the elliptic curve itself or the mapped finite field is the same.


Why is asymmetric cryptography bad for huge data? I've been told that asymmetric cryptography requires that the message to be encrypted be smaller than its key length.
Why is this?

I know about hybrid encryption, which uses symmetric encryption to resolve this problem.
But I still want to know why public-key cryptography needs the data to be shorter than the key length.

There are two main reasons why asymmetric cryptography is practically never used to directly encrypt significant amount of data:

1) Size of cryptogram: symmetric encryption does not increase the size of the cryptogram (asymptotically), but asymmetric encryption does. If we take the example of RSAES-OAEP in PKCS#1v2 with a 1024-bit key and 160-bit SHA-1 hash, a 1024-bit cryptogram can convey a maximum of 688 bit of useful information. Thus data enciphered in this way would cost 49% more space to store, or more time to move over a given link.

2) Performance: on a modern CPU with hardware AES support, encryption or decryption speed is over 2000 megabyte/second (per core); while decryption of a 1024-bit cryptogram in the above scheme can perhaps run at 4000 per second (per thread of a comparable CPU), thus a throughput of 0.4 megabyte/second, 5000 times slower; that's also moreless the ratio of power usage. That ratio tends to get even worse as security increases. While there are more efficient schemes, it is safe to say that a symmetric scheme is orders of magnitude faster and less power hungry than an asymmetric one, at least for decryption (some asymmetric schemes, including RSA with low public exponent, are considerably faster on the encryption side than they are on the decryption side, and can approach the throughput of some symmetric cryptography).

Addition: Asymmetric Cryptography does not "need data smaller than its key length". For example, the public key in an RSA scheme can be reduced to about half the cryptogram / modulus size by fixing high-order bits of the modulus $n$, and setting $e$ to a fixed value, thus can have a cryptogram nearly double the public key size. The private key can be compressed even further, ultimately to the seed of a PRNG.

BUT...  In practical terms, we needn't use these tricks to make the data look smaller than the key size.  This is because it is simple to use hybrid encryption; we pick a random Symmetric key, encrypt that key with the public key, and then use the Symmetric key to encrypt the data.  With this approach, we can handle an arbitrary sized data using any public key encryption method.

However, any public-key encryption schemes is bound to increase the size of the data that it enciphers: if it did not, there would be a single ciphertext for any given plaintext, and thus an adversary could test if the plaintext is a certain value, simply by enciphering that value (using the public key) and comparing to the ciphertext. Public-key encryption schemes typically increase the cryptogram size by $k$ bits to resist such attack with a strength of $2^k$ encryptions.


In Paillier homomorphic encryption, do we need to take modulo after multiplication of 2 ciphertexts? The multiplication of 2 ciphertexts generated using Paillier encryption will result in encryption of sum of corresponding plaintexts. I need to do a linear combination operation of N integers in Paillier encrypted domain. Then after multiplying every 2 ciphertexts, do I have to take mod with respect to n^2.
OR
Is it enough to take mod after multiplying all the N ciphertexts?

Will both give the same result or not?

Yes, both will give the same result. However, taking mod after each multiplication is far more efficient: if you do not take modulos during intermediate multiplications, the size of the strings you are multiplying keeps increasing, and so does the time it takes to multiply new strings, at a very fast rate (if you multiply $n$ ciphertexts over the integers before taking the mod, you'll blow up their size by about $n$). This would be a huge unnecessary waste of computation, so you'd better take the modulo after each multiplication.


What's the ASN.1 structure of ECIES encryption result? I got a ECIES encryption result and a publickey,the publickey after decoding to ASN.1, I obtained the following:

SEQUENCE {
   SEQUENCE {
      OBJECTIDENTIFIER 1.2.840.10045.2.1 (ecPublicKey)
      SEQUENCE {
         INTEGER 0x01 (1 decimal)
         SEQUENCE {
            OBJECTIDENTIFIER 1.2.840.10045.1.1
            INTEGER 0x008542d69e4c044f18e8b92435bf6ff7de457283915c45517d722edb8b08f1dfc3
         }
         SEQUENCE {
            OCTETSTRING 787968b4fa32c3fd2417842e73bbfeff2f3c848b6831d7e0ec65228b3937e498
            OCTETSTRING 63e4c6d3b23b0c849cf84241484bfe48f61d59a5b16ba06e6e12d1da27c5249a
         }
         OCTETSTRING 04421debd61b62eab6746434ebc3cc315e32220b3badd50bdc4c4e6c147fedd43d0680512bcbb42c07d47349d2153b70c4e5d7fdfcbfa36ea1a85841b9e46e09a2
         INTEGER 0x008542d69e4c044f18e8b92435bf6ff7dd297720630485628d5ae74ee7c32e79b7
         INTEGER 0x04 (4 decimal)
      }
   }
   BITSTRING 0x040ae4c7798aa0f119471bee11825be46202bb79e2a5844495e97c04ff4df2548a7c0240f88f1cd4e16352a73c17b7f16f07353e53a176d684a9fe0c6bb798e857 : 0 unused bit(s)
}

I don't really know what's the meaning of every field of the ASN.1 structure.

And the result(use bouncycastle in java) is:

  04067c432c80857e3bd3c437cf6617309768f5ad1a0875d576feda7badf95bb2d572471b75afee6e089ad1128e4b8d587d2b755edf23d0f560dabfdcd66ce1e3c52eca632f28246eb626c148857b1e04b112ac9e2030551b39a87e

I can't decode it with ASN.1 Decoder.

However, I got another result of ECIES use openssl in C, which is:

  304b04210355f43b1936c7d95da83056240032b334334d5166108a37e74b3b1cceebe1d8e00410da784547fd402c00f9aff3d2c2b1a4f50414bec74472761453d0ce9abfee81693c895d5b5840

And I obtain the the ASN.1 structure :

       SEQUENCE {
          OCTETSTRING 0355f43b1936c7d95da83056240032b334334d5166108a37e74b3b1cceebe1d8e0
          OCTETSTRING da784547fd402c00f9aff3d2c2b1a4f5
          OCTETSTRING bec74472761453d0ce9abfee81693c895d5b5840
       }

Which I guess is R||c||d according to Integrated_Encryption_Scheme, but what's the result of bouncycastle ? I want to use openssl to encrypt and use bouncycastle to decrypt, is there any suggestion?

The public key structure is an X.509 SubjectPublicKeyInfo for ECC (public) key, using explicit format instead of (more common and popular) 'named' format. SPKI is a generic ASN.1 structure that supports multiple (and extensible) algorithms:

SEQUENCE {
    AlgorithmIdentifier = SEQUENCE {
        algorithm: OBJECT IDENTIFIER -- identifies the algorithm
        parameters: ASN.1 type and content varies depending on algorithm
    }
    publickey: BITSTRING -- content varies depending on algorithm
}

The algorithm-dependent parts for ECC are detailed in rfc3279 section 2.3.5 and yours has an explicit description of a curve over a prime field with 256-bit prime beginning 8542 in hex, coefficients beginning 7879 and 63e4, base point with X coordinate beginning 421d, and claimed order slightly less than the prime
but cofactor 4 which doesn't make sense to me; and a public key/point on that curve with X coordinate beginning 0ae4.

SPKI is the format Java crypto calls 'X.509' (X509EncodedKeySpec) and OpenSSL calls PUBKEY.

The BouncyCastle IES output is created at the end of encryptBlock in the source here for org.bouncycastle.crypto.engines.IESEngine as the concatenation of 'V' the sender's ephemeral public key, 'C' the ciphertext, and 'T' the MAC tag, without any delimiters or other added structure. Your posted value is 91 bytes, beginning 04 meaning uncompressed, and for a 256-bit curve uncompressed V is 65 bytes, leaving 26 for ciphertext plus MAC, which seems unlikely; could your data be truncated or otherwise damaged?


What does the comma mean in m, c := E(K, m) Disclaimer: I'm a beginner to cryptography.

Background: I'm reading Cryptography Engineering by Ferguson, Schneier, and Kohno, where the authors use this image:

Question: What do the commas mean here?

My attempt: m, c :=  --- seems to mean "given" m, c equals ...

It's a comma to separate the two things.  Alice has $m$ and can calculate $c$ which is equal to $E(K_{e}, m)$.  Bob has $c$ and can calculate $m$ which is equal to $D(K_{e}, c)$.


Is the nonce in GCM mode used as key for HMAC? And how to send it? So, my believe is that, in some way, GCM mode or any other authenticated encryption mode is useful to provide encryption and integrity for the ciphertext altogether instead of having to handle the encryption en HMAC separately (as in CBC + HMAC).

My confusion, and this might be a little bit directly related to Java API.., is that using GCM mode I can specify:

a nonce,
AAD data

So, my questions:

Is the nonce used to generate a "probabilistic ciphertext", as with IV in CBC mode?
Is the nonce also used as key to generate the HMAC for the ciphertext? And therefore only specifying this one I would already obtain an authenticated ciphertext (without having to specify the AAD data)?

Or is the AAD data the one used to generate the HMAC for the ciphertext (I'm pretty sure it's not)?
And if not, what is the AAD used for? "To provide an additional context HMAC to accompany the ciphertext"? Could somebody provide an example of this?

ALSO.., independently of which element is used as key to generate the HMAC for the ciphertext..
How must this one be protected?
As far as I know, the nonce does not have to be random, it can be a numeric sequence like 1, 2, 3.. for each encrypted message. This seems pretty guessable by an attacker. So isn't it dangerous to use a guessable nonce, or even send it in clear with the cyphertext?

Thank you, and forgive me if I have misused some cryptography terms or words.

Is the nonce used to generate a "probabilistic ciphertext", as with IV in CBC mode? Is the nonce also used as key to generate the HMAC for the ciphertext? And therefore only specifying this one I would already obtain an authenticated ciphertext (without having to specify the AAD data)?

Yes, it provides probabilistic ciphertext.

Contrary to you mentioning HMAC, GCM does use a MAC construction but it is called GMAC. The GMAC tag value is encrypted using the initial counter value, so the authentication tag - the MAC value generated by GMAC - does rely on the IV.

  Or is the AAD data the one used to generate the HMAC for the ciphertext (I'm pretty sure it's not)? And if not, what is the AAD used for? "To provide an additional context HMAC to accompany the ciphertext"? Could somebody provide an example of this?

AAD - the additional authenticated data - is included in the authentication, but it isn't responsible for creating the authentication tag. Actually, it is often empty. It can be used for any data that needs to be authenticated, but doesn't need to be confidential.

For instance the header data of a mail message or IP packet could be AAD data. It might be useful to authenticate it so the receiver address isn't altered, but of course the data to route the package to the right address needs to be readable by the routers in between.

  ALSO.., independently of which element is used as key to generate the HMAC for the ciphertext.. How must this one be protected? As far as I know, the nonce does not have to be random, it can be a numeric sequence like 1, 2, 3.. for each encrypted message. This seems pretty guessable by an attacker. So isn't it dangerous to use a guessable nonce, or even send it in clear with the cyphertext?

The authentication tag is protected by the same key (and for GCM, indeed, the same cipher / mode of operation) as used to keep the data confidential. So with most AEAD modes you just need one key (SIV mode cheats on this: it requires a double size key and then just splits it in half). And yes, for GCM mode you just require a unique IV/nonce, but remember that it breaks almost completely if you reuse the IV even once.

Please do not look at the Wikipedia pages to understand GCM, instead check section 7.1 of NIST. Note step 6: 6. Let $T=\operatorname{MSB}_t(\mathit{GCTR}_K(J_0,S))$ where $S$ is the outcome of GHASH and $J_0$ is directly derived from the IV ($T$ is the tag, $t$ the tag size and MSB the most significant - leftmost - bits, to be complete). Note that the hash is not secure without this block encrypt.

So the authentication tag is always dependent on the IV value. Note that a unique IV is required even if no data is being encrypted by GCM mode. The GMAC relies on the uniqueness of the IV, as this answer by poncho explains.


CRL number generation sequence: can I use a time stamp? RFC 5280 states that the CRL number should monotonically increase. I have seen this common practice of incrementing the CRL number by 1, every time a new CRL is generated. But can I use a Unix (epoch based) time stamp as the CRL number, which is monotonically increasing ?

Using a time stamp is certainly allowed, provided it is truly monotonically increasing. What I want to point out here is that computers have knowledge of the current date and time through their internal clock, which may be subject to drift and therefore to alterations to put it "back in line". Some systems will rely on NTP, a network protocol which is not the most secure protocol ever (in fact, base NTP is completely unauthenticated, thereby active attacker may fool with your clocks to some extent). Other CA, that try to work without relying on an unsecured network protocol, may be subject to heavy drifting over time, thereby requiring an occasional manual reset. Both the drift and the risk of human error may induce the CA into issuing a CRL with a non-monotonic number, which is a problem.

Another point to take into consideration is that "relying parties" (the systems that will read and process your CRL) may convert CRL numbers into relatively small integers, under the (faulty) assumption that "MAX" means "fits in a signed 32-bit integer". Beware of Year 2038! This would not be, technically, your fault (the RFC is clear in that respect), but it would still impact the already flimsy support for revocation.

For these reasons, a CRL counter, that is updated and saved across reboots, seems to be a better idea, from an engineering point of view.


What's the meaning of “family” in “family of hash functions”? Many definitions related to universal hashing mention the term

  a family of hash functions, say $H$

What does this 'family' mean exactly? A numerical example would be appreciated. Also, what does it mean to choose a hash function h at random from a hash family $H$?

In general, having a family of functions means that you have a function definition with a small detail, change, parameter or other tweak that can vary from function to function.

An (insecure) example would be if you'd parametrize the S-box in AES. Then you have a family of functions, and you select a particular member of that family by specifying the S-box. If you'd specify the S-box to be equal to the AES S-box you'd have AES.

Selecting a member of a function family at random means that you select the parameter at random. An example would be to randomly generate the S-box byte by byte.


Verifying Diffie–Hellman parameters someone else generated I am auditing some software that includes compiled in Diffie–Hellman parameters (2048 bits).

I can't be sure who generated the DH parameters or how they were generated.

Question:

Can DH parameters be weak if they were generated improperly or
made intentionally weak?
Is it possible to test DH parameters, that I did not generate, to see if
they are 'good'?

I realize this might be better discussed in security SE, however, I wanted to get a more abstract opinion about the cryptography in crypto SE, and depending on the answer here, I will raise a more specific question about the software in question, and what to do about it, on security SE.

UPDATE 2015-Oct-28:
Since I asked this question, the https://weakdh.org analysis was published and the upstream provider ( https://www.stunnel.org ) is changing how they manage the DH parameters. The compiled-in DH parameters may be re-generated during build or software packaging and new DH parameters are generated every 24 hours.

There are several possible ways to generate a weak DH group:

The attacker can generate a $g$ with a small order; this would make deriving the shared secret from the public values easy.
The attacker can generate a $g$ with a smooth order; that is, the order is large, but is composed of small prime factors; this would make deriving the shared secret from the public values easy.
The attacker can generate a $g$ with a large order, but one with a number of small factors; if the implementation also doesn't use large secret exponents, this would also make deriving the shared secret easy
The attacker can select a prime $p$ that is easy to attack with the Special Number Sieve algorithm; this makes deriving the shared secret easier (but no picnic; I believe that attacking a 2048 bit modulus with SNFS may be in the range of the NSA at the moment).
The attacker may select a composite $p$.  While this also makes it easier on the attacker, what this chiefly does is allow the attacker to disguise whether they're doing the above tricks.

With this in mind, the first thing I would do is check if $p$ is prime; if it is not, then either the implementer picked a random odd value for $p$ (which implies he's a bit clueless when it comes to cryptography), or he has something to hide -- neither of those sound good.

Assuming that $p$ is prime, then the next step would be to attempt to factor $p-1$ (or at least, search for any small factors, where 'small' means, perhaps, 128 bits or less); a tool that implements the Elliptic Curve Method to find small factors would be useful here.  You'll get $p-1 = 2 \times p_1 \times p_2 \times ... \times p_n \times q$, where $p_1, p_2, ..., p_n$ are small primes, and $q$ is a large number with no small prime factors (and $q$ may be either prime or composite).

The ideal case is that there are no $p_1, p_2, ..., p_n$ and $q$ is prime; that means that we have a 'safe prime'; any $g$ (other than 1 and $p-1$) is good, and and the implementor is clueful; other than SNFS, we're good.

The other extreme is that there are no large factors; you managed to completely factor $p-1$ into small factors; this means that the DH problem is easy here; fail.

However, if it is somewhere in the middle, we then need to determine the order of $g$.  First thing to check is if $g^{2\times p_1 \times p_2 \times ... \times p_n} = 1$; if so, then someone generated $g$ with a smooth order; fail.

The next step is to compute $g^q$; and find the minimal $r$ which is a divisor of $2 \times p_1 \times p_2 \times ... \times p_n$ with $(g^q)^r = 1$.  Here, the ideal case is $g^q=1$ (as $r=1$).  What this matters is that the attacker can compute the secret exponents modulo $r$.  If $r$ is large, and if the secret exponents aren't, this can significantly reduce the strength of those secret exponents.

The last step is to check if the SNFS discrete log algorithm can be applied; I'm sorry, but I can't help you with that.  On the other hand, SNFS isn't as large of a concern as these above issues.


What is the difference between “secp…” and “sect…”? The National Institute of Standards and Technology (NIST) recommended elliptic curve domain parameters to have names such as “secp…” and “sect…”.

For example: “secp224k1” and “sect571k1”.

What is the difference between “secp…” and “sect…”?

The sect curves are curves over a binary field. From SEC 2: Recommended Elliptic Curve Domain Parameters (chapter 3):

  The example elliptic curve domain parameters over $\mathbb{F}_{2^m}$ have been given nicknames to enable them to
  be easily identified. The nicknames were chosen as follows. Each name begins with sec to denote
  ‘Standards for Efficient Cryptography’, followed by a $t$ to denote parameters over $\mathbb{F}_{2^m}$ , followed by a
  number denoting the field size $m$, followed by a $k$ to denote parameters associated with a Koblitz curve
  or an $r$ to denote verifiably random parameters, followed by a sequence number.

While the secp curves are over fields over a prime field - or $\mathbb{F}_p$ in mathematical representation. Please read elliptic curve tutorials to understand the difference between the calculations for prime and binary fields.


Self verifying hash algorithm For quite some time I've been thinking about the idea to construct a hashing algorithm that contains its own checksum value, and thereby can verify itself. With hashing algorithms like SHA1 and MD5 this seems to be difficult although not impossible as explained here. The content that is hashed could never change, but I can think of a few situations where this is absolutely desirable. For example, certificates containing their own thumbprint calculated over all fields. I have tried to design the basics myself once, but that was more ambitious than I had foreseen.

The way I see it there are two approaches:

Narrow down the possible hash values by analyzing the content. Then race for all possibilities to see if the content and the hash match. I have implemented this and although it did work it was everything but usable.
Calculate a hash and adjust the content to match the hash value. For hashing algorithms like MD5 this is near to impossible and any new algorithm would possibly impaired by this.

I'm convinced it is both possible and usable someway, therefore it surprises me how few there is to find on the subject. Are there any case studies or related algorithms to this idea?

I think what you're missing here is that a cryptographic hash by itself is not actually sufficient to verify the integrity of a message.  Consider this:

I want to send a message over the Internet (on an insecure connection, e.g. UDP), but have it be protected from tampering.  I take the message and attach at the end a cryptographic hash of the message (e.g. SHA256(message)).  When my friend receives the message, she verifies that the hash at the end matches SHA256(message).

Now, despite the fact that she has "verified" the message using a cryptographic hash, it turns out that this is not sufficient to prevent tampering.  If an attacker is able to intercept and modify the message before it reaches my friend, they can remove the old hash, SHA256(message), and add a new hash, SHA256(tamperedMessage).  When my friend receives the tampered message, she won't notice anything is wrong, because the message she receives still ends with a matching SHA256 hash.

Hashes do not (by themselves) provide integrity protection (in other words, prevent tampering).  Hashes provide a convenient way of identifying the content of a message.

We can use hashes to build schemes that do provide integrity protection.  Consider the earlier example.  Let's say I again transmit a message to my friend over the Internet, this time without a hash.  She receives the message, but knows that she can not yet trust that it has not been tampered with.  If I meet up with her in person, I can provide her with the hash, say, diligently scrawled on a sheet of paper.  If she checks this hash against the message she received over the Internet, she will know that it has not been tampered with.  Why?  Because (1) the hash uniquely identifies the original, legitimate message and (2) the hash was provided over a secure channel (i.e. in person).

This is why having a hash that "verifies itself" does not prevent tampering.  You could attach to a hash, a hash of that hash, then attach to that hash, a hash of that hash, but your scheme would still not provide any integrity protection unless the hashes are provided over a secure channel.  Hashes identify, and further identifying the identifier does not actually improve security.

Note (in anticipation of nitpicks): I used the term "uniquely identifies".  Hashes aren't actually unique from a theoretical perspective, but they are in practice.


Is there a lower limit on message length for signature? I was working on a tool that signs small messages (~20 bytes) when a question occurred about message size: What would be the risk of using extremely small/restricted input (say, 5 bytes of hexadecimal chars) messages? Since the data is a hash and replay attack is not a concern, the message wasn't originally salted.

Would a signature and/or collision be easier (/easy) to generate without the private key? Or would that make the private key vulnerable in any way?

In this particular case we are using Ed25519, which does double hashing on the value before encryption, so I don't see an issue for the public key, but I'm still concerned.

The lower limit is a single byte.  Ed25519 is not defined for units smaller than a byte, but if it were, there would be, in principle, no security issue with signing a single-bit message: the expected cost of forgery on a message of any length, from a bit to an exabit, remains near $2^{128}$ and therefore well out of reach for humanity.


Birthday attack on hash functions derived from a collision-resistant hash function $H_1$ is a collision-resistant hash function with an $L$-bit output. 2 hash functions are created based on it as follows:

$$H_2((k_1,k_2);m) = (H_1(k_1;m), \space H_1(k_2;m))$$

$$H_3((k_1,k_2);(m_1,m_2)) = (H_1(k_1;m_1), \space H_1(k_2;m_2))$$

Notation: $k1$, $k2$ are keys. $m$, $m_1$, $m_2$ messages. $(m_1,m_2)$ is simply the concatenation of $m_1$ and $m_2$. What would the smallest number of evaluations (based on $H_1$) be to successfully do a birthday attack on $H_2$ and $H_3$ with at least 1/2 probability? Could you please explain along with the attack that you build against $H_2$ and $H_3$?

This is a past practice question and I do have a solution (spoiler: see bottom of post) but do not understand how to get to it myself. I understand that to find a collision in $H_1$ I have to do $2^{L/2}$ number of evaluations where $L$ would be the output length.

Bonus help would be any variations of the given hashes to help solidify my understanding of the concept further.

The final answer is: $O(2^L)$ for $H_2$ and $O(2^{L/2})$ for $H_3$

Hint:  Can you break down the problem of finding a collision in $H_2$ into two independent subproblems that you can compute separately, or do you have to find a collision for all of it together?  What about $H_3$?


What is the reason of using Pedersen Commitment scheme over HMAC? I want to implement non-interactive Bit Commitment scheme for messages of arbitrary length.

And I am curious, what is the reason of using Pedersen Commitment scheme over Salted Hash (in other words HMAC).

Example is coin flipping protocol from Wikipedia:

Alice "calls" the coin flip but only tells Bob a commitment to her call,
Bob flips the coin and reports the result,
Alice reveals what she committed to,
Bob verifies that Alice's call matches her commitment,
If Alice's revelation matches the coin result Bob reported, Alice wins

With HMAC Alice calculates a hash of her call at step 1 and reports it to Bob, keeps key (salt) in secret. During reveal step (3) she reveals a key.

With Pedersen Commitment scheme she reports her commitment at step 1, then reveals her call at step 3 with additional data, related to scheme.

In this case, there probably is no difference.

The Pedersen Commitment scheme is often used in cryptographic protocols because:

It allows zero-knowledge proof to prove some properties of the committed value.
It is perfectly hiding, which can be important in proving the security of the protocol.

Hash based commitment schemes do not have the above two properties. However, they may be more efficient and are preferable in certain scenarios.


HMAC for round-trip validation I have a need to produce URLs to allow the downloading of a single file, without authentication.  These links will be sent through email, and I understand and accept the risk of a given link being shared by its recipient (or intercepted in transit).

Each file is identified by a UUID, generated in SQL Server using NEWID().  I need to prevent an attacker who knows the link format from brute-force guessing other UUIDs and accessing other files shared this way. Note also that the links have an automatic expiration.

My current link scheme sends the UUID along with an HMAC.  The HMAC is generated using:

a payload composed of system-level salt + a per-file nonce salt + the UUID
a 128-byte system-level key to compute a SHA2-512 HMAC

Is any part of this superfluous or excessive? Does using HMAC gain me any additional security over a simple strong hash in this scenario?

For discussion about T-SQL NEWID(), see SQL Server : does NEWID() always gives a unique ID? on StackOverflow.

If you look at RFC 4122 then you can see which bits are not random. I think that are 128 bits in the UUID and 6 of them are non-random to indicate the scheme used. That leaves 122 bits of UUID, which is probably enough to consider them relatively random. Only if you generate many millions of them is there a chance of collision. However, there is a reason why a hash commonly has an output size of double the wanted security level because of the birthday paradox. And 122 / 2 = 61 bits of security, which is on the low side. So it might be a good idea to extend at least the randomness of the value.

Of course you can always add random bits to them and a MAC using a secret key would that. It would allow you to reject tries with relative confidence. Furthermore, you could reject those before a database lookup. How much confidence depends on the security of the MAC, usually limited by the output size of the MAC. It does of course require the additional burden of key management though.

Alternatively you could simply add more random bits to the UUID or to generate a proprietary 256 bit UUID. However, I think the MAC scheme over the UUID is relatively elegant as the MAC can be over the UUID, while keeping the UUID scheme intact, and it can be extended by adding a salt. Of course the secret key must be kept secret otherwise an adversary can generate the same.

The disadvantage is that the UUID as send with MAC and possible salt is not standardized anymore, so you have to think about an alternative canonical encoding of UUID and MAC.


Randomness extractors from Bourgain’s breakthrough- applications? Some exciting progress to pure mathematics is due to Bourgain

Springer - Multilinear Exponential Sums in Prime Fields Under Optimal Entropy Condition on the Sources

with applications to randomness extractors and gave the first two source extractor with min entropy rate <0.5

Since this paper there’s been other innovations and simplifications of Bourgains work, such as

An explicit two-source extractor with min-entropy rate near 4/9

This is all exciting for mathematics. Is the same true from an applied crypto perspective? For example, would it help in any way with the issues discussed here

The GCD strikes back to RSA in 2019 - Good randomness is the only solution?

Other applications/places where these theoretical breakthroughs have already been applied?

...would it help in any way with the issues discussed here?

No, not really. There's always been a gap between myriad theoretical mathematical extractor constructs and those used in commercial validated TRNGs.  I honestly don't know why as that seems like an unlikely dichotomy, yet it demonstrably exists. The two should ideally converge to a common output entropy rate, but they don't :-(

Most creditable TRGNs are based on min. entropy extraction via the Left Over Hash Lemma: $  \epsilon = 2^{-(sn-k)/2}   $ where $s=H_{\infty}$per bit input to the extractor. This lemma is unaffected by Bourgain.

So no.


What conditions does a provable secure cryptosystem satisfy? A cryptosystem can be entirely dependent on its underlying problem or it can have a reduction to other known problems. Solvability can be affordable if there exists a reduction of the base problem to another problem, and the last is feasible.

I understand that a cryptosystem is provable secure if it has been well studied during years giving rigorous proofs on:

Cryptanalysis. By analyzing the base problem with existing techniques, measuring complexity (computational hardness), attempting to reduce to an affordable/easier problem.
Implementation. There is an efficient way to describe the cryptosystem in a resource bounded device, where security must be achieved.
Future expectation. Security facts based on theoretical cryptanalytic techniques, where the application of these methods is not feasible nowadays but theorized in the future.

Q: Is there any other condition for a cryptosystem to be stated as provable secure?

Q: Provable secure is not the same as probable secure. Does this last term has a broader definition in Cryptography?

Example, in maths a probable prime it's a pseudoprime (prime with probability threshold). And a provable prime is a prime that has been proved to be prime (i.e satisfies Fermat test and is not a Carmichael Number).

Provably secure doesn't actually mean secure. Plenty of provably secure cryptosystems were broken and not because the proof had a flaw. When something is provably secure, it just meant some statement regarding it's security has been proven. There are any number of such statements.

A proof always starts off with some assumptions, such as the hardness of some underlying problem, or security property of some building block. A statement about something else can then be build on top of those assumptions. But when that statement is formalized, it is never as broad as: "$X$ is secure".  Instead the statement would be a more specific statement such as: "If you can invert $F$ you can also invert $G$, but $G$ is believed to be hard to invert. In this protocol under such and such assumption an attacker learns nothing more then he knew initially."

WPA is provably secure. They went all out on this proof. It was not just proven that the specification was secure in that no key material could leak. The implementation was proven to match the specification and the compiler was proven to work correctly.

And yet WPA was horribly broken. The proof didn't say anything about an attacker being able to coerce an all zero key. The attacker learned nothing, the security proof was not violated.

Provably secure does not imply Secure. It implies only whichever claims were actually proven.


Have there been efforts to prevent length extension attacks of hashing algorithms that are based on the Merkle–Damgård construction? Have there ever been some publicized efforts to prevent length extension attacks of hashing algorithms that are based on the Merkle–Damgård construction (MD5, SHA1, SHA2, ...)?

Yes. In this paper, Coron and al. showed that a plain MD construction is secure when it's inputs are prefix-free. They actually proved the indifferentiability of the construction. In other words messages need to be encoded in a prefix-free manner.

Quoting the paper:

  A prefix-free code over the alphabet $\{0, 1\}^κ$is an efficiently computable injective function $g: \{0, 1\}^∗ \to (\{0, 1\}^κ)^∗$such that for all $x \neq y$, $g(x)$ is not a
  prefix of $g(y)$.

One such encoding is given in the paper

  Function g1(m): let $N$ be the message length of $m$ in bits.
  write $m$ as $(m_1, \ldots , m_l)$ where for all $i$, $|m_i| = k$.
  and with the last block $m_l$ padded with $10^r$.
  let $g1(m) = (\langle N \rangle, m_1, \ldots , m_l)$ where $\langle N \rangle$ is a $κ$-bit binary encoding of $N$.


How does hashing help improve password security? Suppose we visit https facebook.com for the very first time. We are creating a new account and creating a password. Then we send then password to the server, the server receives this and only then hashes it.

All consequent log-ins, you won't have to send your password as a plaintext, it will be sent as a hash and the server will compare the stored hash and the hash you've sent. If they match up, it means you know a password.

But interesting thing happens. When we create a password we need to send a password to the server as a plaintext for the very first time in order for the receiver to hash it and store.

What if someone intercepts the data at this time? What am I missing here?

First, you don't actually send a hash on subsequent connection attempts, you still send the plaintext password. Second, even if you would send a hash, the same hash, every time, this hash would effectively be your new password.

Now for your actual question:

  What if someone intercepts the data at this time? What am I missing
  here?

The fact that HTTPS is used. HTTPS stands for HTTP-Secure, which means it's HTTP over TLS. Now if your browser properly validates the data it gets from the server (which all browsers do), then you can be sure that the party at the other end of the encrypted TLS connection actually is facebook.com, at which point you also know for sure that the connection hasn't been intercepted.

  It says that plaintext is not secure so servers store only hashes of
  the passwords. How this works exactly.

Assume we have a secure connection between the client and the server, that is the client knows for sure who the server is (eg facebook.com). TLS achieves this. Now for the registration send the server the username and the password you want to use. The server password-hashes the password and stores it alongside the username. Now on subsequent log-ins you send the password again, the server retrieves some parameters from your username, applies the password hash again and compares the result with the stored value. If they match, you are authenticated, if not, then not.

Why the hashing on the server? Suppose the database of the server where all the password hashes and usernames are stored gets compromised (eg an attacker gets root access to the server or can dump the database using an SQL injection), now if you have stored plaintext passwords, the attacker can immediately use these against your service and any other sevice these users may use (assuming they re-use passwords, many do). Now if you have hashes, the attacker first needs to find inputs that map to these hashes, for this they usually need to try out a lot of passwords, which is infeasible for really good passwords and even for weaker passwords takes a moment of time. So now the passwords aren't complete and utterly compromised when the server's security fails.


Is changing $H(R\mathbin{\Vert}A\mathbin{\Vert}M)$ to $H(R\mathbin{\Vert}A\mathbin{\Vert}H(M))$ in EdDSA secure? EdDSA calculates $s=(r+H(R\mathbin{\Vert}A\mathbin{\Vert}M)\cdot a)\bmod\ell$ and $r=H(h\mathbin{\Vert}M)$, with

$H$ being the hash function (SHA2/512);
$B$ being the generator;
$A$ being the public key;
$a$ being the secret exponent;
$r$ being the per-signature random;
$h$ being the secret seed ($h[b~.\!.~2b-1]$ in the paper).

What is the effect on the security of the signature if $M$ is replaced by $H(M)$ or $H(A\mathbin{\Vert}M)$, thus producing $s=(r+H(R\mathbin{\Vert}A\mathbin{\Vert}H(A\mathbin{\Vert}M))\cdot a)\bmod\ell$ and $r=H(h\mathbin{\Vert}H(A\mathbin{\Vert}M))$?

This would mean the message needs to be hashed only once during signing, which is more efficient for long messages, but would the signature lose any security quality? Specifically the paper says that the signature provides collision resistance, would this disappear with $M$ being replaced by $H(M)$? What about $H(A\mathbin{\Vert}M)$?

Assuming this is the paper you're talking about, your modification completely eliminates resilience to collisions in the underlying hash function $H$. The EdDSA scheme (and in the Schnorr scheme on which it is based) is highly resilient against collisions in $H$. Specifically, in the generic group model, the Schnorr scheme has been proven to be secure even if $H$ isn't collision-resistant; all it requires for security is that $H$ be resistant to random-prefix preimage attacks and random-prefix second preimage attacks (essentially, given random $R$: given $h$ it's hard to find $M$ s.t. $H(R||M)=h$, and given $N$ it's hard to find $N^\prime$ s.t. $H(R||N)=H(R||N^\prime)$ and $N\ne N^\prime$).

So EdDSA can be perfectly OK with a not collision-resistant hash; as far as we know, it doesn't need collision resistance, just random-prefix preimage and random-prefix second-preimage resistance.

However, your modification is trivially vulnerable to a collision in $H$: If $H(M)=H(M^\prime)$, then if you hash $M$ before signing, you end up with an EdDSA signature of $H(M)=H(M^\prime)$ which (under your modification) is a signature for $M^\prime$. If you instead do $H(A||M)$, an attacker who finds any chosen-prefix collision can create two messages such that a signature for one is a signature for the other. If you use $H(A||M)$ as the thing to be signed, someone who can find any two messages s.t. $H(A||M)=H(A||N)$ again can take a signature for one and use it as a valid signature for the other. With a good hash function, they can't find said collision, but Schnorr (and so EdDSA) is designed such that it doesn't break if they can do that.

If someone gets a message $M$ signed with $(R,S)$, and finds a second preimage for $H(R||A||M)$ (i.e. $M^\prime$ s.t. $H(R||A||M^\prime)=H(R||A||M)$, then the signature for $M$ is valid for $M^\prime$. However, an attacker with just the ability to find collisions cannot exploit this: they do not control $R$, and $R$ is different for each $M$. So finding a collision in $f(M)=H(R||A||M)$ is useless for the attacker; to exploit the collision, one of the colliding messages must have $H(h||M)B=R$, which is not going to be the case for a generic one of a colliding pair. Collision attacks do not apply, because a colliding pair only helps if they collide when prefixed by a secret function of one of them, which will not generally be the case.


Cryptography scheme to prove you really are the author for something Say I'm a researcher like Satoshi Nakamoto that wants to stay anonymous. I want to publish documents and sign them somehow. A few years, I want to reveal my identity and prove it was me who was Satoshi all along.

Is there a cryptography scheme that can be used to achieve this?

The solution is easy if you have a Trusted Authority(TA). Assuming that there is no TA.
A direct digital signature can be a solution. However, how we can trust that Satoshi is not faking person $x$ by stealing his keys or he killed the person $x$ to steal the keys.
A solution
by using biometrics to uniquely identify the original person.
Satoshi follows the steps;

produces a private-public keys $k_{priv_s}, k_{pub_s}$  for his digital signatures.

he appends his biometric data; his fingerprint $fp_s$, his unique DNA code $dna_s$, and his iris $iris_s$ data to the document $d$.
$$author = d \| fp_s \| dna_s \| iris_s $$

$Sign(k_{priv_s},author)$ by using digital signature standard.

Adds the signature and $k_{pub_s}$ to the document before print.

Secretly publishes the document.

So that, when a person showed up with the signature key to reveal himself, the others have to look at the biometric data to match.
The entropies;
Possible values: O’Gorman,L., Comparing Passwords, Tokens, and Biometrics
for User Authentication;

A biometric doesn’t have a fixed number of possible values. Theoretically, the keyspace of biometrics such as fingerprints is unlimited because if you could measure the continuous signal with infinite precision, no two would be the same. But, one could say the same for passwords, that if you allowed the password length to be unlimited, you’d also have an unlimited keyspace

Fingerprints; Young et. al, Entropy of Fingerprints;

The average number of minutiae present in each image was 28.02. Therefore, dividing the entropy of 55.02 bits by the average minutiae of 28.02, each minutia provides 1.963 bits of entropy.

Note: Fingerprint copying; I've found only this, it is easy to detect it when there are observers.
Note: I changed the key generation from biometrics. Some of them are not exactly reliable.

Claims to be the Satoshi

nChain chief scientist Craig S. Wright that he created Bitcoin. But it is debunked and the claims are called nonsense.


Why does the WhatsApp protocol require elaborate computation when verifying user keys? Reading through the WhatsApp protocol (PDF), I am trying to understand why the multiple hashing and other stuff done is required. According to the paper, one can compare the hash of the key material on both ends. The hash (60 bytes) is computed like this:

  The 60-digit number is computed by concatenating the two 30-digit numeric fingerprints for each user’s Identity Key. To calculate a 30-digit numeric fingerprint:

  Iteratively SHA-512 hash the public Identity Key and user identifier 5200 times.
  Take the first 30 bytes of the final hash output.
  Split the 30-byte result into six 5-byte chunks.
  Convert each 5-byte chunk into 5 digits by interpreting each 5-byte chunk as a (big endian) unsigned integer and reducing it modulo 100000.
  Concatenate the six groups of five digits into thirty digits.

Why is that elaborate computation needed? What if I simply do a hash of both public keys and concatenate the first 30 bytes of each key? Why would it not suffice? Is it simply to make sure to reduce collision when using only 30 bytes of each hash?

I agree with the comments, in that the aim of step 1 is likely to increase the cost of performing a man-in-the-middle attack. When two users want to verify their keys, the only information they rely on is that the 60-digit number derived from both their keys matches. Hence, an attacker would need to generate an expected $2 \cdot 10^{30}$ random Curve25519 keys to find two keys that generate a matching 60-digit number. Since a security level of $2^{101} \approx 2 \cdot 10^{30}$ is a little weak, additional SHA-512 operations are added to make brute force costlier (although this technically does not raise the security level, since that is generally measured in terms of the key length and not the number of operations).

Steps 2 to 5 are just to make the output human readable. See this blog post on Signal for more information on why they chose this format.

Hashing both public keys and then concatenating the first 30 bytes would also be fine, and it would in fact give you a higher security level, but then you'd end up with 60 bytes, or 120 hexadecimal characters, to compare.


Which is better when the secret is leaked, RSA or Diffie-Hellman? I know that DH can be used for perfect forward secrecy but for the sake of this example, let's say that RSA and Diffie-Hellman are both used to establish a symmetric key that will be used for future encryptions.

Which one is more secure or more vulnerable if the secret key was ever leaked?

Neither one is secure if the private key is leaked; if the connection data is kept by and adversary then the adversary could decrypt the connection data if the private key of either DH or RSA key pair is lost.

The idea of ephemeral Diffie Hellman is that you create two new key pairs for each connection. Then you can throw away the key pair(s) after the connection has been set up and authenticated. Even if the private key is factored or otherwise retrieved then you could only attack a single connection. If the server is found by anybody then the private key would already have been destroyed, so this makes it impossible to decrypt the data when the server is found. This is what forward secrecy offers you.

RSA is not very useful when it comes to generating ephemeral key pairs. RSA key pair generation is one of the slowest algorithms that exist, and the time it takes to find two or more primes is indeterministic as well. In principle you could generate a new key pair at one side and use it to agree on a master key, just like with ephemeral Diffie-Hellman.


Using Stream Cipher as CSPRNG Are there any guidelines or justification for converting a stream cipher algorithm for use as a CSPRNG?

For instance, lets say I wanted to convert one of the eStream portfolio Profile 1 (software) selections for use as a CSPRNG. What I could do is generate a really unique hash from some other algorithm and use it as the key. Then I could generate another really unique, lets say 64-bits, and use it as the initialization variable. Now, what are my options? I could continue regenerating output blocks based on the cipher's internal variables. I could try to encode an incrementing counter into the block stream and then get the output. I could regenerate a key and (iv) and get the output again (seems costly).

I read that it's generally not smart to re-use the key on multiple encodings, so that makes me think I should just keep regenerating the first output block. Is the original output block by definition an unending random stream?

Using a stream cipher for mass generation of "random" bytes is a fairly good solution, however the risk is loosing Forward Secrecy at some point. The trick then is re-keying the cipher often enough, and having a good source of random data with which to rekey your cipher.

See Fortuna.


Operation sequence authentication shared storage Let's say there is a shared storage: USB flash drive, external HDD, or whatever you like. I'll refer to it as disk. Also, there are multiple parties, let's say Alice and Bob (may be thousands of them) who periodically access that disk exclusively. So, for instance, one day Alice takes disk from the table, reads and writes to that disk and puts it back on the table. Next day Bob takes disk from the table, reads and writes to that disk and puts it back on the table. Than Bob again, than Alice again. Access sequence is random and unpredictable.

If we'll assume that Bob's PC is compromised and Eva sees everything written on Bob's PC, everything written on disk from Bob's PC, etc. It there any way for Alice to detect that disk was modified by Eva?

Here is Example. Let's say we store some number on the disk and all parties have assigned public and private keys and we write "Number", "Author" and "Number encrypted by private key" on the disk.

So, Bob writes

"3", "Bob", RSA("3", BobsPrivateKey)

Alice can decrypt 3rd value with Bob's public key and see if it equals to "3". But if Eva had stolen Bob's private key she can write

"5", "Bob", RSA("5", BobsPrivateKey)

So Alice validation will fail. I need some other validation, not so simple, to detect if disk was modified by Eva. I've thought about HMAC with operation sequence numbers and list of sequence numbers used, but I'm not sure.

Yes. $\:$ Since "Eva sees everything written on Bob's PC", the process needs to involve something

that's not written on Bob's PC. $\:$ They could use either some sort-of MAC that can be computed

with pencil-and paper, or a signature scheme whose private key is held on a hardware token.

I don't have any particular such MACs in mind, although my immediate idea would

be to lay the message out on a grid, interpret characters as modular integers,

and let the tag consist of sums of characters from certain small subsets of the grid.

Also, it is very rare for using "Number encrypted by private key"

and decrypting values with public keys to be secure.

Almost always, one should be using Number signed by private key

and verifying with the public key instead.


Why are elliptic curve variants of RSA "chiefly of academic interest"? Yesterday I was thinking about elliptic curve variants of popular protocols/algorithms (ECDH, ECES[1], etc) and the thought occured that I had never seen an elliptic curve variant of RSA. My understanding of RSA and elliptic curves told me that it should be possible.

After some searching I found the following explanation:

  As we have mentioned, there are elliptic curve analogs to RSA but it turns out that these are chiefly of academic interest since they offer essentially no practical advantages over RSA. This is primarily the case because elliptic curve variants of RSA actually rely for their security on the same underlying problem as RSA, namely that of integer factorization.

This got me thinking. I had thought that the discrete log based systems I mentioned earlier were also based on the same underlying problem, the discrete log. But the article had this to say:

  The situation is different with variants of discrete logarithm cryptosystems. The security of the elliptic curve variants of discrete logarithm cryptosystems depends on a restatement of the conventional discrete logarithm problem for elliptic curves. This restatement is such that current algorithms that solve the conventional discrete logarithm problem in what is termed sub-exponential time are of little value in attacking the analogous elliptic curve problem. Instead the only available algorithms for solving these elliptic curve problems are more general techniques that run in what is termed exponential time.

So now, to my question: Why are we able to restate the discrete log problem to make it more practical on elliptic curves but not the RSA problem?

1. ECES is the elliptic curve variant of ElGamal

The generic discrete logarithm problem is this:

  Given a group $(G, ·)$ with generator $g$ and $y \in G$, find $x \in \mathbb N$ such that $y = g^x$.

The "classic" discrete logarithm problem (the one used in "classic" DSA and ECDSA) is this with some subgroup of the (multiplicative) group of a prime field, i.e. $(\mathbb Z/p \mathbb Z)^*$:

  Given a prime number $p$, a generator $g$ (of some large subgroup) and $y \in \left<g\right>$, find $x \in \mathbb N$ such that $y = g^x \bmod p$.

The elliptic curve discrete logarithm problem is this with a subgroup of an elliptic curve group:

  Given an elliptic curve $(E, +)$, a generator $G$ of some large subgroup, and $y \in \left<G\right>$, find $x \in \mathbb N$ such that $y = x · G$.

There are generic algorithms (such that the baby-step giant-step algorithm) for solving the discrete logarithm in any group (assuming a computable group law, or even just oracle access to the group law), and these work just fine for elliptic curve groups, as well as for the classic prime field. The average running time of these algorithms usually depends on the size of the group, like $O(\sqrt{|G|})$ for baby-step-giant-step. This is still exponential in the input size (since the input size is in $O(\log|G|)$, if one doesn't select really stupid encodings).

But for some special groups the discrete logarithm is easier, since they have some more (and known) structure. As an extreme case, consider the additive group $(\mathbb Z/n \mathbb Z, +)$ (for any positive integer $n$), with any generator. It is very easy to solve this problem even for quite large $n$ – we need only a single modular division, i.e. one execution of the extended euclidean algorithm. (And if the generator is fixed, we even can calculate its multiplicative inverse once and reuse it later, then it gets down to one multiplication per problem.)

The multiplicative group of the prime fields is harder. There is no known polynomial time algorithms, but there are still algorithms faster than the generic ones, using subexponential time. (Yes, there is some gap between exponential and polynomial.) The number field sieve for factoring integers can actually also be used to calculate discrete logarithms in prime groups (and needs similar running time for similar input sizes of both problems).

Thus we need larger prime field groups than we would need for a generic group for a same "security level".

For some elliptic curves, it looks like the discrete logarithm is almost as hard as for a generic group of the same size, which means that there are no specialized algorithms which are much faster than the generic ones. (When there are, one calls the corresponding group "broken". )

The effect is that for a similar security level, we can use quite smaller elliptic curve groups than prime groups (and it turns out that for these smaller groups, the calculation is also faster).

On the other hand, have a look at the RSA problem. It is about this:

  Given $n$ (a product of two large unknown primes), $e$ (with $\operatorname{gcd}(m,e) = 1)$ and $x < n$, we look for $m$ such that $x = m^e \bmod n$.

The most efficient known method to solve this (other than maybe a brute force attack on $m$ when it comes from a small sub space) is by factoring the modulus, then calculating the private key $d$ and decrypt it. So the hard problem here is factoring the modulus.

It is not really clear how to generalize this to any group (or what other kind of structure). I found A semantically secure elliptic curve RSA scheme with small expansion factor (2002), and it refers to (and includes an description of) an earlier work (N. Demytko. A new elliptic curve based analogue of RSA. EUROCRYPT ’93,
LNCS 765 40–49 (1993).)

Demytko's scheme works on an elliptic curve (and its twists) over the ring $\mathbb Z/n\mathbb Z$ (where $n$ is still a product of two large primes), and encrypts using $c = e \star m$, which is the $x$-coordinate of $e·(m,y)$ for some $y$ such that this is on the curve, and decrypts a ciphertext $c$ as $m = d \star c$, where $d$ is one of four inverses of $e$, and it depends on $c$ which one to use.

The second one even works in a curve over $\mathbb Z/n^2 \mathbb Z$ (but claims to be semantically secure, as it incorporates a random component).

In both cases it looks like the easiest way to break this is to factor $n$ (in the natural numbers), not some analogous problem in an elliptic curve based structure.

This means $n$ must be just as large as for RSA, and thus we have correspondingly large curves – not really an advantage of using elliptic curves here.


Security of the iterated Hill Cipher I can understand that the basic Hill Cipher is susceptible to known plaintext attacks, but suppose the Hill Cipher is modified into the Iterated Hill Cipher. For a plaintext $x_0=m_0$ and an initialization vector $x_{-1}=u_0$ we have,

$$x_{i+1}=Ax_{i}-x_{i-1}$$

for $0\leq i< k$. So our private key consist of the triplet $(A,\,u_0,\,k)$ where $A$ is an invertible matrix. The ciphertext will be the tuple, $c=(x_{k},\,x_{k-1})$. This is the idea behind the Iterated Hill Cipher given in Symmetric-Key Homomorphic Encryption for Encrypted Data Processing (paywall).

Then there are lots of research papers which try to employ Latin Squares and Magic Squares for $A$. Here are some:

Strengthened Iterated Hill Cipher for encrypted processing (paywall)
Successful Implementation of the Hill and Magic
Square Ciphers: A New Direction (pdf)

So my question is: why do people try to use Quasi-groups (Latin Squares) and Magic squares for the Hill Cipher? Does it improve the security?

Updated answer

The question was changed, so here is my updated answer.

This scheme is not secure against known-plaintext attacks.  It is no better than an ordinary Hill cipher.

If you iterate the recurrence relation you listed, we find that

$$x_k = Bx_0 - Cx_{-1}$$

and

$$x_{k-1} = Cx_0 - Dx_{-1}$$

where $B,C,D$ are matrices given by $B=f(A)$, $C=g(A)$, $D=h(A)$, and $f(\cdot),g(\cdot),h(\cdot)$ are publicly known polynomials that depend only upon $k$.  (For instance, for $k=4$, we have $B=f(A)=A^4 - 3A^2 + \text{Id}$, $C=g(A) = A^3 - 2A$, $D = h(A) = A^2 - \text{Id}$.)

It immediately follows that this scheme is insecure against known-plaintext attack.  Each known plaintext pair gives you $m_0$ (the message), $u_0$ (the initialization vector), $x_k$, and $x_{k-1}$ (from the ciphertext), so we know $x_{-1},x_0,x_{k-1},x_k$.

Therefore, each known plaintext gives us two linear equations, with the unknowns being the elements of $B,C,D$.  If the matrix is $n\times n$, then after $1.5n$ known plaintext pairs, we have enough information that we can probably recover all of $B,C,D$, and then the scheme is broken.

In fact, I expect this scheme might even be breakable via a ciphertext-only attack.  I think we always have $C^2 = BD + \text{Id}$.  Therefore,

$$Cx_k = BCx_0 - C^2 x_{-1}$$
$$Bx_{k-1} = BCx_0 - BD x_{-1}$$

so

$$Bx_{k-1} - Cx_k = x_{-1}.$$

Note that in a ciphertext-only attack, $x_{-1},x_{k-1},x_k$ are all known (from the initialization vector and the ciphertext).  Therefore, each ciphertext gives us a linear equation on the unknowns $B,C$.  After observing $2n$ ciphertexts, we should be able to solve for the matrices $B,C$.  Then deriving $D$ is easy, and we will be able to decrypt.

Therefore, it looks like there is even a ciphertext-only attack on this scheme.  Caveat: I haven't validated this ciphertext-only attack carefully, so check the details yourself.  I might have made a mistake somewhere.

So why do those three papers still study Hill ciphers?  I don't know, that would be an excellent question for the authors of those papers!  Only they will know what was going through their minds.  I wasn't able to read the first two papers (due to the paywall), but I took a quick look at the third paper, and I do not think there is a good reason to study these ciphers.

Keep in mind that there are a lot of papers out there, and quality varies widely.  Just because a paper has been published doesn't mean it is any good.  You will do better by sticking to conferences and journals that are well-reputed; once you start wandering off into obscure conferences and journals that are not well-regarded among cryptographers, the quality might vary tremendously.  Similarly, if you find a crypto paper published in a conference that is not dedicated to cryptography, you might also want to be a bit cautious or skeptical.  My suspicion is that the three papers you have found just aren't very good, and so there is not much more to say.

Original answer

Your proposed scheme is not secure.

If $A$ is public, given $x_{i+1},x_i$ you can compute $x_{i-1}$ via the equation

$$x_{i-1} = Ax_i - x_{i+1}.$$

Everything on the right-hand side is known.  Thus, an eavesdropper can start with $x_k,x_{k-1}$ and iteratively compute $x_{k-2},x_{k-3},\dots,x_1,x_0$.  Once the eavesdropper has computed $x_0$, he knows the message $m_0$.

Another way to see that your proposed scheme is insecure is that there is no secret key.  There is no secret known to the recipient that is not also known to the eavesdropper.  Thus, if the recipient can decrypt, surely so can an eavesdropper.

So, your scheme is trivially broken under ciphertext-only attack.  It is even worse than an ordinary Hill cipher.  The attacker doesn't even need known plaintext.


RSA: revealing the modulus factorization by choosing a bad message I started reading the book Cryptanalysis of RSA and its variants by M. Jason Hinek and I stumbled upon a phrase that intrigued me:

  plaintext
  messages that are relatively prime to the modulus (i.e., $gcd(m, N) > 1$) should
  be avoided, since their ciphertexts $c = m^e\; mod \; N$ reveal the factorization of
  the modulus.

Firstly, if $m$ is relatively prime to $N$, shouldn't $gcd(m, N) = 1$?

Secondly, how is it possible to extract the factorization of $N$ by choosing a bad message $m$?

Firstly, it's not co-prime to the modulus, so $\gcd(m,N)$ would be greater than $1$.

Secondly, $N$ is the product of two (and only two) prime numbers $p$ and $q$, so if $\gcd(m,N)>1$, then you know $m$ is one of the factors (and prime factors) of $N$.


Multi-party encryption algorithm To give some foreground information: I acknowledge that I am a cryptography newb and not by any means an expert (and probably never will be).

In a recent CS class we had several assignments writing and implementing RSA and Diffie-Hellman. It was fun but it was exclusively two party encryption. I want to implement multi-party encryption. For example, a chatroom or IRC scenario where all parties involved send cyphertext to each other simultaneously. Looking around, I've seen that there are several libraries that accomplish this in other questions. But not just algorithms in general.

I can imagine something like this implemented in RSA and sending out public keys to everyone and simultaneously encrypting and decrypting messages multiple for every other member. For example, 3 people are in a chat room. Person A sends out "Hello guys" two unique cyphertext message that Person B and Person C receive and individually decrypt with their own private keys. This would work, but this seems inefficient and somewhat haphazard.

Is there a generally accepted algorithm that allows multiple parties to use public key encryption at once?

(Once again, this won't go to any production level system. This is just for my own academic curiosity.)

What is usually meant by "group encryption" is not what you are after. Group encryption algorithms strive to achieve the following: a given message is encrypted, and may be decrypted only if sufficiently many group members collaborate. This is not what you seek; what you want is a system such that a given message can be encrypted once and every member of the recipient group can decrypt it independently of all others.

The technical term for what you want is broadcast encryption. A specific and quite challenging case is what is done in Blu-ray discs, and is called AACS. Namely:

Each Blu-ray reading device has its own private key.
Disc contents ought be readable only by allowed devices (this is the "recipient group") but there are billions of them.
It is impractical to include in the disc some data specific to each target device (same disc for everybody, and too many target devices).
Communication is one-way only (devices are offline, so the disc contents must be sufficient).
Media producers wish to retain some "revocation capability" so that the contents of new discs cannot be read by some known "cracked" devices, while still being readable by other devices which (that's the crucial point) cannot be "updated" in any way (since they have no network capability).

For small groups (as a chat server, with only a few dozen recipients), the problem is rather easy:

Have each group member own a public/private key pair.
Make a symmetric group key K, known to all members by virtue of sending to each member the encryption of K with his public key.
To add a group member, just send him K encrypted with his public key.
To remove a group member, since forgetfulness cannot be enforced, you have to create a new group key K' and send it to all remaining members.

The biggest cost in that system is group key renewal, which is necessary only when a member must be removed, and the cost is proportional to the size of the group (an RSA-encrypted value with 2048-bit keys is 256 bytes, which is very tolerable as long as groups are no larger than, say, a few hundreds of people).


How secure is the AES master key if Round Keys are found If an attacker finds some round key of AES256, is it possible to find the master key?

How safe is the master key if an attackers finds multiple round keys?

If an attacker find some round key of AES256. Is it possible to find the master key ?

If the attacker is given a single round key from an 256 bit AES key, it is infeasible to reconstruct the full key (even if you have access to chosen plaintext/ciphertext against the full key).

This single round key reduces the number of possible AES keys from $2^{256}$ to $2^{128}$; however a search over the remaining 128 unknown bits would be computationally infeasible.  In addition, there is no obvious way to use you single known round to aid a Pt/Ct attack, because while there's a subkey which you know the key, there are 14 subkeys which you have no information on (AES-256 has 14 rounds, but 15 round keys).  Known "chosen key" attacks on AES-256 involve modifying the key; there's no obvious way to exploit that here.

  How safe is the master key if an attackers finds multiple round keys?

That's different; if the attacker finds two adjacent subkeys, then it's game over; he can trivially reconstruct everything.  For AES-256, each round key is an easily computed function of both the previous two round keys, or the next two round keys; hence with two adjacent round keys, you can reconstruct everything.  In fact, some hardware AES-256 implementations store two subround keys; the first two for encryption, and the last two for decryption; they reconstruct all the other round keys on the fly during the en/decryption process.

Now, what if the attacker finds two subkeys, but they're not adjacent?  Well, that's not quite as clear.  My instincts tell me that would be safer to assume that the attacker is able to recover everything, but how easy that really is might depend on how close the exposed rounds are; if they have a gap of one, you ought to be able to trivially reconstruct the round key between the two; if what's exposed is the first and last round keys, it might be a tad trickier.