Are there any practical use cases for performing homomorphic operations on encrypted Strings? Does anybody know which practical use cases there are to operate on encrypted strings? Even niche problems that can be solved using homomorphic encryption on strings are interesting to me, but not academic ones.

I believe you're talking about homomorphic encryption. It allows to have operations on encrypted data.

A simple use-case example:

Sometimes data has to be kept confidential (i.e. names, address, ... ). It could be that you want to perform computing on data but you're missing the computational power to do so. So you're outsourcing this computation to someone else (cloud computing), but now you have a problem with privacy and confidentiality, because in this case the data has to be handled confidentional.

That's where homomorphic encryption is useful. You encrypt the data and afterwards an untrusted server can perform computation on this data. After the computation you can decrypt the data again and a third party has not gained any knowledge of the data.

Examples in the case of strings:

You have a database with tables and you would like to add a new row with data. The database can be encrypted and hosted by an untrusted server (we're looking over the fact that this is maybe a bad practice). You can encrypt the data and add it to the database.
You want to compare a lot of data (strings), for example you want to be sure that database A ($D_a$) has exactly the same data as the database B ($D_b$). You can compare the data with homomorphic encryption by an untrusted third party. After the comparison you know if $D_a = D_b$.


For the hash computation of SHA-256, is it computed in parallel or series? I'm trying to write my own SHA-256 implementation in VHDL, which runs in parallel execution style

I have been using this as a reference to the SHA-256 algorithm: https://www.researchgate.net/file.PostFileLoader.html?id=534b393ad3df3e04508b45ad&assetKey=AS%3A273514844622849%401442222429260

In the hash computation where a, b, c, d, e, f, g, h, T1 and T2 are being calculated for 64 rounds, are these values being computed in parallel or sequentially?

For example, if we take the iteration number at 10 for the value e
e = d+T1
Does e take the value of d and T1 from the previous iteration 9, or the value of T1 which was just calculated in this iteration?

Thanks

SHA-256 has a basic building block which is not easily paralalized. Between blocks SHA-256 follows a Merkle-Damgard construction and needs to be computed sequentially.
You could build a tree-hash using the same compression function, and this will be secure and allow parallel computing but results would not be consistent with the SHA-256 standard.

https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction
https://en.wikipedia.org/wiki/Merkle_tree


Is this fixed length MAC unforgeable? Consider the following fixed length MAC for messages of length $\ell(n)=2n-2$ using a pseudorandom function $F$:

On input of a mesage $m_0||m_1$ ($|m_0| = |m_1| = n-1$) and a key $k \in \{0,1\}^n$, algorithm Mac outputs $t=F_k(0||m_0)||F_k(1,m_1)$. Algorithm Vrfy is defined in the natural way.

Is (Gen, Mac, Vrfy) existentially unforgeable under a chosen message attack? Why?

Forgeries can be made against this algorithm; here's how:

If the attacker gets the MAC with the two messages M0||M2 and M1||M3 as follows:

MAC(M0||M2) = Fk(0||M0) || Fk(1||M2)
MAC(M1||M3) = Fk(0||M1) || Fk(1||M3)

then, the attacker knows the values of Fk(0||M1) and Fk(1||M2), and thus can deduce the MAC of the message M1||M2 as:

MAC(M1||M2) = Fk(0||M1) || Fk(1||M2)

BTW: is this a homework assignment?


How to construct a variable length IND-CPA cipher from a fixed length one? Suppose we can construct a secure (IND-CPA) encryption scheme for fixed length messages. I was wondering if there is a natural way to extend this construction for messages of variable length such that it is still an IND-CPA secure scheme.

The typical way to make an encryption scheme work for variable length message is to use a mode of operation.

Since you are starting with an already IND-CPA secure cipher, even the often despised ECB mode will work. That said, you will still need padding to make the plaintext length a multiple of the blocksize. If adding padding is out of the question, a streaming mode such as CTR will work.


Is my understanding of CPA indistinguishability experiment correct? Following are steps to conduct Chosen Plaintext Attack (CPA) indistinguishibility experiment $PrivK_\mathcal{A,E}^{eav}(n)$.

$\mathcal{A}$ is the adversary $\mathcal{E}$ is the encryption scheme (Gen, Enc, Dec), $n$ is the length of the input.

a secret key SK is generated using Gen($1^n)$
$\mathcal{A}$ is given input of $1^n$ and oracle access to $Enc_{sk}(.)$ and outputs a pair of messages $m_0$ and $m_1$ of the same length.
A random bit $b$ is chosen.  $Enc_{sk}(m_b)$ is computed to form $challenge$ ciphertext $C$ given to $\mathcal{A}$.
$\mathcal{A}$ continues to have oracle access to $Enc_{sk}(.)$ and outputs another bit $b'$.
If $b'== b$ then $\mathcal{A}$ succeeded, otherwise $\mathcal{A}$ lost the game.

To better understand the experiment above, I decided to run it with simple values of my choosing:

secret key SK 10101010 generated with length n=8 by defender (one who wants security)
$\mathcal{A}$ is given an input $1^n$ =  11101110 by defender.  Using the length of this input, $\mathcal{A}$ comes up with $m_0 =  11111111 $ and $m_1$ = 00000000
Defender randomly selects $b$ = 0 and encrypts $Enc_{sk}(m_b)$ = $Enc_{sk}(m_0)$ = $Enc_{sk}(11111111)$ = 10111011 = $C$ challenge and given to $\mathcal{A}$
Using $C$ = 10111011 $\mathcal{A}$ tries to guess if it came from $m_0$ or $m_1$.  Guesses $b'$ = 1.  This means $\mathcal{A}$ lost the game.

My understanding is the adversary continues to pick different $m_0$ and $m_1$ values and has the defender encrypt them until he starts guessing correctly over 1/2 the time.

Is this a correct understanding or am I missing something?

There are a surprisingly large number of subtly different definitions of CPA indistinguishability.  What you describe in points 1 through 5 is one that I have heard of, though at the end of your post you make it 'iterative', in the sense that $\mathcal{A}$ can play the game over and over with $\mathcal{E}$ using the same secret key but fresh, independently-random values for $b$ for each game.  I have not heard of the IND game being set up iteratively like that -- usually $\mathcal{A}$ only gets one bite at the apple in terms of guessing $b$. Are you sure you meant to define it that way?

You also don't really define what it means for $\mathcal{A}$ to "continue to have access to the oracle" in point 4.  Do you mean $\mathcal{A}$ can make more chosen plaintext queries before it has to guess $b$?  If so, do they have to be of the form $(m_0, m_1)$ where only the encryption of $m_b$ is returned to it, or can they be individual messages?

Granting $\mathcal{A}$ up to $q_e$ queries of the form $(m_0, m_1)$ (i.e. so that every query is a 'challenge') before it has to make its guess for the value of $b$ is the more common Left Or Right (LOR) notion of IND-CPA.  BDJR'97 defines LOR IND-CPA (as well as several other notions of CPA security):
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.4734


How is SSL secure from rogue Certificate Authorities? There's one thing that I've never quite understood about SSL (which perhaps means I don't understand SSL at all): how is SSL secure from rogue Certificate Authorities?

This is probably best elaborated as an example:

Suppose company B buys a certificate C from certificate authority A.

Now, normally I would go to the website, B's servers shows me certificate C, I see it's signed by A, I trust A's root certificate, everything is dandy, and off I go to throw furious avians at malicious boars.

But suppose, for whatever reason, someone M persuades/tricks a different certificate authority N to issue them a certificate Q that looks just like certificate C but isn't.

Now if M does something to man-in-the-middle me, my understanding is that M's server shows me Q, I see Q signed by N, I trust N's root certificate, everything is dandy...except it's not because M can see all my plaintext, and is free to do with it as he wishes, including the other half of the MITM if he wants, passing the information on to B, etc.

(I know this is a classic MITM with an SSL twist, but I just wanted to be really clear with my logic just in case I missed something along the way that's relevant.)

I'm guessing that there's some other protection to mitigate against this, I presume? I hope? ...Please?

SSL offers protection against Man-in-the-Middle only if the client can make sure that what it believes to be the server's public key is, indeed, the true server's public key. X.509 certificates aim at providing this information, but this is relative that no rogue CA was involved. A "rogue CA" is here one of:

An evil or gullible root CA ("subverted" CA might be a more neutral term).
An evil or gullible intermediate CA, whose own certificate was issued by another CA (going up to a trusted root).

In fact, rogue CA are out of scope of X.509. It is a strange assertion, but its meaning is that X.509 works on damage containment:

If a mishap occurs, revocation is used to limit damage in time.
Though nothing technically prevents a rogue CA from issuing a fake certificate, it leaves traces; namely, the fake certificate points at the rogue CA for being, indeed, rogue. Fear of retaliation is supposed to keep CA honest and robust.

Even though a basic OS or Web browser tends to trust a hundred root CA or so by default, and that this trust is limited by the weakest of all of them, it so happens that "mishaps" involving a subverted CA are rare, about once a year or so. This means that the system kind of works in practice. Your understanding of the problem is correct, but experience shows that the mitigations which are in place (retaliation from legal/police forces, and revocation and OS/browser patches) make the attack "not worth it" for the attacker (it won't work for long, and it is risky), which explains why such attacks remain infrequent. I daresay that X.509 is not the weakest link in SSL-powered Web site (and SSL is not the weakest link either; the Web site is the usual problem).


Is the following scheme secure for different cipher Let's say I have

two keys K1 and K2.
two messages M1 and M2 of the same length.
Cipher (E,D)
3 ciphertexts: C11, C12,C22 where Cij = E(Ki, Mj)

In situation where attacker knows K2 and all the ciphertexts (which also gives him M2), can I choose a cipher to guarantee that attacker won't be able to compute neither the K1 key, nor first message.

I see three possible options:

Attacker won't be able to compute anything no matter what cipher was chosen [if cipher itself is "secure"].
Attacker will be able to compute either K1 or M1 for some ciphers.
Attacker will be able to compute either K1 or M1 for all ciphers.

Which one is correct?

P.S.: Saying "all ciphers" I mean "all more or less secure ciphers".

P.S. 2: I suspect that it is not the first option because at least for stream cipher attacker can easily compute the pseudorandom sequence for K1 if he knows M2 and C12. Then he will be able to decode C11 using this sequence. Is it true for other ciphers?

Actually, it's option 1: the attacker won't be able to compute anything, as long as a secure cipher is used.

The reason for this is that one of the requirements of a security cipher is resistance to known plaintext; that is, a message encrypted by the cipher with a key is secure even if the attacker can get the text of another message (and corresponding ciphertext) encrypted with the same key.

Your attack reveals M2 to the attacker and so the attacker has the pair C12 and M2 (a known plaintext pair) along with the ciphertext C11; this is exactly a known plaintext scenario; because a cipher is not considered secure unless it is invulnerable to a known plaintext attack, the attacker learns nothing about M1.

Note that your stream cipher example is not a counterexample to this, because this usage of a stream cipher is not particularly secure.  For example, even without any known plaintext, the encrypted messages C11 and C12 allows an attacker to compute the value of M1 exclusive or'ed with M2; depending on the language that M1 and M2 are in, this is often enough to deduce the values of M1 and M2 (and so this example isn't even secure against a ciphertext only attack.

Because of this, we never use a stream cipher in that manner; you should either use a distinct key for each message, use successive portions of the key stream to encrypt successive messages, or use a stream cipher that take a nonce (which modifies the stream cipher output).


Validating file type via magic of an AES encrypted .ts file would it be impossible to validate the file type via magic (file command for example) of an AES encrypted ts file? asking since the magic tests are looking for the sync byte (value of 0x47) each 188 bytes.

For a well-designed block cipher like AES, its output should be indistinguishable from random noise except to someone who knows the key, so this is not possible in the general case.

The larger problem here, however, seems to be that you are trying to use the magic tests to verify file integrity without having any other protections. Confidentiality (as provided by encryption) does not guarantee integrity, and vice versa. You should use an authenticated encryption mode that handles both or find another way to create a system that provides both confidentiality and integrity.


Shamir secret sharing with field 2^8 I want to split a message using Shamir's Secret Sharing by splitting each byte of it so the field I'm using is $2^8$.
Assume $(2,2)$ scheme, i.e., splitting it into $2$ shares and both of them are needed for reconstruction.
By having one share, can I guess the second (I have max $256$ options) and try to build the polynomial to reveal the secret? am I missing something here? so larger $k$ is important here?
Thanks!

There is a one-to-one correspondence between the value of the second share and the value of the secret: each of the $2^8$ possible values of the second share will give a (distinct) value of the secret among the $2^8$ possible values for it, and vice versa. Hence, guessing the second share is exactly the same thing as guessing the secret.


Can public key be recovered from ciphertext & encrypted private key? I'd like to implement something like a write-once public/private encrypted shared secret (no better quick description for the lack of terminology knowledge). I guess, I'm trying to implement HSM.

The scheme goes as follows:

given a secret (e.g. 512 characters long string)
generate a public & private key pair
encrypt the secret with the public key, for private key to decrypt
encrypt private key, to a hardware token key (OpenPGP smartcard, yubikey, FIDO secure key, TPM etc.) such that only the hardware token can decrypt it.
destroy public key, destroy plain copy of the secret key

The following properties are achieved:

given that public key does not exist, no other encrypted secret can be created for that private key.
both encrypted secret & encrypted private key can be stored externally and transmitted via insecure channels
to unlock the secret, both encrypted secret & encrypted private key must be presented to the hardware module that does on-chip decryption of the private key & decrypts the original secret which is presented back
a single hardware token can unlock unlimited amount of secrets (as they are stored externally)
it's not possible to tell which hardware token can unlock which secrets

Are there fallacies in above argumentation and is it a reasonable scheme?
Can a public key be derived from ciphertext & encrypted secret key?
Can a public key be derived from ciphertext & decrypted private key? (assuming hardware token is flawed and exposed it externally)

Essentially, I'm trying to create a multi-factor scheme to store shared secret which is used for full-disk encryption (LUKS / cryptsetup). With above to access unlocked encrypted disk I'll need to have:

ciphertext
encrypted private key
hardware token to unlock the first two (e.g. smart card)
smart card pin

But I can reuse the smart card for multiple secret/ciphertext/private-key combinations. Or am I unnecessary complicating things, and should simply encrypt the shared secret with a smart card?

Are there fallacies in above argumentation and is it a reasonable scheme?

It's not unheard of to encrypt secrets for them to be decrypted by a HSM or smart card. Usually though the smart card or HSM itself is used to encrypt/decrypt stored secret values. I know that at least one HSM does this, and all TPM's out there.

If you are accepting an unlimited number of secrets, then you seem to be generating an unlimited amount of key pairs. If any combination of public/private key pair is accepted then you may as well always use the same public key/private key pair.

As a side note it's strange to talk about a secret being 512 characters. That doesn't mean anything in cryptography (unless you mean C/C++ char values that essentially translate to bytes).

Can a public key be derived from ciphertext & encrypted secret key?

No, not if the encrypted secret key is presented as raw key material. Both outputs should be (almost) indistinguishable from random.

What you are trying to accomplish should be possible without a secret public key. Using cryptography outside its bounds is dangerous and should be avoided.

Can a public key be derived from ciphertext & decrypted private key?

Yes, almost certainly, unless the public exponent has the same properties as the private exponent. The modulus will be known so it is required to keep the public exponent safe. Most private key containers will contain CRT parameters and/or the public exponent. Furthermore, the exponent of the public key is often a known value such as 3 or the fourth number of Fermat (65537).

Or am I unnecessary complicating things, and should simply encrypt the shared secret with a smart card and that's it?!

Yes. That seems at least more reasonable than the scheme you've described above.

Even if the scheme is not directly wrong, it contains too many assumptions and leaves too many things not well described. It's unlikely that a direct implementation will be secure.


What is the difference between information-theoretic and perfect types of security? I'm having a hard time pinning down an exact definition of the difference between  information-theoretic and perfect types of security.  A rigorous definition seems elusive...

A. Wikipedia puts the difference down to the perfect type being a (poorly) defined special case of the information-theoretic type. "...a cryptosystem to leak some information" - yet I thought that these two particular security definitions only applied to breaking the encryption, rather than peripheral things like leaking the time the message was sent,
 it's length, etc.

B. An e-voting manufacturer uses entropy to quantify the difference as:-

$H(K | C) = H(K)$ – Perfect secrecy
$H(K | C) < H(K)$ – Information-theoretic security

Yet #2 can be rewritten as $H(K | C) = H(K) - \delta$, and that leads to #2 equalling #1 if $\delta \to 0$.

C. And finally a link from What's the difference between perfect security and unconditional security? is suggesting that "perfect security is the same as information-theoretic security".

Information-theoretic security means that any algorithm (even unbounded) has a negligible probability of breaking the security property (in the security parameter). This is the same as unconditional security: it does not rely on any computational assumption, and is not limited to probabilistic polytime adversaries.
A perfectly secure protocol is such that any (possibly unbounded) adversary has probability $0$ of breaking the security property. It is a special case of information-theoretic security: every perfectly secure protocol is information-theoretically secure, but the converse is not true.
To take a simple example, the distinction often appears when some secret value is masked with a random value, and we ask how hard it is to distinguish the masked value from a uniformly random value. Consider the following protocol: $x$ is an integer, say, between $0$ and $n - 1$. The game is as follows: we first sample a random bit $b$. If $b = 0$, we send a random value $r \gets X$ to the (unbounded) adversary, sampled from some set $R$, while if $b=1$, we sample a random value $r \gets R$ and send $x + r$ to the adversary. Fix a security parameter $k$. We say that the protocol has perfect security if the adversary has probability exactly $1/2$ of guessing the value of $b$ given the input, and that the protocol has information-theoretic security if the adversary has probability $1/2 + \mu(k)$ of guessing the value of $b$, where $\mu$ is a negligible function.
Suppose we identify $[0, n-1]$ with $\mathbb{Z}_n$ and define $R$ to be $\mathbb{Z}_{n}$ as well. The computation of $x + r$ is done over $\mathbb{Z}_n$. In this case, the protocol is clearly perfectly secure, as sampling $r$ from $\mathbb{Z}_{n}$ and returning $x+r$ gives exactly the uniform distribution over $\mathbb{Z}_{n}$, for any $x$.
On the other hand, suppose we set $R = [0, 2^{k} \cdot n]$ and compute $x + r$ over the integers. Then, it is easy to show that any (possibly unbounded) adversary has probability at most $1/2^{k}$ of distinguishing a sample from $R$ from a sample from $x + R$ (the statistical distance between these sets is $1/2^{k}$). Since this is a negligible function in $k$, this variant satisfies information theoretic security, but not perfect security.


Definition of perfect secrecy using ciphertext This week my professor in class taught us the definition of perfect secrecy. He said that for any ciphertext the probability that it might have come from any message in the message space should be equal.

$\Pr_{k\leftarrow Gen}[Enc_k(m)=c]=\Pr_{k\leftarrow Gen}[Enc_k(m')=c]$

He then said to think of the possibility where we vary the ciphertext and not the message. I think what he said might be interpreted as that the probability that a message encrypts into a ciphertext should be equal for all ciphertexts.

$\Pr_{k\leftarrow Gen}[Enc_k(m)=c]=\Pr_{k\leftarrow Gen}[Enc_k(m)=c']$

I thought about this but haven't been able to relate it to the original definition. I wanted to prove the equivalence or get a better inference of what he said. I don't know if this is even true. So a counterexample might be more useful.

If I haven't written any detail please let me know.

I think they are similar but not equivalent.

The first condition says that for any ciphertext $c$ all messages $m$ have equal probability to encrypt to $c$. The second says that for any message $m$ all ciphertexts $c$ have equally probability of encrypting $m$.

So I think you can demonstrate non-equivalence as follows:

Imagine a (somewhat contrived) scheme satisfying the first condition but not the second: The scheme has two disjointed sets of ciphertexts $C_0$ and $C_1$. Concretely, consider one-time-pad where keys and ciphertext contain one extra bit, simply indicating if we are in $C_0$ or $C_1$. Now, assume we pick the extra bit to be 0 with probability 1/3 and 1 with probability 2/3.

Now if $c \in C_0$ and $c' \in C_1$ it is clearly not the case that
$$
Pr_{k \leftarrow Gen}[Enc_k(m) = c] = Pr_{k \leftarrow Gen}[Enc_k(m) = c']
$$
because the probability that $Enc_k(m) \in C_1$ is twice as big as $Enc_k(m) \in C_0$.

Alternatively, I think you can show that condition two implies condition one. I.e. condition one is more general than condition two.


What makes this mixer function resistant to differential cryptanalysis? I recently learned how differential cryptanalysis works, and decided to have a play around with testing various designs for resistance against attack.

My testing algorithm is essentially to loop through all $A$ and $B$ values for all potential input differentials ($\Delta A$ or $\Delta B$), and count how many distinct output differentials are seen for each input differential. To ensure its efficacy, I ran it against FEAL's gbox and got the expected value of 1 (0x02) at input differential 0x80.

Testing some other randomly conjured up designs resulted in all sorts of interesting weaknesses, until I stumbled upon this particular construction:

Where $S$ is a simple s-box built from fixed 8-bit lookup table. My results from this construction appear to be immaculate: every input differential has a perfect score of 255. I also noticed that removing any single instance of $S$ negates this property.

Am I correct in saying that this is resistant to differential analysis? What is it that produces this apparent resistance? Is there a classification for this kind of mixer construction?

From your picture I deduce that $A$ and $B$ are both 8 bits.
So this construction can be seen as a $16 \times 8$ bit S-box (not bijective). The fact that it's not square is probably what is causing confusion.
Usually, for SPNs, invertible S-boxes are used. Non-invertible S-boxes are less common, but they certainly have applications.

One of the things we can do to determine the weakness of an S-box with respect to differential cryptanalysis, is to look at the difference distribution table (DDT).
That's just a table where each row (column) represents an input (output)  difference. The entries are equal to the amount of times the output difference occurs for the  input difference. If a certain input difference $\Delta X$ often leads to output difference $\Delta Y$, then this is considered a weakness.

So, how is the value you compute related to the DDT?

  My testing algorithm is essentially to loop through all A and B values
  for all potential input differentials (ΔA or ΔB), and count how many
  distinct output differentials are seen for each input differential.

For a given input difference $(\Delta A, \Delta B)$ (this corresponds to a row), you compute the amount of columns (output differences) that have a nonzero DDT entry on that row.
For S-boxes that are not square, this doesn't really tell us a lot about the strength with respect to differential cryptanalysis. For square S-boxes, it may be some kind of average indicator (which is probably not very useful).

It does explain why you get 255 though. The amount of columns in the DDT equals $2^8 = 256$. The output difference $\Delta Y=0$ only occurs when $\Delta X = 0$. I assume you didn't count those (the result would be 1). This means that there are at most $256 - 1 = 255$ nonzero entries in a row.
For common $8 \times 8$ S-boxes that would indeed be theoretically optimal (unfortunately that's not possible, even in theory).
But in your case, given that there are $2^{16} = 65536$ (256 times as many) input values, you can indeed get 255 nonzero entries.

(Sorry if the above was not entirely correct, I may have misunderstood the way you compute the "score".)

I computed the DDT for this structure, scaled to an $8 \times 4$ system. With $S$ a very good $4 \times 4$ S-box, the result isn't a very good S-box. Of course it's dangerous to extrapolate to a larger size, but I see no reason why this structure would be particularly good.


Two working decipher keys giving various, valid results for one ciphered message - is it possible? Let's assume following scenario:

There's a ciphered message. Two decipher keys (let's name them A and B) are known.

Message deciphered with key A gives valid result - normal text but with no secret information. Let it be a poem or other meaningless content.

The same message deciphered with key B gives the right output, the real secret message revealed.

Please tell me, is it possible (or well-known and existing method/algorithm), or just a work of fiction? I've read about it in some novel a long time ago and tried to figure it out on my own, but with no result. But I'm rather ignorant in terms of cryptography so I might just miss something obvious.

Thank you in advance for any help - just a simple name of ciphering method or link to Wikipedia or something will be enough. I don't even dare to ask for the full and detailed explanation.

This property can be achieved with a One-time pad.

  "In fact, it is possible to "decrypt" out of the ciphertext any message whatsoever with the same number of characters, simply by using a different key, and there is no information in the ciphertext that will allow Eve to choose among the various possible readings of the ciphertext."

This is nicely shown in this example from Wikipedia (section "Attempt at cryptanalysis").


Using chi square for distinguishing between compressed and random data I am trying to find some measurement for identifying and distinguishing between compressed and random data. I tried this first by computing the entropy of such data, the entropy value is extremely high (almost maximum) in both cases, so that way does not seem to work as a distinguisher.

I read about the chi square algorithm but I've never used it (actually I still have some problems with interpreting the results). Does anybody know if this algorithm can lead to better results?

The NIST tools are a good starting point.

There is no general-purpose algorithm that will always distinguish compressed from random data

However, if you want to try the chi-squared test, you can compute a histogram of the frequency of all byte values (how many 0 bytes you saw in the data, how many 1 bytes you saw, etc.), and then use the chi-squared test to test whether this appears to deviate from what you'd expect for uniform-random data.


What is the point of digital signatures if confidentiality is violated? Lets say we use RSA as the signature method.

Alice wants to send a message to Bob and uses RSA signing. For that she signs her message with her private key. But everybody could now have access to her message if one just decrypts the signature with Alice's public key.

What is the point of digital signatures if confidentiality is violated?

Digital signatures are not designed for confidentiality. For the simplest counterexample to the implicit conclusion that there is no point to digital signatures without confidentiality, consider the use of PGP signatures. People may sign a message that they send to a public mailing list, allowing others to verify that they indeed said that and not an imposter pretending to be them.
Also, you seem to be misunderstanding how digital signatures work. It is not encryption that you decrypt to verify. A digital signature is a mathematical operation on a hash of the message that you verify is valid for the message. You don't recover the message itself from the signature.


Where can I double check my elliptic curve results? I am trying to do some elliptic curve calculations by hand, just to refresh myself on how the system works. I calculated some points and did some operations by hand. I am trying to double check my work with some web calculators, but I have tried several different calculators and each gives me a different result...

Is there a verified implementation or library somewhere that I could use, rather than pet projects that people have on their websites?

I am working with the curve

$y^2 \equiv x^3 - 2 \pmod 7$

I calculated the points to be

$(3,2),(3,5),(4,1),(4,6,),(5,2,),(5,5),(\infty, \infty)$

I calculated $(3,2) + (5,5) = (3,5)$ I'm fairly confident in this answer.

The problem I'm struggling with however is $(3,2) + (3,2) = (3,5)$. I have tried several times and have gotten the slope between the two points to be $27/4$. When I convert this to an integer $\mod 7$, I get the slope equal to either $3$ or $5$. When $m=3$, I get the point $(3,5)$. When $m=5$, I get the point $(5,1)$, which isn't on the curve, so I'm assuming I'm doing this step incorrectly.


Asmuth-Bloom's threshold secret sharing scheme I was learning Asmuth-Bloom's threshold secret sharing scheme. I was working out an example as given in this Wikipedia article.
As per the example, the secret, d is 2, the number of shares, n is 4 and threshold, k is 3.
The list of relatively prime integers, m is [3,11,13,17,19] and it follows the criteria $m_1.m_2.m_3 > m_0.m_3.m_4$.
As per the example, the shares are generated as $1$ $mod$ $11$, $12$ $mod$ $13$, $2$ $mod$ $17$ and $3$ $mod$ $19$. The example then regenerates the secret using the shares $1$ $mod$ $11$, $12$ $mod$ $13$, $2$ $mod$ $17$.

However, when I tried to reconstruct the secret using two shares ($1$ $mod$ $11$ and $3$ $mod$ $19$) I could regenerate the secret, which is against the threshold property.

I tried for multiple examples and this was true for all cases.

Can somebody explain if I am wrong somewhere or if there is a limitation in the threshold scheme?

I don't believe that, in the example you gave, you can reconstruct the secret using two shares.

$d + \alpha m_0$ is in the range $[0, 2431)$; using the two shares $1 \bmod 11$ and $3 \bmod 19$, you can determine that it is one of $155, 364, 573, 782, 991, 1200, 1409, 1618, 1827, 2036, 2245$, however you have no further information about which it might be.  Since these include values consistent with all possible values of $d$ (which must be between 0 and $m_0-1$), we can conclude that the attacker cannot determine the value of $d$, or even eliminate any potential value of $d$.

On the other hand, if the attacker knows the probability distribution $\alpha$ was chosen from, he can obtain some probabilistic information about $d$.  In the case in question, we see that there are four possible values of $\alpha$ that is consistent with $d=1$ and $d=2$, while there are only three possible values that is consistent with $d=0$.  If the attacker knows that $\alpha$ was chosen uniformly, he may conclude that while $d=0$ is possible, it is somewhat less probable to be the shared secret than either of the other two.

In contrast, Shamir's Secret Sharing doesn't leak any such probabilistic information for any number of shares less than the threshold.


In what sense addition modulo $n$ ($n>2$) isn't linear in the field $\mathbb{F}_2$? I've been reading the Reason why “XOR” is a linear operation, but ordinary “addition” isn’t? question, in which one of the answers states that addition modulo $n$ ($n>2$) is linear in $\mathbb{Z}_n$ but not in $\mathbb{F}_2$, it also states that - conversely - $XOR$ is linear in $\mathbb{F}_2$ but not in $\mathbb{Z}_n$($n>2$).

But in what sense?

I mean, how can I think about a $n$ ($n>2$) modular addition in $\mathbb{F}_2$?

When I've to sum modulo $n$ I usually sum the digits modulo $10$ (or directly reducing them modulo $n$ before doing the sum) and then reduce the result modulo $n$

F.i.: Taking $n = 3, x_1=2, x_2=2$

$$x_1+x_2 = 2+2 = 4 = 1 \pmod 3$$

But how can I think about a sum modulo $n$ in $\mathbb{F}_2$ ? And why it isn't linear in $\mathbb{F}_2$?

Conversely, how can I think about a $XOR$ in $\mathbb{Z}_n$, and why it isn't linear?

Sicne your question is refering to an answer on this site, I will not quote the entire answer here. But the crucial point is there in the last paragraph:

  If none of that made any sense to you, that's OK. You just need to read up about Abstract Algebra, and Fields, Rings and Groups. It's a fascinating and beautiful area of mathematics, and much of cryptography will make no sense without at least some understanding of it.

I can only suggest you do the same and carefully read the answer again, because $\mathbb{F}_2$ was not mentioned in the answer at all. It contained statements about (finite) fields of Characteristic 2, which are $\mathbb{F}_{2^k}$ for any integer $k$.

If you carefully read the statements again, you will see that $\mathbb{F}_2$ actually meets both criteria, being a finite field of characteristic 2 and being a ring of the form $\mathbb{Z}_n$. In fact, XOR and modular addition are the very same group operation. It is quite obvious in this example, but could easily be checked by writing down the operator tables.

Considering your real question about linearity in finite fields, let's look at $\mathbb{F}_4$, which has characteristic 2, and is also described in the according Wiki article.
So we got $\mathbb{F}_4 = {0,1,a,1+a}$, where addition is just the normal addition of polynomials, coefficients are reduced modulo 2, and multiplicaion is the regular multiplication of polynomials modulo $X^2+X+1$.

Unfortunately, the answer in question has a few points, which only make sense under a certain point of view. Basically, if you consider a number in a binary format, and then interpret each bit as a coefficient in $\mathbb{F}_{2^k}$ (see above construction for $\mathbb{F}_4$, with 2 coefficients before $a$ and a constant $1$), then XOR-ing numbers can be interpreted as the actual addition of polynomials in that finite field. However, you can't express XOR in $\mathbb{Z}_4$ as a linear equation - which has a quite different meaning than linear function in algebra. Analog, you can't express addition modulo 4 (in  $\mathbb{Z}_4$) as linear equation in the field $\mathbb{F}_4$.

As a final note I can only say: Notation and details matter a lot in algebra. Especially if you don't understand the exact statement, this becomes even more important to avoid confusion  - or even worse, that you learn something that is just false.


Security game oracle queries Concerning private key (symmetric) IND-CPA game definition:

Attacker $A$ queries the encryption oracle polynomial number of times.
$A$ sends the challenger $C$ a message pair $m_0$ and $m_1$. $C$ picks a random bit $b$ and sends back to $A$ a cyphertext $Enc(m_b)$.
$A$ makes further queries to the encryption oracle polynomial number of times.
$A$ tries to guess $b$.

An encryption system is considered broken if $A$ has a non-negligible advantage in guessing $b$.

My question is:

Let's denote the original game as $Game_0$. Now we remove step (3), i.e. $A$ cannot query the oracle after receiving the challenge cyphertext. We call this $Game_1$. Is it true that if $A$ can break $Game_0$, she can necessarily break $Game_1$? In other words, does any encryption system exist such that $A$ cannot break $Game_1$, but can break $Game_0$ with the extra queries after receiving the cyphertext?
Similarly, now we remove step (1), i.e. $A$ cannot query the oracle before receiving the challenge cyphertext. We call this $Game_2$. Is it true that if $A$ can break $Game_0$, she can necessarily break $Game_2$? In other words, does any encryption system exist such that $A$ cannot break $Game_2$, but can break $Game_0$ with the extra queries before receiving the cyphertext?

I will think more about a proof/counterexample for #1, but here is a counterexample for #2.

Let $\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec}$ refer to a CPA-secure encryption scheme with message space $\{0,1\}^\lambda$, and define the following modified scheme:

$\mathsf{KeyGen}'$: run $sk \gets \mathsf{KeyGen}$ and sample $m^* \gets \{0,1\}^\lambda$. The key is $(sk,m^*)$.
$\mathsf{Enc}'( (sk,m^*),m)$: if $m = m^*$ then output $\star$; otherwise output $(\mathsf{Enc}(sk,m), m^*)$.
$\mathsf{Dec}'( (sk,m^*), c)$: if $c = \star$ then output $m^*$; otherwise parse $c$ as $(c_1,c_2)$ and output $\mathsf{Dec}(sk, c_1)$

The idea is that $m^*$ is a special message whose encryptions are easily distinguishable. But the only way to learn $m^*$ is to query the encryption oracle.

Suppose you play the CPA game with pre-challenge queries. Make any query and the response will include $m^*$. Now choose as your challenge $m_0 = m^* \ne m_1$. You can determine $b$ exactly by seeing whether the challenge ciphertext is $\star$.

Suppose you play the CPA game without pre-challenge queries. With no information about the "magic" plaintext $m^*$ you will not be able to make $m^*$ one of the challenge plaintexts except with negligible probability. So the challenge ciphertext is a regular $\mathsf{Enc}$-encryption of $m_b$ and the game can be reduced to the CPA game for $\mathsf{Enc}$.

Update:
For #1 the best counterexample I can do is a stateful encryption scheme. It's a bit of a cheat but one could argue that the "right" definition of security for stateless encryption should also be the "right" definition for stateful encryption.

Let $\textsf{Enc}$ refer to a standard CPA-secure encryption, and define the following encryption scheme with internal state $st$, initialized to $\bot$:

$\textsf{Enc}'(sk,m)$: output $(\textsf{Enc}(sk,m), st)$; update $st = m$.

Every time you encrypt, you are also told the plaintext that was used in the previous ciphertext! So breaking CPA with post-challenge queries is trivial.  But with no post-challenge queries, things reduce to the CPA security of $\textsf{Enc}$ in a straight-forward way (the reduction already "knows" the plaintexts used for pre-challenge queries, so can add them on appropriately).


Is XOR-and-SUM inherently sequential? I have been thinking recently about inherently sequential functions. In trying to wrap my head around them, I tried to come to the simplest possible function that looks inherently sequential to me. For didactical purposes, I'd like some feedback.
Consider two sequences of 64-bit integers: $a_1, \ldots, a_N$ and $b_1, \ldots, b_N$. Now, consider the sequence of 64-bit integers $x_0, \ldots, x_N$ defined by
\begin{align}
x_0 &= 0 \\
x_{n + 1} &= (x_n \oplus a_{n + 1}) + b_{n + 1}
\end{align}
where I use $\oplus$ to denote bitwise-XOR and $+$ to denote the sum modulo 64 bits. Intuitively, $x_N$ is obtained by a long sequence of alternating XORs and sums. I am wondering: is the computation of $x_N$ inherently sequential?
I cannot seem to easily see how one could achieve $x_N$ faster than just going through each operation. But, I realise that I might be missing something.
Here I am interested about both theory and practice: I'm curious to know if this function can be proved to be inherently sequential, but also if this function could be safely assumed to be inherently sequential, just like, e.g., cryptographic hash functions are safely assumed to approximate well a random oracle.
More specifically
I'll try to be more specific. What I am wondering is whether or not all bits in $x_N$ can be computed by a polynomially-sized boolean circuit whose critical depth is smaller than that of the trivial circuit, sequentially applying XORs and sums.

This is actually touching to the notion of "rotational cryptanalysis", except you're missing the rotation part.
We usually use (modular) "Addition" or "Add" instead of "Sum", Add-Rotate-Xor are the core functions used by the so-called "ARX"-based algorithms which nowadays constitute an important part of the "fastest" stream ciphers (See Salsa/Chacha20, or the more controversial Speck, etc.) and hash functions (Blake, etc) out there.
The main idea behind ARX ciphers is that (modular) addition is not associative with the rotate, nor the XOR operation, and thus are difficult to simplify. (Exactly what you're interested in here.)
However skipping the rotation part as you did in a ARX design is an issue because it has been shown that systems made only of additions and XOR are broken since they can be reworked from rightmost to leftmost bit. To see the gory details I'll refer you to this Paul & Prenel paper that explain why this is broken: https://eprint.iacr.org/2004/294.pdf
As you'll see in the linked paper, A(R)X construct are a pain to study because they do not have nice algebraic structure like AES, RSA or ECC, which sadly means that they are usually less anayzed. This is why some cryptographers believe it would be best to avoid ARX designs when designing new cipher and schemes, and we've seen cipher such as NORX or Gimli which are explicitly not-ARX designs.
Interestingly, using only Additions and Rotations, it is possible to emulate Xor, so the Xor can be removed in a "secure way" in ARX designs, unlike the rotation. (At the cost of a somewhat lower security bound though.)


Is there a time-space tradeoff attack for breaking symmetrical cryptos? Is there any known techniques for using time-space tradeoff for speeding up symmetrical crypto breaking? Kind of like rainbow tables speed up breaking hashes by using huge precomputed tables.

Is something similar possible for symmetrical cryptos like AES? If not, why? Is there a difference between block and stream ciphers in this regard? Couldn't you get at least a head start on brute forcing by searching through gigantic tables where a lot of plaintext "heads" have been pre-computed?

The idea you have is: lets say we have a known plaintext/ciphertext pair; can we use a precomputed table to speed up the recovery of the key?

Well, the main problem with that precomputed tables don't actually speed up the search time, if you count the time taken to generate the precomputed table.  What the table precomputation does is (for example) generate lots of key/ciphertext pairs (for a given plaintext), and store those in a table (in a clever way that makes the table much smaller than just storing each set individually.  That's the real meaning of the phrase "time/memory trade-off"; it doesn't reduce the amount of time taken by using memory, it reduces the amount of memory (in terms of table space) by making the table lookup harder.

Then, when given a plaintext/ciphertext pair, it checks the table to see that if that ciphertext appeared in a key/ciphertext pair; if so, you have a solid guess of the key.

Now, if the key/ciphertext pair never occurred during the precomputation phase, you won't find it in the table; hence to generate a table where a lookup has a $2^{-32}$ probability of finding a 128-bit AES key, you need to spend at least $2^{96}$ time; that's no better than brute force; and we already believe brute force is too hard.

So, you say, why then do we use rainbow tables?  Because we can spend the time to compute those tables once, and then use the same table multiple times.  So, if we have $2^{32}$ different crypto texts with $2^{32}$ different keys, with each crypto text containing the encryption of the same plaintext block (and that same plaintext block would result in $2^{32}$ different ciphertexts), we could (with the above $2^{96}$ precomputation) have a decent chance at recovering the key to one of those sessions.

Isn't that some benefit?  Well, in theory it might, but in practice, not so much.  Remember, we generally run ciphers such as AES within a mode, and the mode may not give us consistent access to the same plaintext across sessions.  For example, for CBC mode, the plaintext we present to the AES block cipher is effectively randomized; that means that you are quite unlikely to get the same plaintext used by even two different sessions, and so rainbow tables are not a win here; brute force is actually more efficient.


SPI Frame format of TPM1.2 Commands I have bought a TPM Chip: SLB9670.
It can be communicated via the SPI Bus.
What is the SPI frame format for firing TPM Commands with or
without arguments. I have read the TPM Main Specifications documents
but haven't found much help. Can someone please help me with this.

What you are looking for could be in the Data Sheet (be sure to read 5.5) for the hardware layer, or/and the TCG PC Client Platform TPM Profile (PTP) Specification for SPI frame format.

You'll also need to find out what commands to send. The specs are there, and it is rumored that some have rewired their brain to actually use it (I'm not in). More.


How is the curve equation used in ECC? I have a hard time learning exactly how the elliptic curve equation is used in the ECC.

$$y^2 = x^3+ax+b$$

If someone knows and could explain to me in simple steps how this is done or a link to it that would just be amazing. I know how point addition is done, so I know the mathematical side to it.

This is a high school project so it does not have to be very specific, just like a general idea.

In fact the equation is not used directly.

If you work in the field of integers modulo $p$, both the $x$ and $y$ coordinates are integers in the $0$ to $p-1$ range, so there are $p^2$ possible points. The equation tells you which points are part of the curve (the $(x,y)$ such that $y^2 = x^3 + ax + b$) and which points are not. In that sense, the equation defines the playground. The size of the curve (number of points which match the equation) is close to $p$, so the vast majority of possible points are not part of the curve.

However, if you just want to use the curve for adding points together, then the usual formulas (as seen e.g. here) do not use the curve equation: the $a$ parameter appears only in the formula for doubling, the $b$ parameter does not show up at all. The curve equation is used implicitly by virtue of the input points being part of the curve, i.e. fulfilling the equation.

So, in practice, the curve equation is used to verify that the input points are valid, i.e. part of the curve. When doing elliptic-curve Diffie-Hellman, each party sends to the other a curve point, as two coordinates $x$ and $y$. When receiving such values, you must first check that they define a point which is indeed a curve point, i.e. you compute both $y^2$ and $x^3 + ax + b$ to see if they match. If they don't, then the input points are not on the curve (or, rather, not on the curve you believe them to be), and bad things may occur.

As an optimization, the systems who do ECDH may send to each other only the $x$ coordinates. Indeed, when you receive $x$, you can compute $x^3 + ax + b$, which is equal to $y^2$. By computing the two (at most) square roots of that value, you recover $y$ and $-y$. In other words, from $x$ alone, you can use the curve equation to work out the (at most) two curve points which have that $x$ value. This is sufficient to do the ECDH. This is an optimization because it allows the two systems to send less bytes over the wire. This is called point compression and it directly uses the curve equation.


What is the actual difference between security through obscurity and true encryption? In an abstract sense, aren't both the same?

Don't their definitions boil down to the following?

security through obscurity:
trying to make sure some information cannot be obtained without knowing the secret method
encryption:
trying to make sure some information cannot be obtained without knowing the secret key

That secret method of STO is, in an abstract meaning, just a key.

So, is the actual difference that in encryption the connection between the key and the information is mathematically sound while STO uses something so abstract that attempting to describe it mathematically is not feasible and its security basically relies on that?

We often mock "security through obscurity", but it is not without value, especially in today's web environment.

Most attacks today are statistical in nature:  a virus attempts to infect 10,000 computers by blasting out random attacks.  If it infects even two more computers out of those 10,000, it has achieved its goal.

Those viruses are aggressive in volume, not precision.  They don't all do a port scan, analyze the responses to determine OS version, they don't do a vulnerability assessment, then launch a precise attack the way a human would.  Instead, they try to exploit a common weakness - a buffer overrun exploit in PHP, or SQL injection vulnerability in a Wordpress plugin.  Anything the system administrator does to alter their defaults:  changing the base URL from "index.html" to "index.htm", or changing the database names in MySQL, might keep a particular automated attack from harming his system.  It doesn't remove the vulnerability, it merely changes it so that an attack relying on the defaults will not succeed.

Will this keep out a determined attacker?  Of course not.  But it will reduce the number of low-level threats that can still surprise anyone if they exploit a 0day vulnerability.  And those low-level threats can quickly escalate to be every bit as damaging as an Advanced Persistent Threat.

That's why obscurity, which I define here as to be "any implementation settings changed from the default", still improves your overall security picture.  It may only reduce a few particular attacks, or delay them by a few days, but those days can be enough to get a real patch installed.  In practice, preventing a threat from becoming a successful attack is the true job of security, regardless of whether it was based on bad theory.


Is finding collisions in a part-hash not often enough a bad problem? My situation: I've been working now for a couple of months on my own unique hash function, I've changed it many times and had two main versions but I won't bore anyone with the details of my work; at least not here. I'm here to ask a question that's specific and helpful to anyone attempting to design a cryptographic hash. (I hope)

Now I'm more than aware that simply being a normally-distrusted random function, does not make a cryptographically secure hash.

MY QUESTION however IS:
If collisions are found LESS often than would be predicted by a random function, is this an alarm-bell that we may have some empirical weakness?

Allow me to elaborate:

In my tests, I found that any given set of 32 bits  (from a set position in the hash) from an array of unrelated input (or related input but different output) hash functions were indeed seemingly random until I noticed that: In order to find a collision: one would have to go through about 89000 different attempts on average (although obviously the numbers swayed massively). Since the birthday bound is only 65536 (or ~77000), something seems amiss. Since my testing involved using batteries of different PRNGS to create the inputs aswell as non-random methodical ones and I ran these tests hundreds of millions of times, meaning I've made literally billions of hashes... I don't think it's my testing that is flawed or that my sample sizes are too small.

I can say with almost 100% confidence, that it is taking more attempts to find a collision than would be expected of a truly random (ideal) output.

Side note: I tried with 16 bit, 40 bit samples, etc and always came up with the same results: collisions were LESS frequent.

2nd Side note: When describing the hash as a PRNG or indeed a PRNG using the hash, it passes birthday-spacing tests on the dieharder suite just fine (I find this bit very confusing).

If anyone can explain this strange phenomenom (the passing on dieharder but failing on my own tests) then extra points but what I want to know is:

So given we do have a "Desired probability of random collision" in a given hash (and logically speaking any smaller word within that hash) then what happens when in a given word (and presumably the hash in general) collisions are found less often than expected? What info do we gain about the likely hood of pre-image attacks? Non ideal distribution or any other info in fact?

I know this is probably a hard question to answer but maybe not.

There are different birthday bounds when we draw independent uniform random integers less then $d$  (for some large $d$, including $d=2^{32}$ of the question) and watch for collision(s):

In crypto, we often consider the bound of $\sqrt d$  ($65536$ for $d=2^{32}$) draws, at which there is a fair probability of collision: $p\approx1-1/\sqrt e\approx39.3\%$. This is also about the number of draws for which it is most likely that the first collision will occur.
The number of draws starting at which it becomes probable ($p\ge1/2$) that there is at least a collision; that is about $\sqrt{\log4}\sqrt d$  ($\approx1.17741\sqrt d$ , $\approx77163$ for $d=2^{32}$); more precise formulas are here.
The average (equivalently: expected) number of draws at which the first collision appears; that is about $\sqrt{\pi/2}\sqrt d$  ($\approx1.25331\sqrt d$ , $\approx82137$ for $d=2^{32}$); more precise formulas are here.

The difference between the three is because mode, median and mean of a discrete probability distribution are not the same thing (sort of: we rarely have a collision much before $77163$, and often have the first collision way after that, hence the significantly larger mean). The confusion is probably what causes the discrepancy in the question.

Image credit: Cmglee; source; Creative Commons license.

If for some would-be hash function we consistently observe collisions much less frequently than predicted by these bounds, for would-be random input (restricted to a domain still much larger than the output domain is), then

our would-be random input (or its domain) is biased
and our hash function is not secure in the random oracle model, in a manner that is related to the bias in our random input.


Least-weak way to authenticate using only AES ECB/CBC I have an embedded application that needs to occasionally get secure updates from a server. The only crypto library I have available for the chip is an AES-256 cipher (ECB and CBC, encrypt/decrypt).

Is there any worthwhile way to authenticate the message using only these functions and simple checksums? If I just did something like a 32 bit checksum of the plaintext and appended it before encryption, would that be vulnerable to attack (other than being only 32 bits of protection)?

Is there any worthwhile way to authenticate the message using only
  these functions and simple checksums?

As usual, of course there is: AES-CCM!

AES-CCM basically is CTR mode with a tagged-on CBC-MAC and length prepending. You can implement CTR trivially using your ECB primitive and CBC-MAC shouldn't be too hard to implement given a CBC primitive and direct function access.
If implementig CTR is infeasible, CBC should do the job just as well.
If you want to go fancy (and don't live with length-prepending) you can also go for AES-EAX although it's a bit more difficult to implement.

  If I just did something like a 32 bit checksum of the plaintext and
  appended it before encryption, would that be vulnerable to attack
  (other than being only 32 bits of protection)?

No, this is a bad idea. Not only is a checksum usually not safe in the sense that a proper cryptographic hash would be, but also is this composition already insecure as fgrieu explained much better than I ever could in his answer to "Why is plain-hash-then-encrypt not a secure MAC?".

Relevant standards: CCM: RFC 3610, NIST SP 800-38C (PDF); EAX: The original specification


How does Diffie-Hellman apply to strings? I have been doing a lot of research on Diffie-Hellman, and I understand how Alice and Bob are able to get a shared g^ab using both of their private keys. However, I am unsure about how this can be applied to passwords (strings). I assume you have to do something with the hex version of both the password and g^ab, but what? Any help would be much appreciated!

No, DH does not apply to strings. However, what you are likely trying to achieve is to perform Diffie-Hellman with authentication. For that you can use a PAKE protocol, which stands for Password Authenticated Key Exchange (Wikipedia obviously made a bit of a mess of the naming, Password-Authenticated Key Agreement would be PAKA, not PAKE).

In such protocols DH is performed and the password authentication is part of the protocol; if the password is not correct then either the protocol exits early or the shared secret is not computed to the correct value, which means that subsequent authentication will fail.


Responsibility of quantum-weak cryptography At this point, should we consider it irresponsible to design new systems that assume hardness of problems already known vulnerable to quantum computers, such as factoring of large numbers or discrete logarithms? Likewise, do we have a moral obligation when answering questions about cryptosystems based on these, to ensure readers are aware of the coming insecurity?

Should we consider it irresponsible to design new systems that assume hardness of problems already known vulnerable to quantum computers, such as factoring of large numbers or discrete logarithms?

Some would answer that it is irresponsible to design new systems at all, regardless of the threat of quantum computing. It's hard to prove something is secure even in a classical computing setting, as it requires valuable time from highly skilled people.

Others might argue that Quantum Computing might never take off and become a real thing, and so designing post-quantum algorithms is a waste of time.

We usually (arguably have to) assume the worst-case scenario when designing algorithms, and the worst-case scenario in this day and age implies a quantum computer. You could design new cryptosystems based off of problems that are known to be vulnerable to quantum algorithms and hope that quantum computers never become relevant.

If you are disinclined to include "hope" in the justification for your design, then you need to avoid problems that are already known to be broken. This means using hard problems other then the discrete logarithm/factorization.

  Likewise, do we have a moral obligation when answering questions about cryptosystems based on these, to ensure readers are aware of the coming insecurity?

It depends on your specific audience.

If it's just someone who is asking a question on crypto.se about discrete logarithms in general, then it may (or may not) be off-topic to bring up quantum computing.

Anyone who is capable of designing their own public key algorithms is probably already aware of the threat of quantum computers and hopefully does not need to be told.

Someone who is designing a new protocol should be informed that the standard go-to primitives may not provide long term security against quantum computers. Again, they may already be aware.

If your audience is someone who is instantiating a specific, already defined protocol that uses DH or RSA, then telling them that DH or RSA is broken against quantum computing is possibly not helpful or relevant - it's not up to them to make such design changes. Although, such information may cause them to select a new protocol to implement.

I would say that if it the information is relevant and they are unlikely to know it already, it certainly should be mentioned.


Why is xor'ing plaintext blocks and encrypting the resulting checksum not a secure MAC using CTR mode? Consider message $P$ being split into $n$ blocks that match the block size of the underlying block cipher. The message has fixed length and the length is always a multiple of the block size.
Encryption using CTR mode:
\begin{align}
C_0 &= P_0 \oplus E_k(nonce\mathbin\|0) \\
C_1 &= P_1 \oplus E_k(nonce\mathbin\|1) \\
\vdots &  \quad\quad\vdots\\
C_{n-1} &= P_{n-1} \oplus E_k(nonce\mathbin\|(n-1))
\end{align}
Why is the following MAC tag not secure: $T = (P_0 \oplus P_1 \oplus \cdots P_{n-1}) \oplus E_k(nonce\mathbin\||n)$ ?

Bit flipping
Flip the bit in the position $x$ on ciphertext block $C_i$ then on the block $C_j$ where $i \neq j$ and similarly for the plaintext $P_i$ and $P_j$. The the new MAC result
$$T = (P_0 \oplus P_1 \oplus \cdots \oplus \bar{P_i} \oplus \cdots \oplus \bar{P_j} \oplus \cdots \oplus P_{n-1}) \oplus E_k(nonce||n)$$ will be the same for the plaintext $Q = (P_0\mathbin\| P_1 \mathbin| \cdots \mathbin\|\bar{P_i}\mathbin\|\cdots \mathbin\|\bar{P_j}\mathbin\|\cdots \mathbin\|P_{n-1})$
Now, send $(Q,T)$ as the message and the tag to the target and they will accept it as a valid tag. This flipping is not related to a single position. The attacker can choose more than one position as longs as the resulting x-or is the same.
Details
Flip is $\bar{x} := x \oplus 1 $ then
\begin{align}
\bar{C_i} &= \bar{P_i} \oplus E_k(nonce\mathbin\|i-1)\\
C_i \oplus 1 &= P_i \oplus 1 \oplus E_k(nonce\mathbin\|i-1)\\
C_i  &= P_i \oplus E_k(nonce\mathbin\||1)\\
\end{align}
So $\bar{C_i}$ and $\bar{P_i}$ work as an attack on the ciphertext. The tag calculates on the messages, therefore one-bit change will be not enough. We need to modify even pairs exactly at the same positions.


Verify product without revealing multipliers Situation:

Several participants contribute encrypted random numbers. These numbers will be used to generate community-agreed random (by simple multiplication).

Question:

Is there any way to detect same products values without revealing multipliers? Maybe it is possible to use some homomorphic encryption?

What I originally want to do:
The task is do eliminate same random values (results), generated in different rounds. There should be some history log and we should regenerate random result if we already generated equal one.

You are asking the wrong question.  You shouldn't do it the way you described (by multiplying or adding random numbers submitted by the participants).  This problem has been well-studied, and there are solutions to it.  Your question assumes a particular approach to the problem, but that approach turns out to be flawed.

Your approach is vulnerable to numerous security problems.  For instance, if you multiply, any one participant can force the final result to be 0 by just submitting 0 as their contribution.  As another example, if you add, any one participant can force the final result to be anything they want, by waiting for everyone else to submit their contributions, looking at their contributions, and then choosing their own contribution so they all sum to the desired result.

Instead, if you want to jointly generate a community random value that none of you can influence, here is what you should do:

Each party picks a random value, and publicly commits to it.  In detail: the party Pi should pick a 128-bit random value ri and broadcast yi = Hash(ri, Pi).
After everyone has received everyone else's commitments (yi values), then each party should open their commitment.  In detail: once party Pi has received all n-1 commitments, he/she broadcasts ri.  Everyone checks that each published ri value is consistent with the earlier commitment yi.  If anyone detects any inconsistency, or if anyone doesn't finish the protocol, you have to call the whole thing off and punish whoever didn't follow the instructions.
Finally, compute R = Hash(r1, r2, ..., rn).  The value R is the random value that everyone has jointly generated.

The security property we get is that no one party, or no coalition of a subset of the parties, can influence the final random number R, except by refusing to finish the protocol.

(You'll have to have a separate out-of-band way to punish parties who don't follow instructions or don't finish the protocol.  The scheme above describes how to detect such parties; it will be up to you to adequately disincentivize such behavior.  If a malicious party Pj is willing to possibly decline to finish the protocol, they can exert modest influence over the final random number R, simply by waiting to be last to reveal their random number rj, checking what R would be if they finished the protocol, and determining whether it is more favorable to them to finish the protocol and end with random number R or to refuse to finish the protocol and leave everyone with no random number.)


Paillier's Cryptosystem - Homomorphism I'm lacking quite some mathematical knowledge here, but could anyone please explain to me why the Paillier cryptosystem is still (additive/multiplicative) homomorphic despite introducing a random value?

$[\![w_1w_2]\!]_g$ = $[\![w_1]\!]_g + [\![w_2]\!]_g\ \bmod\ n$

Does it have to do with the value being sampled from $\mathbb{Z}^*_n$? Is the only requirement for the above statement to hold that $w_1, w_2 \in \mathbb{Z}^*_{n^2}$?

The difficult part about understanding the Paillier cryptosystem is to understand what the $L$ function in the cryption actually does and why it works. The good news is: To understand the homomorphism, that detail can be put on hold.

The best way to understand homomorphism is to have a close look at the encryption function. Here it is:
$$ E(m) = r^n g^m \mod n^2$$

If we take this apart, we can see:

The modulus is $n^2$. That means we operate on a multiplicative group with order $n \cdot \lambda$ (with $\lambda=lcm(p-1,q-1)$).
This means, there exist subgroups of order $p,q,n,pa, qa,$ and $na$, where $a$ is any proper divisor of $\lambda$.
The random number $r$ has an order equal to one of those subgroup orders. It could be divisible by $p,q$ (actually, it's overwhelmingly likely to be the order $n\lambda$). However, if we take that to the $n$-th potency, then the order of $r^n$ is not divisible by either $p$ or $q$, it can only be a divisor of $\lambda$. That is a property that can be used.

Now for the decryption, it is enough that somehow the decryption function can:

Remove any masking factor which is such an $r^n$, without knowing which $r$ it is.
Get $m$ back from the remaining number $g^m$, which is basically a discrete logarithm in this special kind of group.

Now for the homorphism, just encrypt two messages, build their product and do some very basic transoformations:

$$ E(m_1) = c_1 = g^{m_1}{r_1}^n$$
$$ E(m_2) = c_2 = g^{m_2}{r_2}^n$$
$$ c_1 c_2 = g^{m_1}{r_1}^n g^{m_2}{r_2}^n = g^{m_1+m_2} (r_1r_2)^n$$

Clearly, this is just the same as using the encryption method with the message $m_1+m_2$ and the random number $(r_1r_2)$. And for that the decryption works just like for a single ciphertext.


Which is/are the strongest known Fully Homomorphic Encryption scheme(s)? As it is discussed here that the highest security any homomorphic encryption scheme is at most IND-CCA1, Is there any known fully homomorphic encryption scheme that achieves this security level? Out of many schemes mentioned here (or otherwise) which of them are IND-CCA1 secure ? (not necessarily practical though)

A recent paper: https://arxiv.org/abs/1804.06862 claims to be fully homomorphic with IND-CCA1. However it is a symmetric encryption scheme and I'm not sure if IND-CCA1 is an appropriate measure in this setting.

Besides this, I think security is based on the hardness of solving overdetermined systems of quadratic equation over $\mathbb{Z}_{(p\cdot q)^2)}$ rings, which then might not be Quantum-hard. If I'm not mistaken, there are sixteen quadratic equations and if we can factor $(p\cdot q)^2$ then these equations can be efficiently solved.

Otherwise the scheme is pretty efficient, in terms of key-length, decryption and encryption time, I think. It is noise free and based on ring-automorphisms for matrices with elements from the quaternion-ring over some $\mathbb{Z}_{(p\cdot q)^2)}$ ring.

However as the paper appeared only recently, an in-deep analysis, besides the argumentation auf the authors, is not yet availablabe as far as I know.


Increase number of rounds for SPN and Feistel ciphers Read a post on Schneiers blog (and again 2011) about increasing the number of rounds for AES from to "AES-128 at 16 rounds, AES-192 at 20 rounds, and AES-256 at 28 rounds" to raise the security. However, I did wonder where these figures came from. According to Schneier "hey're off the top of my head, and certainly not the last word on the topic", and a previous topic on stackexchange "more rounds means more security against cryptanalysis, simply, since there is more confusion and diffusion".

My question is:

Could any high number of rounds do for SPN and Feistel ciphers like
AES, Serpent or Twofish? Or would/could the ciphers end up being
weaker after a certain X number of rounds? Or maybe even repeat some
patterns?
How much more secure can AES, Serpent or Twofish become if the
    rounds increases? Would AES, for example, be strong as whatnot if
    the number of rounds were to be ridiculously increased?

Usually, more rounds increase security as long as subkeys are independent of each other. That's a critical point.

Consider AES-128 as currently defined, with its ten rounds; that's eleven 128-bit subkeys. Adding six rounds means adding six extra 128-bit subkeys. The original AES-128 is still there. If the six extra subkeys are generated independently of the first eleven subkeys, then they cannot decrease security. Security can thus only increase. However, there are important caveats:

In practice, subkeys are not independent of each other. They are produced from the encryption key using a process (the key schedule) which is rather simple and cannot be considered to be a reasonably secure PRNG by itself. The AES key schedule is known to be somewhat weak to analysis, when pushed outside of its intended usage scenario (e.g. it has non-fatal related-key attacks).
If extra rounds do not decrease security, there is no guarantee that they will increase security. Personally, I tend to refuse to consider an algorithm stronger than another as long as both are in the "cannot break it" zone. Such comparisons rely on prophetic assumptions on how technology will evolve in the far future, sometimes quite far in the absurd (it makes little sense to compare 230-bit keys with 260-bit keys while still using an hypothetical classical computer, since it would require eating full stars to power it).

Increasing the number of rounds is more about building trust. That's still science, but not computer science; rather psychology. Increasing the number of rounds gives the feeling that "we are doing something against attacks". It is like making some offerings to Nammu, Sumerian goddess of the sea, before going on a cruise; at least, it won't harm -- except for the off-chance that Poseidon gets displeased at your allegiance to the competition... In the case of AES, increasing the number of rounds does lower performance, although this is not significant in most contexts (AES encryption speed is rarely a bottleneck; e.g. Microsoft measured that applying AES-based Transparent Data Encryption on SQL Server implied an average CPU overhead of 3 to 5%, no more).


Encryption of 8 bit block of data I'm looking for a cryptographic algorithm that allows encrypting only 8 bits of data in a block. Is there any such algorithm that is considered secure?

The reason I'm asking is because I have to encrypt and decrypt the data contained in SPI Flash memory (the BIOS flash), and I need it to be really fast to get the cyphertext and give the plaintext to the CPU. The CPU can fetch 8 bits at a time, and can jump to a different address each time.

First of all, there's no such thing as a secure 8-bit block cipher, at least not as such things are conventionally used.

That's because there are only 256 possible values for an 8-bit byte, and a block cipher will map each of these values to a different fixed value.  Thus, an attacker who can even occasionally guess the unencrypted value of some bytes (or, worse yet, can control the bytes to be encrypted) can easily learn which unencrypted byte corresponds to many, if not all, the encrypted bytes.  In fact, even if the attacker only had access to the encrypted data, they could most likely still decrypt much of it simply by comparing the frequencies of different encrypted bytes, and the patterns in which the bytes occur, with known examples of typical BIOS contents.

If you had a fast, key-agile block cipher, you could in theory make this attack a lot harder by using a separate key (typically, generated "on the fly" from a master key and the byte address) to encrypt each byte.  If the data never changed, and assuming that the keys were effectively independent (or at least independent enough to avoid related-key attacks), this could be secure; indeed, even if the data did sometimes change, all that observing multiple versions of the encrypted data would leak is whether the value of a particular byte matched an earlier value of the same byte.

Alas, I'm not aware of any fast, key-agile 8-bit block ciphers with a good track record of resisting cryptanalysis.  (That doesn't prove that there aren't any, of course.)

However, you could instead go further, and encrypt each bit separately.  Of course, there's only one possible 1-bit block cipher*, and it has only two possible keys: 0, which leaves the bit unchanged, and 1, which flips it.  Thus, "1-bit block cipher" is really just a fancy name for XOR.

You still need to generate an independent key bit to XOR each of your data bits with, of course.  For that, you need a stream cipher.  In particular, since you say you need random access to the data, I'd suggest using a (conventional, wide-block) block cipher in CTR mode as your stream cipher.

As long as your data never changes, XORing it with a keystream generated by a conventional block cipher (e.g. AES) in CTR mode actually is semantically secure.

With CTR mode, you can generate any (e.g.) 128-bit block of the keystream any time you like, without having to generate all the preceding bits of the keystream first.  As a simple performance optimization, consider caching the most recently computed keystream block in a register, just in case the next byte to be requested falls inside the same block.  You could even optimistically start pre-calculating the next block before you actually need it, if you expect a lot of sequential reads in practice.

However, note that CTR mode (and stream ciphers in general) may be insecure if the data can change.  In particular, as soon as an attacker learns both the encrypted and the unencrypted value of a given byte (or even a given bit), they'll learn the corresponding bits of the keystream.  Further, even just observing two different encrypted values read from the same address will reveal the bitwise difference of the corresponding plaintext values.

Avoiding such attacks is the domain of disk encryption theory, and can get rather tricky in general, especially if you demand that no extra storage space be used.

However, if you can set aside a bunch of (say, 16 or 32) bits in each Flash memory block to store a write counter, and are fine with the value of this counter being leaked if someone inspects the encrypted data, there may be a simple solution: just use this write counter together with the byte address (truncated to cipher block boundaries, of course) as the counter value.  That way, every time a Flash block is rewritten, the keystream for that block changes completely.

Of course, this means that you can't store data in the bits used for the counter, which, in particular, could complicate addressing, since the "logical block size" seen by the CPU will be slightly smaller than the physical block size of the Flash memory.  There are various tricks you might be able to use to get around that, but they depend on the specs of the system you're working with.

Also note that CTR mode encryption (like stream ciphers in general) is particularly malleable, and therefore potentially culnerable if an attacker may modify the encrypted data in the Flash memory.  To prevent such attacks, you may also want to store a (possibly per-block) MAC of the encrypted data, and verify it before allowing any data to be read.  (Note that the MAC input should include the block number and the write counter / IV, to protect against attacks involving swapping blocks or resetting the counter.  If you're using per-block MACs, you may also wish to compute a global "MAC of MACs" to prevent an attacker from mixing blocks from different versions of the data.)

*) Technically, there are two 1-bit block ciphers, but they differ only by a trivial rearrangement of the key space.


Are there any security risks in using Elliptic Curves defined over fields $\mathbf{F}_{p^n}$ where $n>1$ I've recently been studying elliptic curves, and I've found that most of the current implementations use fields $\mathbf{Z_p}$ or in some cases $\mathbf{F}_{2^n}$. All the reasons I've seen for not using other extension fields are for reasons of efficiency.

I'm wondering if, efficiency aside, are there any security concerns inherent to using curves over  $\mathbf{F}_{p^n}$ where $n>1$ and $p > 2$?

There are concerns on curves defined over an extension field. In particular for those of a small extension degree.

For a curve with a subgroup of prime order $r$, generally the best algorithm to solve the discrete logarithm problem has a complexity $O(r^{1/2})$. But there are attacks that use the structure of the extension field to get an algorithm with a smaller complexity.

Weil descent. The finite field $\mathbf F_{q^n}$ can be viewed as a $\mathbf F_q$ vectorial space of dimension $n$: a polynomial equation defined over $\mathbf F_{q^n}$ can be viewed as $n$ polynomial equations defined over $\mathbf F_q$.
It is possible to construct, under some conditions, a homomorphism from an elliptic curve $E$ defined over $\mathbf F_{q^n}$ to the jacobian a hyperellipti curve $H$ (the group associated to the curve, in the case of elliptic curve it is the curve itself) over the smaller field $\mathbf F_q$.
$$
\varphi : E(\mathbf F_{q^n}) \to \mathrm{Jac}(H)(\mathbf F_q)
$$
When this can be achieved, we can use better algorithms to solve the discrete logarithm on $\mathrm{Jac}(H)(\mathbf F_q)$.
There are some limitations: for most curves $E$, the hyperelliptic curve produced has a high genus that makes algorithms much slower than on the elliptic curve.
Algebraic approach. Index calculs method brought a better than square-root complexity for the discrete logarithm on the multiplicative group of a finite field. The idea is to decomposed random elements over a factor basis, and with enough relations and linear algebra, the discrete logarithme is solved. For elliptic curves over an extension field $\mathbf F_{q^n}$, the factor basis can be defined as:
$$
\mathcal F = \{ P \in E(\mathbf F_{q^n}) \mid x(P)\in \mathbf F_q\}.
$$
Suppose $n=2$ and you want to decompose a point $R=(x_R, y_R)$ into two points of $\mathcal F$. There exist a polynomial $S_3$ such that if $S_3(x_1, x_2, x_3) = 0$, then there exists $P_1, P_2, P_3$ with $P_1 + P_2 + P_3 = \infty$. It can be used to solve the system
$$
\begin{array}{l}
S_3(x_1,x_2,x_R) = 0 \\
x_1, x_2 \in \mathcal F
\end{array}
$$
And $S_3$ can be viewed as $2$ polynomial equations over $\mathbf F_q$ and since $x_1$ and $x_2$ are already in the subfield, we have a polynomial system (non-linear, unfortunately) of $2$ equations and $2$ variables that can be solved by computing a Groebner basis. This can be generalized for bigger $n$.
This approach has lead to an algorithm of heuristic complexity $\tilde{O}(q^{2-2/n})$ which is faster than the square-root algorithm when $n\geq 3$. One drawback is that there is a constant $n!$ on the complexity.

You can find a survey from 2015, Recent progress on the elliptic curve discrete logarithmproblem that talks about the above and more.
Attemps have been made to apply the algebraic approach for curves over a prime field $\mathbf F_p$ but have failed (a factor basis that can be translated algebraically is harder to find without having a polynomial of high degree, which makes is very difficult to solve non-linear polynomial system).

To prevent the above attacks, it is recommanded to have a finite field of prime degree which is the case for most of binary standardized curves ($\mathbf F_{2^n}$ with $n$ prime), but not all, or use a curve defined over a prime field.


Figure out algorithm to numeric key generator with one known input and output I have a software program running on a piece of hardware. To access a specific functionality it runs a challenge-response-like authentication, that is it generates a numerical 4-digit PIN and expects a 4-digit numerical PIN in response. I'm now looking for whether it is possible to come up with the algorithm that is used to generate the response and if so how.

Right now I have one sample pair (7153 - 9533) to work with. Ideally there would be some utility or a formula that I could apply or tweak here. I'm confident that once I figure out what the underlying algorithm is to convert from one 4 digit challenge to the 4 digit response then I will be able to code me a little utility to always get the response.

Since the response is always a 4 digit number that is generated from another 4 digit number I assume that there is only 10,000 possible codes that relate to the 10,000 possible "seeds" so I don't think this should be very hard for me to reverse engineer or brute force, essentially I'm looking for a direction where to start.

So my question (in short):
How would I approach such a problem and can it even be done at all?

Ideally there would be some utility or a formula that I could apply or tweak here.

I have to say there is no such utility, no such formula. This problem has no solution.

There is 10000! = factorial(10000) different transformations of 4-digit numbers to 4-digit numbers. For instance, your input 7153 and result 9533 can be produced by any of the following functions:

f(x)=(2x+5227) MOD 10000

f(x)=(3x+8074) MOD 10000

f(x)=(x^3+8956) MOD 10000

Knowing a single pair is not sufficient to find out what transformation was used. If they use some simple function, then having more pairs might give (without guarantee) an insight about this function.


Is it secure to choose d in a RSA key pair? An RSA key pair consists of the private key $(n,d)$ and a public key $(n,e)$ such that $de \equiv 1 \bmod{\lambda(n)} $.

Usually one chooses a small $e$ and computes $d$ by inverting it modulo $\lambda(n)$. This makes things computationally easy for the user of the public key, but makes it expensive to use the private key because $d$ is large (typically only a few bits shorter than $n$).

If one wants to shift computational cost from the private to the public side of the cryptosystem, would it be secure to select $d$ as, say, a random 128-bit number coprime to $\lambda(n)$ and then compute $e$ as its inverse instead of the usual way around?

Selecting a small $d$ is known to be insecure.

Wiener has shown in 1990 that if $\log d \leq \frac14 \log N$, the private exponent $d$ can be reconstructed from the public key $(N,e)$.

If you're interested in making the private computational cost cheaper, then I would suggest that RSA is not the best solution; I would recommend you start looking at Elliptic Curve based solutions.


RSA decrypt message with low public exponent (n = 187, e = 3 and C = 185) n = 187
e = 3
C = 185

How to decrypt message? I know there is some way using cryptogram exponentiation. Can you give me a hint?

For small $N$, textbook RSA decryption is possible without factoring $N$ using the cycling method, (sometime called cycling attack; see this for a reference):

initialize $M\gets C$
set $D\gets M^e\bmod N$ (otherwise said, encrypt $M$)
if $D\ne C$, then set $M\gets D$ and loop to the previous step
output $M$ and exit.

Since encryption is a reversible mapping of the finite integer set $[0,N)$, the algorithm must cycle and stop. Obviously, when it does, we have $C=M^e\bmod N$, thus the algorithm has deciphered $C$.

Note: this is unrelated to small $e$. It works well for small $N$, but for other $N$ or multiple messages to decipher, it is more efficient to factor $N$.


Pseudo Random Function The definition of pseudo randomness that leads to pseudo random function talks about indistingishability of a key-ed function and a random function.

i.e. The key-ed function family $\{F_k\}$ is PRF if $|Pr[D^{F_k}(1^n)=1] - Pr[D^{f}(1^n)=1]|$ is negligible for $k\leftarrow\mathcal{K}$ and $f\leftarrow\mathcal{F}$.

Informally the output of both the function $F_k$ and $f$ at polynomial many points follows same distribution. Since $f$ is a random choice of random function family, $\{f(x)\}$ is uniformly random.

So can I use output $F_k(x)$ as the key to same PRF in next iteration?
i.e. say $k1=F_k(x)$ and I can compute $k2=F_{k1}(x)$. But will $\{F_{k1}\}$ still be a PRF?

Well, yes, but you cannot use the key $k_1$ for anything else because knowledge of $k_1$ would mean that an attacker can simply calculate $k_2$. If an attacker can find a direct relation between parts of the output then the function is of course not pseudo random anymore. So although it is possible it seems pretty useless to me.

Even if you would not directly use $k_1$ as output you would need to prove that you use it in such a way that security is not compromised. In general you should try to not reuse keys for different purposes.


Why use RSA-2048 for plaintext when AES-256 is much more secure? Why do we use RSA encryption for ANY text/communication/data encryption when everybody on internet is writing that AES-256 is much stronger than RSA-2048? If this is true, why do encrypted email services like Protonmail even use RSA encryption for their email communication when it is not as secure as AES-256?

I have read that it is currently impossible to break AES-256 using brute force attacks, but RSA is not such a big problem to break. Why is this method even used in cryptography when it is slower and weaker than a symmetric cipher like AES?

Is the only reason for using RSA is because of its asymmetric geometry (private/public key)?

I know that this question is not easy to answer but I will give one example:
If I want send secure and encrypted plaintext of - for example - two full A4 pages of text, is it better to use AES-256 or RSA-2048? What I know much stronger and also faster is using AES, but maybe I am missing something?

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

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


Inverse of a polynomial using long division over GF(256) I am trying to find the inverse of a polynomial $3x^3+x^2+x+2$ over the field $GF(2^8)$ with polynomial $(x^4-1 )$

Here is what I did,

$$ \dfrac{(x^4-1)}{3x^3+x^2+x+2}$$

$$ (x^4-1) = (171x+199)(3x^3+x^2+x+2)+ (142x^2+227x+115)$$
$$ \dfrac{(3x^3+x^2+x+2)}{(142x^2+227x+115)}$$

But I can not divide further because 142 does not provide me odd multiples to cancel $3x^3$. Can I use fractional number to get rid this? I tried fractional number too, but they made its too much complicated.

How can I do this? Or I am following a wrong approach?

I think the root of the misunderstanding is that there are two completely disjoint notions of polynomials at work here.

First there is the finite field $\mathbb{F}_{2^8}$. It's the field where coefficients like "3" live. Following the AES notations, you represent these elements as integers, but they really are finite field elements. The definition of the finite field usually involves polynomials (of degree less than 8 and with coefficients in $\mathbb{F}_2$) but that's best viewed as a matter internal to that field.

Then the question you are trying to solve is about polynomials whose coefficients are themselves elements of $\mathbb{F}_{2^8}$. These polynomials are not at all the same polynomials as the ones used internally by $\mathbb{F}_{2^8}$.

Apparently you are trying to do computations with the coefficients (the ones in $\mathbb{F}_{2^8}$ as if they were integers, so your numbers are off. Let's see things in details:

You want to divide $x^4-1$ by $3x^3+x^2+x+2$. Not that in $\mathbb{F}_{2^8}$, addition really is XOR, so subtraction is the same as addition; thus, $x^4-1$ is also $x^4+1$. But anyway, in the course of the division, you want to "cancel out" the top coefficient of $x^4-1$ with a multiple of $3x^3+x^2+x+2$. In $\mathbb{F}_{2^8}$, $3\times246 = 1$, so you can write:

$$x^4 - 1 = 246x(3x^3+x^2+x+2) - 246x^3 - 246x^2 - 247x - 1$$

Next step is to cancel out this spurious $-246x^3$. Again, take care that this "$-246$" is not an integer; it is a field element in $\mathbb{F}_{2^8}$. Also, since (again) addition is XOR in that field, we can remove the minus sign (in binary fields $\mathbb{F}_{2^m}$, $z = -z$ for all elements $z$). Acknowledging that additions and subtractions are the same thing in a binary field, we can write this:

$$x^4 + 1 = 246x(3x^3+x^2+x+2) + 246x^3 + 246x^2 + 247x + 1$$

In the field, $246 = 82\times 3$ (yeah, for once, this matches integer multiplication, but it is fortuitous). So we can write this:

$$x^4 + 1 = (246x + 82)(3x^3 + x^2 + x + 2) + 164x^2 + 165x + 165$$

So the first "long division" in the Extended Euclidean Algorithm yields a quotient of $246x+82$, and the remainder is $164x^2+165x+165$.

Next step in the Extended Euclidean Algorithm will be to divide $3x^3+x^2+x+2$ by $164x^2+165x+165$. And that one will begin by dividing $3$ by $164$ in the field $\mathbb{F}_{2^8}$. The result of that division is $138$; that is, in the finite field: $3 = 164\times 138$. Computing out the division, we get:

$$ 3x^3 + x^2 + x + 2 = (138x + 79)(164x^2 + 165x + 165) + 79x + 168 $$

I am too lazy to finish it by hand. The crucial point to understand is that all computations on coefficients are in $\mathbb{F}_{2^8}$, which is a finite field with its own rules, which are not the same rules as integers, even though they are represented as integers. In particular, there should be no notion of "odd integer".

Here is a piece of C code that implements computations in $\mathbb{F}_{2^8}$:

static unsigned
add(unsigned x, unsigned y)
{
        return x ^ y;
}

static unsigned
mul(unsigned x, unsigned y)
{
        unsigned z;
        int i;

        z = 0;
        for (i = 0; i < 8; i ++) {
                z ^= x & -(y & 1);
                y >>= 1;
                x <<= 1;
                x ^= (0x11B & -(x >> 8));
        }
        return z;
}

static unsigned
invert(unsigned x)
{
        unsigned z;
        int i;

        z = x;
        for (i = 0; i < 6; i ++) {
                z = mul(z, z);
                z = mul(z, x);
        }
        return mul(z, z);
}

static unsigned
divide(unsigned x, unsigned y)
{
        return mul(x, invert(y));
}

In this code, every element of $\mathbb{F}_{2^8}$ is represented as an integer in the $0$ to $255$ range (0xFF is $255$). As you see, addition really is XOR (the C operator ^ is bitwise XOR). Multiplication is done bit by bit; the weird-looking code:

                x <<= 1;
                x ^= (0x11B & -(x >> 8));

is really a "left shift" of x in $\mathbb{F}_{2^8}$ (try to work out why it works, it's enlightening). Finally, inversion (invert() function) is done with exponentiation: since there are exactly $255$ invertible elements in $\mathbb{F}_{2^8}$ (all except $0$: it's a field), then the inverse of $z$ is $z^{254}$ for all elements $z\neq 0$. The invert() function computes $z^{254}$ by repeated squarings and multiplications. (Note: that invert() function will happily compute the inverse of $0$ as $0$, even though $0$ is not invertible.)


Tree hash and multithreading for parallelism I am using tree hash mode of Skein on a 16 core processor. Will it automatically employ parallelism using more than one cores or do I have to use multi-threading within the tree hash for parallel processing?

Also, the tree hash mode requires three parameters: leaf size encoding, fan-out encoding and tree height. Except for the last one, I am confused about the other two parameters, what are they exactly?

On multi-threading: Read the code.  As Paulo writes, that's up to the implementation.  Read the source code of your library and see for yourself what it is doing; it shouldn't be too hard to figure it out.


Verification using recovered public key from ECDSA signature and normal verification: what are the differences? For ECDSA, a given signature and its message can be used to recover the public key used to sign it (produce 2 public keys). By making comparison of these recovered public keys against the known public key, one will be able to verify the signature.

Does this method differ from the conventional signature verification? If it does differ, is there any performance difference between these two methods?

Recovering the two potential public keys and comparing them to the known public key is related to, but distinct from the normal ECDSA signature verification algorithm, and is somewhat more costly.

The notation I'll use:

$r, s$ are the values from the signature
$h$ is the hash of the message being verified (truncated, if the length of the hash is longer than the group size)
$P$ is the public key
$G$ is the group generator
$|Q|_x$ is the x-coordinate of the point $Q$
$\{R, R'\}$ are the two curve points with x-coordinate $r$

Then, the standard verification algorithm is:

$$r \ \overset{?}{=}\  |(hs^{-1}G + rs^{-1}P)|_x$$

To evaluate this requires two point multiplications and one point addition, which with Shamir's trick, can be done in not much more time than one point multiplication.

In contrast, the 'recover the private key, and compare' logic would be:

$$P \ \overset{?}{=} r^{-1}s\{R, R'\} - r^{-1}hG$$

Where you accept the signature if either $R$ or $R'$ satisfies the equation.

This may require three point multiplications (or two applications of Shamir's trick); rather more than the standard logic; even if you get lucky and pick the correct $R, R'$ initially, you're no better off.  You could rearrange this to make this more efficient (as you have the potential value $P$ in hand); however if you do, you'll find that you'll arrive back at the standard ECDSA verification logic.