Curve point generators for ECC I'm working on a cryptosystem based on ECC (elliptic curve cryptography). I need to choose several (~10) curve points which should be used as generators, and it's important that their relation is unknown, i.e. no one should be able to obtain one generator by multiplying another one by some scalar.

So that just choosing all the generators in a random manner isn't good idea, because some may suspect that they're not actually random, and their relation is known.

Natural solution is to create all the generators by using hashing scheme, i.e. pick several strings and create all the generators by hashing them (or hash each generator in order to create the next). This should convince everyone that their relation is unknown.

However it's also important that the obtained curve points are indeed generators, i.e. each one forms a cyclic group which spans all the curve points.

Now, this is where I'm confused. I've read once that selecting right points isn't a trivial task, there exists an algorithm to test the rank of a point, but it's somewhat complex to implement.
However I've also heard that most of the points on an elliptic curve are generators, and when selected in a pseudo-random manner it's very unlikely to fall onto a bad point.

So, what is right to do? Is it ok just to pick random points and hope for the best?

Is there an "online resouce" which can test the selected points? I mean, I can define the problem (curve formula, the prime for the underlying field order), give the point, and get its rank?

Now, this is where I'm confused. I've read once that selecting right points isn't a trivial task, there exists an algorithm to test the rank of a point, but it's somewhat complex to implement. However I've also heard that most of the points on an elliptic curve are generators, and when selected in a pseudo-random manner it's very unlikely to fall onto a bad point.

Actually, finding a generator is typically a lot easier than what you've read, at least in practice.

In crypto, we generally use curves that have an order of the form $hq$, where $q$ is a large prime, and $h$ is a small integer.

So, what you do is:

Run your hashing function to create an arbitrary point $H$
Multiply it by the cofactor $h$ to find the point $H' = hH$ (which is totally trivial for those curves with $h=1$; not that difficult for curves with larger cofactors)
Verify that $H'$ is not the neutral element (aka the identity aka the point at infinity).

If $H'$ is not, then that's your generator; it's guaranteed to be of order $q$, and to have no known relationship with other points (assuming that your original point $H$ didn't)


Would the public key of Digital Signature be replaced? According to my understanding, Digital Signature is a technology to use private key/public key to sign/verify data in order to ensure data authentication, integrity and non-repudiation. Sender signs the data with private key and send the signature with the original data to receiver, and receiver verify the signature to confirm the sender is trustworthy.

But I wonder how the receiver confirm whether the public key on his hand hasn't been changed?

I mean if it is possible that the public key has been intercepted and replaced with a fraudulent public key while transferring to the receiver, and finally receive a fraudulent message with a signature signed by a fraudulent private key? If there is a safe way to send a public key to receiver, why don't just send the message in the same way?

I tried to google for the answer but no luck, if you think this question is too simple you can just throw me the url or something, I am willing to study by myself.

Thanks in advance.

extended and transformed comment into an answer

Digital signatures are not a complete system, they are one mechanism. They assume public keys are known by everyone.

In practice, this is often achieved by some sort of public key infrastructure. In software it's also possible the program has the verification key hard-coded.

  If there is a safe way to send a public key to receiver, why don't just send the message in the same way?

Well, that's pretty much what the chain of certificiates in a PKI do - but the sender might be a different person then.


Bitwise operation on secret values revealing the result only to the participants Given the following situation, what sort of cryptographic construction am I looking for?

Alice has a bitfield (vector, polynomial representation, etc.)
Bob has a different bitfield of the same length
Alice and Bob want to know the bitwise AND of their two bitfields without revealing the result to others and without revealing their personal bitfields to each other or anyone else

For example

Alice has 0101
Bob has 1100

What would one do for Alice and Bob to know the result 0101 & 1100 = 0100 without revealing anything as stated above?

I imagine this would require some combination of zero-knowledge and homomorphic techniques, but I will be the first to admit that this is probably a bit out of my depth.

The concept of "bitfield" is in fact irrelevant in this case since it doesn't really matter to which algebraic structure the data belongs to, at the end you're not using this structure at all, you're just treating them as bit strings.

What you're looking for is Secure Multiparty Computation (MPC). A bit more specifically, you need Two party computation (2PC). There are many techniques to achieve this but since you're working over a binary representation I recommend you to take a look at Garbled circuits or TinyOT (the latter should perform well since your circuit has low depth).

As a note, you cannot achieve this with something weaker than 2PC since computing AND gates is essentially complete for 2PC, meaning that any other solution you find could potentially imply a 2PC protocol.


What is more secure, a ciphertext encrypted with AES-256 or encrypted with 3 different AES-128 keys? Or better yet, is encrypting a block with 2 AES-128 keys just as secure as encrypting a block with 1 AES-256 key? By the way, I've only recently been learning cryptography stuff; I've made working prototypes in python for both RSA and AES and am familiar with (basically) how they work in general; just not the complex mathematical concepts and terms.

Although my intuition tells me that you cannot fully decrypt a message encrypted twice with two different keys without knowning both keys, that fact that I haven't heard of doing this makes me think it's been asked and answered to the negative and I'm just not seeing it. If AES is really fast, what's to stop paranoid people from going all the way up to 16-32 different keys? That is completely computationally viable for email and chat clients, maybe even other applications (I know nothing about computational complexity).

If I had to guess what would break this, I would say that for any known ciphertext encrypted with AES-128, there exists exactly one 128 bit key that will return the original plaintext from the recovered ciphertext. But I can't see a method for potentially figuring out what the original plaintext was, since that ciphertext could decrypt into any and all plaintexts still.

You have more than one question in your... question. user13741 already did answer the "is 2x AES-128 as secure as 1x AES-256?" part, so only a small summary: Plaintext is the message before it was encryptet, and ciphertext after it was encryptet. You can encrypt a known plaintext with all possible keys and save the result. Now you decrypt the ciphertext with all possible keys and look if the result is in the database of the first encryption task. If yes, you have found the two keys. The first task takes $2^{128}$ encryptions (for AES-128) and the second task takes $2^{128}$ decryptions. If you add them you get not $2^{256}$, but $2^{129}$.  That attack is called Meet-in-the-middle attack. (But you need the space to store $2^{128} \times 128$ bit. That's more than you will ever be able to store, but still you have to consider this. Maybe a future attack will somehow reduces the security of AES in a way which will make this kind of attack feasible without storing over $10^{27}$ terabytes.)

In the title you ask about 3 different AES keys. Yes, this construct is more secure than AES-256. An attack on this (if AES is not broken) would take something like $2^{257}$ encryptions or decryptions, even more than on AES-256. Without the mentioned meet-in-the-middle attack you would even need $2^{384}$ to fully search the possible key space. This is the reason why Triple DES was used and not Double DES. DES with two keys would be enough in terms of the number of possible keys, but this attack makes it possible to reduce the amount of work to a nearly managable number. Not secure enough for most of the experts.

Why nobody (or at least not a high number of people) encrypt their message more than one time? There's no need for that. Even $2^{128}$ attemps are totally unfeasable. Even if the future of the world would depent on it and every government would need to break it. There are just too many possible keys. An attack on the person which knows the key or attacking the underlying protocol is much more promising.

Yes, you are right, there's exactly one key which results in the given plaintext for a given ciphertext (and the other way round). Also there's exactly one plaintext for every given plaintext and given key (and vice versa). This is true for AES-128, while AES-192 and AES-256 are slightly more complicated, but not much.

Now comes the big "but": All this only works if AES is fully secure. It is not. There exist some attacks which reduce the amount of security AES has. AES-256 is more "broken" than AES-128 and AES-192 (because the key setup is slightly different for AES-256 and it uses a bigger key size). Still, all three are (as we know it) still not really broken. The security margin is still quite high and the kind of attack is a pretty hard one. We don't have to panic, but for the future we should either change AES to make it more secure (Bruce Schneier suggests more rounds as fast and easy change) or take a look at some other ciphers like one of the other finalists of the AES process. If you really need to secure some highly risky data for 30 years against the NSA and other major organisations, than you should consider not using AES. For every normal person, AES is more than enough.)


Constructing a commitment scheme from two (possibly defective) commitment schemes If we have two commitment schemes Com1 and Com2, which are possibly defective (in the sense of not satisfying hiding or binding properties), is it possible to construct a commitment scheme which does satisfy those properties?
Specifically, in the following scenarios:

Both Com1 and Com2 satisfy the hiding property, and one of them satisfies the binding property (but you do not know which). In this case, I think that we could construct a commitment scheme by letting Com(m,s) = Com1(m,s)||Com2(m,s), but I am not sure if I am right or not.

Both Com1 and Com2 satisfy the binding property, and one of them satisfies the hiding property (but you do not know which). In this case I do not think we could create a good commitment scheme. Suppose that Com1 is the scheme which does not satisfy the hiding property- we cannot be sure to avoid using Com1 in our construction since we do not know which of the two schemes satisfies the hiding property, and using Com1 in our construction in any way would seem to preclude our construction from satisfying the hiding property as well, unless I am mistaken?

Any help would be greatly appreciated, thank you!

It's been over a month, and so if this was a homework question, the due data has already passed.

Both Com1 and Com2 satisfy the binding property, and one of them satisfies the hiding property (but you do not know which). In this case I do not think we could create a good commitment scheme.

Sure you can; you just do:
$$Com(m, r_1, r_2, r_3) = Com1( m \oplus r_3, r_1 ) || Com2( r_3, r_2 )$$
If Com1 does not have the hiding property, someone can learn the value $m \oplus r_3$, however if $r_3$ is selected randomly, they learn nothing about $m$.  Similarly, if Com2 does not have the hiding property, they can learn the value of $r_3$; again, they learn nothing about $m$.
The other piece we need to show is that $Com$ also has the binding property; that is straightforward with the assumption that both $Com1$ and $Com2$ do; $Com1( m \oplus r_3, r_1 )$ can be opened only as $m \oplus r_3$, and $Com( r_3, r_2 )$ can be opened only as $r_3$, and the xor of the two will have to be the original committed string $m$.


Is there any ECDSA Attack if I have millions of signatures? I have been given the task to test the security of our company software. Our company software generates ecdsa signed supply order files. One can generate as many files as he wants.

so my question is Is there any ECDSA Attack if I have millions of signatures?

we are using 112bit prime curve order: 4451685225093714776491891542548933

I have calculated 1 million signatures using the following method:

public void GenerateSignature()
{
    //curve order
    BigInteger n = ec.N;

    Ramdom rand = new Random();

    //private key
    BigInteger d = ((ECPrivateKeyParameters)key).D;

    //loop for 1 million signatures
    for (int i = 1; i <= 1000000; i++)
    {
        //random k and e
        BigInteger e = new BigInteger(112, rand).Mod(n);        //new biginteger by giving bitlength and random
        BigInteger k = new BigInteger(112, rand).Mod(n);

        //calculate r
        BigInteger r = key.Parameters.G.Multiply(k).X.ToBigInteger().Mod(n);

        //calculate s
        BigInteger s = k.ModInverse(n).Multiply(e.Add(d.Multiply(r))).Mod(n);

        //save generated signatures to database
        new DBCon().ExecuteNonQuery("Insert into signatures values ('" + e.ToString() + "', '" + r.ToString() + "', '" + s.ToString() + "')");
    }
}

I am using BouncyCastle crypto library with C#.

I know private key can be calculated if k value is known by d = (sk - e) / r

I also know private key can be calculated if two signatures have identical r value then we can calculate k by k = (e1 - e2) / (s1 - s2) and then d by using above formula.

I also know that private key can be calculated if some bits of k are known using about 100 signatures with lattice attacks, but in this case bits of k are unknown.

any help will be appreciated. Thanks.

In the question's particular context, and ignoring the preamble, yes, the private key can be found (assuming the public key is known, which is a standard assumption). I see two ways, the first using no signature at all, the second likely requiring only a few ones.

Mere knowledge of the public key allows to find the private key for the curve secp112r1, using moderate brute force and 2009 technology. See Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra, Peter L. Montgomery's Solving a 112-bit Prime Elliptic Curve Discrete Logarithm Problem on Game Consoles using Sloppy Reduction, in IJACT 2012.
As an artifact of the code shown in the question, we get in the database the result of BigInteger e = new BigInteger(112, rand).Mod(n); where rand is an instance of the basic, non cryptographically-secure Random. With a little digging (left a an exercise to the reader) in the source code of this BigInteger constructor (likely equivalent to this) and of Random, it should be possible to mount an attack recovering the state of rand, and the rest is easy.

In real life, it is possible we would not be so lucky as to have the second avenue. Yet, if the non-cryptographically secure Random was used, we might be able to attack its seed, or multiple signatures could be sharing the same $k$ due to poor seeding (but in the question, repeated $k$ is unlikely).


How can we compare an encrypted number with a normal number? I am currently doing a project on privacy preserving encryption using a k-means system and the Paillier encryption algorithm (homomorphic algorithm). I have to send an image of a skin disease to the server as an encrypted image.

To do this, k-means is applied on the encrypted image and the image is sent to the respective party with k-means already applied. The decryption happens on the party side.

However in the k-means algorithm itself, I have to compare an encrypted pixel value of the image to a normal number, and this is where I am getting stuck.

If this is not performed under the encrypted version of the plaintext on the semi-honest party there is a problem.

Assume that there is a method $f(m,c)$ return $T$ if the values are same and $F$ if the values are not same. So you can compare a plaintext with a ciphertext.

With the same way you did, an attacker can test any number to reveal the value.

   for i in range(plaintext):
       if F(i,c):
          break

So this must be as follows;

negate the value,
encrypt it with the Paillier,
Sent it to the server.
the server calculates the summation,
the server returns the result.

If there are more than one k-means on the server, and, actually, you are trying to perform

SELECT * FROM table WHERE key_mean = query

you need to apply a different method.


Things already known to adversary before planning an attack This is a very basic and practical question. Since I started reading cryptography recently, these things keep bugging me.

What are the things that an adversary is usually aware of before planning an attack?
Let's say an adversary plans an attack on a server of a big company.

Does he know what encryption scheme/model is being used by the company to protect its data stored in the server?

I think usually companies use very standard and popular schemes that are known already to the cryptographic community since using a totally unknown scheme might have a huge data leakage which the company was not able to discover.

Let's say adversary knows about the model. So what about the specific functions that are used in them. For eg. Pseudorandom generators used in stream ciphers(obviously, the key is not known), or S-box in case of DES etc. Are these things known to the adversary already?

I think these things are usually fixed while implementing the model. And even if these things are known, for example S-box in DES is known, it still won't change the security of the scheme. But even if the company tried to hide the above functions, can it actually increase the security of the data?

Keys

I think this is mainly the information that separates the user and the adversary. But can you tell what are the other things that are hidden in practical implementations?

My assumptions are based on the quote that one should only use encryption schemes that are trusted by the cryptography community. Else there is a high probability that there can be an unknown leakage that an adversary can exploit.

I think usually companies use very standard and popular schemes that are known already to the cryptographic community since using a totally unknown scheme might have a huge data leakage which the company was not able to discover.

Definitely. And remind yourself that implementing cryptography is hard as well. Self made schemes may have side channel attacks, data leaks and whatnot.

Quite often the algorithms that are used are known in advance. They are in design documents, leaks by developers, can be determined from the protocol configuration directly, are specified to certification agencies etc. etc. etc. So we simply assume that Kerckhoff's principle applies.

This is also why cryptographers don't take people seriously when they are confronted with a ciphertext without specifying the algorithm. Finding the algorithms is generally not the problem we're trying to solve.

  I think these things are usually fixed while implementing the model. And even if these things are known, for example S-box in DES is known, it still won't change the security of the scheme. But even if the company tried to hide the above functions, can it actually increase the security of the data?

The same applies as in the above.

  I think this is mainly the information that separates the user and the adversary. But can you tell what are the other things that are hidden in practical implementations?

Anything that is known as a secret. That includes keys, but also passwords, PIN, biometric data (where applicable). Besides keeping things secret, there are of course also other counter measures such as access conditions, number of retries and whatnot. A system never solely relies on cryptography, i.e. cryptography is never the solution, but it may be part of a solution.

  My assumptions are based on the quote that one should only use encryption schemes that are trusted by the cryptography community. Else there is a high probability that there can be an unknown leakage that an adversary can exploit.

Correct. As Bruce Schneier famously summed it up:

  Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break.

with a corollary from Cory Doctorow :

  any person can invent a security system so clever that she or he can't think of how to break it.


Any affine function will do. Let your Sbox be $$S(x)=Mx\oplus c$$ where $M$ is an $n\times n$ binary matrix and $c$ is an $n-$bit constant vector.

The output difference for this Sbox is, for any nonzero $a$
$$
S(x \oplus a)\oplus S(x)=(M(x\oplus a)\oplus c )\oplus Mx\oplus c= M a\oplus c
$$
which is a constant for fixed $a$ so all the output differences for that input difference take on the same value.

For nontriviality pick either $c$ nonzero or $M$ a non identity matrix. The matrix must be invertible (over $GF(2)$) for the Sbox to be invertible, i.e., a proper substitution.

AES with this type of Sbox can be trivially broken.

Edit: See the answer to this question for details.


Why don't we use Blowfish if it hasn't been cracked? Since Blowfish is old, well-audited, and has no published attacks, why are we using AES instead? I know that Bruce Schneier said that Blowfish is insecure and told people to transition to Twofish, but why? AES has many vulnerabilities, such as padding oracle attacks and power-consumption analysis, but Blowfish doesn't have any well-known issues. And Blowfish can take a key up to 448 bits, which is larger than AES's 256 bits. Is there something I am not understanding? It's been under public scrutiny for the longest with the least issues.
Perhaps it is because of Blowfish's small block size?
Context: Is it safe to use Blowfish to encrypt strings of less than 30 characters?

Why don't we use Blowfish if it hasn't been cracked?

The reason is well-known, it has 64-bit block size and therefore it is vulnerable to birthday attacks. This is done for HTTPS and for more information see sweet32;
$$\text{Sweet32: Birthday attacks on 64-bit block ciphers in TLS and OpenVPN}
$$

Is it safe to use Blowfish to encrypt strings of less than 30 characters?
If I don't use it for HTTP, just for storing small strings, is it still insecure?

There is no problem. GnuPG made a recommendation for Blowfish;  Blowfish should not be used to encrypt files larger than 4Gb in size. If you want to use a block-cipher from Bruce Schneier use the successor, the Twofish algorithm, as he said.
This recommendation 4GB makes $\approx 2^{33}$-bytes therefore, they recommended using at most $2^{30}$ blocks of encryption under the same key. With the birthday probability if you encrypt $2^{30}$ blocks you will have
$$(2^{30})^2/2^{64}/2 = 2^{60 - 64-1} = 1/2^{5}$$ probability of collision. This is still a high probability in the attacker's advantage.

What is Sweet32 in short:
The attack performed on the CBC mode of operation where the encryption is $$c_i = E_k(m_i \oplus c_{i-1})$$ wiht $c_{-1}$ is the nonce for the CBC.
Once one encrypts $2^{n/2}$ blocks with one key by the birthday attack we expect a collision on the ciphertext with 50% probability that can be observed by an eavesdropper. This means that $c_i = c_j$ with $i \neq j$ is observed. Since a block cipher is a fixed permutation under a key this implies that the inputs of $c_i$ and $c_j$ must be the same;
$$ m_i \oplus c_{i-1} = m_j \oplus c_{j-1}$$ with changing the side of the values we get $$m_i \oplus  m_j = c_{1-1} \oplus c_{j-1}.$$ That is the eavesdropper knows the x-or of the two message blocks.

A short note padding oracles;
Padding oracle is first described by  Serge Vaudenay in 2002;

Security Flaws Induced by CBC Padding Applications to SSL, IPSEC, WTLS

years later real attacks are performed. Vaudenay applied it to RC5 in CBC mode, and it applies to any cipher that uses CBC mode as long as the server sends the padding-fail as an error. With the padding oracle attack, all messages can be revealed since it is a decryption oracle. Encrypt-than-Mac will prevent this attack.

Update for the comment;
It turns out that OP has X/Y problem; the short string is a password then the obvious choice is the well-known solutions like the argon2 which is the password hashing competition, winner. It has two modes;

Argon2d: is faster and uses data-depending memory access. Data dependency immediately enables side-channel. This is suitable for cryptocurrencies and applications with no threats from side-channel attacks.
Argon2i: uses data-independent memory access and this is preferred for password hashing and password-based key derivations.
If you are not sure about which one to use then you can use the combined mode Argon2id.


Simplified ECC non-point public key example, how it works I know that ECC public key is in fact point on curve calculated by $(x,y) = k \times G$ , while $k$ is random and $G$ is the base point, it performs "Point addition" which involves some math behind.

However, in many ECC examples, take this as example:

domain parameters $(p, q, g)$ and private/public key pair $(b, g^b \bmod p)$

The generation of the public key is simplified to power of base point $g^b$, yet it works perfectly well for the example. Im puzzled by how a $(x,y)$ 2-dimensional public key can be reduced to 1-dimensional and still work?

However, in many ECC examples, take this as example:

That reference doesn't talk about ECC as all; instead, it talks about traditional El Gamal in the group $\mathbb{Z}_p^*$.


Building an LSFR Logical bit map using characteristic polynomials How would one build an LSFR logical map, with a characteristic polynomial such as

$$P(x) = x^4 + x^3 + 1$$?
Also how would you interpret it, and what would you do to  do the reverse it in order to create a characteristic polynomial from an LSFR map? Thank you

The recipocal $P^*(x)$ of a polynomial $$P(x)= a_0 + a_1x + a_2x^2 + \cdots + a_nx^n$$ is given by;

$$P^*(x) = a_n + a_{n-1}x + \cdots + a_0x^n = x^n P(x^{-1})$$

The feedback polynomial that defines the tap points of LFSR. The characteristic polynomial and is the reciprocal of feedback. Therefore;

Let $P^*(x)= x^4 \cdot P(1/x) = 1 + x + x^4 $ be the feedback polynomial LFSR   calculated by the recipocal of characteristic polynomial $P(x)$. Then the taps of the LFSR as follows;

 xxxxx <--
 ||      |
 ++--- ->|
 01234


Why do we need Hash by key? (i'm just trying to find what am I missing...)

Assuming John have a clear text message , he can create a regular hash ( like md5 , or sha256) and then encrypt the message.

John can now send Paul the message + its (clear text)hash and Paul can know if the message was altered. ( decrypt and then compare hashes).

Even if an attacker can change the encrpyted data ( without decrypt) -  - when paul will open the message - and recalc the hash - it wont generate the same hash as the one john sent him.

so why do we need hash by key ?

The question is about an attempt to augment an encryption scheme with an integrity-protection measure, by additionally transferring the hash $H=\mathtt{Hash}(P)$ of the plaintext $P$ together with the ciphertext $C=\mathtt{ENC}(P)$ of the original encryption scheme; and having the recipient of an alleged $(C,H)$ obtain the alleged $P=\mathtt{DEC}(C)$, and accept that $P$ as genuine if $\mathtt{Hash}(P)=H$.

This attempt fails disastrously:

The original encryption scheme is greatly weakened, for $\mathtt{Hash}(P)$ reveals information about the plaintext $P$. An attacker Eve can test with high confidence if a guess of $P$ is correct! If $P$ legitimately sent by Alice is the result of a yes-or-no vote, or otherwise is one in a moderate list of possibilities (e.g. a password), Eve can now recover $P$ without attacking the original encryption scheme at all.
The change provides no integrity protection when used with a public-key encryption scheme, where Alice enciphers a message to Bob using Bob's public key. Eve can choose any message she desires, hash it, and encipher it using Bob's public key, just like Alice.
Even considering symmetric encryption schemes, in many important use cases, the change fails to provide integrity protection against an Eve able to guess/obtain/choose the plaintext, or part of it; these are standard hypothesis, and we have seen with 1 that guesses have been made verifiable by the attempted strengthening. Examples, among many:

a. Many schemes, including the One Time Pad, all Stream Ciphers, and all Block Ciphers employed in the OFB or CTR mode of operation, have the property that $\mathtt{ENC}(P\oplus X)=\mathtt{ENC}(P)\oplus X$ (where $\oplus$ is bitwise Exclusive-OR). In these cases, Eve is able to change the message $P$ to $P'$ of the same length: Eve uses $\mathtt{Hash}(P)$ to confirm her guess of $P$, chooses $P'$ she want to substitute, computes $\mathtt{Hash}(P')$, and computes $C'=\mathtt{ENC}(P')$ as $C'=\mathtt{ENC}(P)\oplus P\oplus P'$.

b. Most schemes have the property that truncating the ciphertext correspondingly truncates the plaintext (often, with restriction to truncation at block boundaries). An adversary unable to guess the end of a message, but knowing the start (because that is conventional, or transmitted in clear alongside) can truncate the ciphertext, and compute the corresponding plaintext's hash. Thus Eve can make a forgery that deciphers to the truncated original plaintext, and passes the hash check.

c. Many symmetric encryption schemes, including all Block Ciphers employed in the ECB, CBC or CFB mode of operation, have the property that decryption of a segment of the ciphertext leads to the corresponding fragment of the plaintext (often, with restriction to segmenting at block boundaries, and need to adjust the IV). If Eve can persuade Alice to encipher some message $P||P'$ of Eve's choice (a standard assumption; say, $P$ is a nice image that a viewing program will show when fed with the file $P||P'$), Eve now has $C'=\mathtt{ENC}(P')$ for $P'$ of her choice, and can compute the matching $\mathtt{Hash}(P')$.
Many common hashes (including MD5, SHA-1, and all SHA-2 hashes) have the length-extension property, which is that from knowledge of the length of $P$ and $\mathtt{Hash}(P)$, it is easy to determine a short $F$ such that for any $X$, it is easy to compute $\mathtt{Hash}(P||F||X)$. For some symmetric encryption schemes and plausible assumptions (similar to 3c), it might be possible to extend an unknown $P$ with some $F||X$, deduce $\mathtt{ENC}(P||F||X)$ from intercepts, and compute $\mathtt{Hash}(P||F||X)$ from the length-extension property.
The scheme is not protected at all against replay of earlier messages.

A Message Authentication Code (or keyed hash, which includes HMAC) can be used instead of the hash to fix 1/2/3/4 (but something extra is needed for 5). The key used for the MAC should be different from the key used for the encryption scheme, in particular if the MAC has building blocks in common with the encryption scheme.


Why is it a quadratic equation? In Groth-Sahai NIZK proof system, they have defined something called Quadratic Equation in $\mathbb{Z}_n$ as shown below. But, my idea of quadratic equation was a second order polynomial equation in a single variable, something of the form $ax^2 + bx + c = 0$. Then how is the below equation a quadratic one?

$ax^2+bx+c=0$ is the general expression of a quadratic equation in one variable. Here, there are more than one. You may want to look into how the degree of a multivariate polynomial is defined.


What is the NIST recommended maximum bias for random number generators? What is the maximum bias recommended by NIST for random number generators?
This answer says that it is $2^{-64}$.
Is it same for all applications? Does NIST have a publication with more information?
I tried to browse through NIST Recommendation for Random Bit Generator Constructions, but couldn't find it.

Yes, NIST recommends $\epsilon \le 2^{-64}$. They consider such a sequence to have "full entropy".  It's in the definitions (page 4) of SP800-90C.

Converting that to a probability bias, $P(x_i = 0, x_i = 1) \approx 0.5 \pm 2^{-66}$.
The interesting thing is that if the Leftover Hash Lemma is used, $\epsilon$ can be set by the designer.  ID Quantique TRNGs are designed with extractors such that $\epsilon \approx  2^{-100}$.


SHA512 vs HKDF key expansion I'm working on a secure file storage server. This server allows users to upload and download files based on a "seed". This "seed" is a 128-bit value.

From this 128-bit seed, we run SHA512 to derive a 256-bit key, 128-bit IV and 128-bit file identifier used to find the file on the server. The key and IV are then used to encrypt the file with AES in GCM mode. Only the file identifier is sent to the server at any point, encryption is done completely client side.

The only point at which I'm concerned here is the SHA512 of the 128-bit seed. Would there be any benefit to going to an HKDF based key expansion? It seems to be designed for this purpose, but considering we're able to achieve everything we need with a single invocation of SHA512 I'm unsure of the benefit. As far as I can tell, HKDF is still relying upon hash functions to randomly distribute entropy.

I understand there may be some theoretical benefit here, I'm just looking for details on how this benefit may work, what a theoretical attack might look like and if there's anything practical which could be used to exploit this today.

I'm not aware of any attacks on SHA-512 this way. I would create a small function to validate that the input size to SHA-512 is indeed identical to the seed size though, just in case. Even without that the function should be secure. Kind of related is my question about KDF1 and KDF2.

Note that implementation of HKDF-expand from a hash should be pretty easy, especially if a HMAC construction is already available. KDF1 or KDF2 would be even easier, it would probably be trickier to find test vectors for those KDF's though. So you might ask yourself why not to use HKDF-expand.

Generating a 256 bit key using a KDF over a 128 bit means that the security margin would remain at 128 bit. Basically it's fine as long as you don't claim a security margin of 256 bit. Just claiming AES-256 bit encryption would probably mean the same thing to most people.


Rounding down in the exponent of group element I have been struggling to find the algorithm $\mathcal{A}$ in the following. Let $(G,g,q)$ be the group parameter, $p << q$, $x\in \mathbb{Z}_q$, can we build the following algorithm:

$$\mathcal{A}(g,g^x,g^{x^k},p,q) = g^{y^k} \text{ where } y = \bigg \lfloor x \cdot \frac{p}{q}\bigg\rfloor \in \mathbb{Z}_p$$

can we build the following algorithm:
$$\mathcal{A}(g,g^x,g^{x^k},p,q) = g^{y^k} \text{ where } y = \bigg \lfloor x \cdot \frac{p}{q}\bigg\rfloor \in \mathbb{Z}_p$$

It would appear that such an algorithm that works for any input would allow us to compute discrete logs (hence we hope the answer is "no" in general, however it might be possible for certain inputs (although I personally have my doubts).
One way to do this to evaluate the discrete log of $g^x$ would be to start with evaluating $\mathcal{A}(g, g^x, g^x, 2, q)$ (that is, with $k=1$); if $x < q/2$, this evaluates to $g^0$, if $x \ge q/2$, this evaluates to $g^1$, thus halving the range of where $x$ might be.
Then, we would follow it up with $\mathcal{A}(g, g^x, g^x, 4, q)$, which would allow us to further halve the possible range of $x$.  We could keep on going until we've recovered all of $x$, hence solving the DLog problem.


Cryptographic hash function for 32-bit length input keys Since I'm unfamiliar with cryptography area I haven't been able to find cryptographic hash functions for 32 bit integer keys. It seems all such functions (as I saw here) are designed to digest a stream having hundreds of bytes. What I need is a cryptographic hash function that receives a 32-bit length key, and – preferably with basic math operations (addition, shifting, negating, multiplication) – delivers a preferably 32-bit length hash of the key. Later on I will crop 1, 3, 7, 15, or 31 least-significant bits of the output and use it in my application. Can someone please introduce a suitable algorithm for this purpose?

One more thing to ask: can I rely on simple hash functions on integers introduced here for this purpose? Can I expect them to have quite same characteristics as cryptographic hash functions, such as avalanche effect, for 32 bit integers?

Edit:
The function I'm trying to find or come up with receives an input 32-bit integer number (I referred to it as key in the question description), and delivers a 32-bit length hashed output. What I'm looking for in the output is that by changing even a single bit of the input integer, output varies (preferably drastically in Least Significant Bits). There can be hundreds of millions of keys, so it's better that its output range has a good distribution. Low computation complexity with simple math operations is preferred.
The variation of LSBs in output is much preferred since I'm going to crop LSBs as I described in the question. For example, if I'm going to crop 1 LSB bit, a parity bit would suffice. Or if I want to crop 3 LSB bits, 3 LSB bits of checksum is enough. But if I'm going to crop 7, 15, or 31 LSB bits, checksum would waste 2, 10, and 26 bits respectively.

The question asks for a "cryptographic hash function" with 32-bit input and 32-bit output, such "that by changing even a single bit of the input integer, output varies (preferably drastically in Least Significant Bits)". In cryptographic terms, that criteria is reminiscent of good diffusion of input changes.

The non-cryptographic hash functions linked to in the question only vaguely aim at something similar (if we assume that unsigned is 32-bit, unsigned char is 8-bit, and some conversion from 32-bit input to void *key, int len bound to be messy or dependent on endianness). Many of the proposed constructions do not pass the stated criteria. From a quick glance, at least add_hash, xor_hash, rot_hash, djb_hash, sax_hash, fnv_hash, jsw_hash and elf_hash have the problem that some bit of the input never influence the low-order bit of the output.

Out of my head, here is some simple C code matching the stated objective:

#include <stdint.h>
// some arbitrary permutation of 32-bit values
uint32_t perm32(uint32_t x) {
    int n = 12;
    do // repeat for n from 12 downto 1
        x = ((x>>8)^x)*0x6B+n;
    while( --n!=0 );
    return x;
}

It uses techniques borrowed from cryptography, namely:

multiple rounds with equivalent structure, each performing a transformation of the state x; these transformations are reversible (avoiding a reduction in the number of possible results as the number of rounds grows), non-linear and with diffusion in both directions (insuring overall diffusion), and different at each round; the combination gives high confidence that near-perfect diffusion is reached after some moderate number of rounds, and remains so with more rounds;
x ↦ (x>>8)^x is a reversible transformation with right diffusion (8 allows a speed-up on common low-end CPUs, is high enough that the leftmost bit has traveled to the right in a reasonable 4 rounds, while being low enough that the eXclusive-OR acts on many bits);
x ↦ x*0x6B is a reversible transformation with left diffusion, amounting to repeated addition modulo $2^{32}$ (the multiplicative constant must be coprime with the modulus; 0x6B is high enough that the rightmost bit has traveled to the left in a reasonable 5 rounds, while allowing fast implementation on any CPU with an 8-bit multiplier, and has binary representation 01101011 with some irregularity);
x ↦ x+n for given n is a reversible transformation, introduced so that rounds are different, and x=0 is not a fixed point;
alternating bitwise eXclusive-OR and addition modulo $2^{32}$ results in non-linearity.

I guesstimate from its structure that the function already has fair diffusion at 6 rounds; and with 12 rounds is good enough for almost all uses where using an arbitrary reversible function (rather than an arbitrary function) is fit, and no intelligent adversary is involved.

Applying a cryptographic hash like MD5, SHA-1 or SHA-256, and truncating the output to the first 32 bits, matches the stated objective (in an extremely overkill manner). Each bit in the output is essentially a (different) function of all input bits, that behaves much like a random function among the $2^{(2^{32})}$ such functions, except that it has a short description: being that bit of the output of the hash. Notice that the resulting transformation is not reversible (much likely, some 32-bit outputs are reached for several different 32-bit inputs).

As test vectors for a possible implementation, here is an input-output table showing the effect of changing an input bit starting from input A7000AB9h, for the MD5 and SHA-1 hashes; all values are in hexadecimal.

 input        MD5     MD5 (BE)   SHA-1
A7000AB9    C4D1EA9D  4DDC786B  BF7C439D
A7000AB8    6F8D506F  9415C265  8C104649
A7000ABB    B140436D  60A906F5  607EA4C3
A7000ABD    55D15F80  C500E8C7  A4E02774
A7000AB1    34B3EFD1  D6EA08ED  7A0181D9
A7000AA9    2FBAC43D  CCF97629  E727356B
A7000A99    2D4BCF14  546B1E97  5707C499
(..)
A6000AB9    84DF82C6  E9319225  5DE2A3A7
A5000AB9    0D314C76  0D70D1D8  39DB8C96
A3000AB9    38A46809  62B798C4  BD586E3C
AF000AB9    E4F2D5DE  57A4E8E1  AF434967
B7000AB9    2E0671E2  25EFAE88  8D0C6003

Note: for MD5, I have also shown what happens if Big-Endian convention is used in converting 32-bit integers to octet strings and back rather than the little-endian convention used by MD5, because that's what you'll tend to get when asking the hash of A7000AB9 to an online tool (scroll down for the results).

While the above solves the problem as stated, it might not be what is actually needed in the (unstated) practical situation. In particular, the functions defined here are public, thus anyone can quickly compute them. And because the input is short, it is possible to try all input values to find those (if any) that give a particular output value, even if the transformation is not directly reversible.

Cryptography has other constructs that might be better suited. In particular we have Message Authentication Codes, that accept a secret key, and a message (which would be the 32-bit input, even though it is named key in the question), and outputs an authenticator (that can be truncated as we did for hashes). That would behave much like the above, but some adversary without the key is left totally in the blues about output that is not known from earlier observations. A common suitable MAC would be HMAC-SHA256.


In veracrypt when i generate a random keyfile, does the size of the keyfile mean anything? thanks for looking at my question, i have been getting several different answers to this question so i thought i might ask it here, when i create a random generated keyfile in veracrypt, does the size of the file mean anything? for example, does a larger file mean it's more secure?

when you generate a random key file it says that it can create the file anywhere between 64 and 1048576 bytes, so does that mean that a 1048576 byte file is more secure then a 64 byte file?

thanks.

When you generate a random key file it says that it can create the file anywhere between 64 and 1048576 bytes, so does that mean that a 1048576 byte file is more secure then a 64 byte file?

Mathematically speaking no. 64 bytes is 512 bit at which point guessing the keyfile is as expensive as guess the data encryption keys used for volume directly. Note that even if you use double or triple encryption a 512-bit random string is well beyond feasible for anybody to guess physically, as even guessing a 256-bit secret is.

The only argument for something larger than 64 bytes is that if you assume an attacker that can only say leak 1 byte per hour from memory / your filesystem (or something similarly slow), it would take longer to assemble 1MB than to assemble 64 byte. Of course the question of whether assuming such an adversary is sensible or not depends on your threat model...

In case you are wondering why it says above that the key is 512-bit long when AES-256 is used. The reason is that XTS uses two AES keys which are derived from the password in a secure manner transferring the security of the password to the combined key.


Any stream cipher with avalanche effect? As far as I know, all stream ciphers work by generating a stream of pseudo random bytes, and XOR it with the plain text to get the cipher text. It has the property that one bit change in the cipher text results only the corresponding bit change in the decrypted message.

Is there any stream cipher that has the avalanche effect, where one bit change in the cipher text will result about half of the bits changed in the decrypted message after the corresponding bit?

A stream cipher, by definition, acts on individual bits at a time. This effectively means that bits later in the plaintext cannot affect bits around the beginning of the ciphertext. It can, however, feed the ciphertext back into the state of the PRNG to affect all future bits. This can be seen in the CFB (Cipher Feedback) block cipher mode. It acts similarly to a stream cipher, in that each ciphertext bit can be drawn one at a time, but they feed back into the system to affect all future bits.


Proof that $g(x) = f(x) || f(f(x))$ is a OWF when $f$ is a OWF Assume that $f$ is a one-way function (OWF), and let $\mathbin\|$ denote string concatenation.
Consider the function $g$ defined by $g(x) = f(x) \mathbin\| f(f(x))$. It is easy to prove that $g$ is a OWF as well, assuming that $f$ is length preserving (that is, $|f(x)|=|x|$ for all $x$). Here's a sample proof, taken from Lindell's final exam:

Now consider the case where $f$ is a general OWF, not necessarily length preserving. This case is considered in Katz & Lindell book, 2nd Edition, Exercise 7.8:

Q: Why Lindell's proof for length-preserving $f$ does not work?
A: In the proof mentioned above, $\mathcal{A}'$ invokes $\mathcal{A}$ on $y || f(y)$, which upon success, returns $x'$ such that $f(x') \mathbin\| f(f(x')) = y \mathbin\| f(y)$. However, this does not entail $f(x') = y$, as the length of $f(x')$ might be different from the length of $y$.

My question is, how to prove that that $g(x) = f(x) \mathbin\| f(f(x))$ is a OWF when $f$ is a general OWF?

/!\ the counter-example I build below is not a formal refutation of the statement, a more rigorous analysis is needed, but it gives an intuition of why I think that $f'x\mapsto f(x)\mathbin\|f(f(x))$ is not necessarily an OWF (thanks to Christian Matt for pointing out the necessity of a more rigorous analysis).

It seems to me that $f': x \mapsto f(x)\mathbin\|f(f(x))$ is not necessarily a OWF when $f$ is not length-preserving. Consider the following function $f$:

$h$ is an arbitrary length-preserving OWF. $g$ is an arbitrary OWF that compresses its input by a factor two.
$f$ is defined as follows: on input $x$, if $|x|$ is odd, then $f(x) = 0^{|x|} \mathbin\| h(x)$. Else, if $|x|$ is even, then if $|x|/2$ is also even and $x$ is of the form $x' \mathbin\| 0^{3|x|/4}$, return $x' \mathbin\| 0^{|x|/4}$. Otherwise, if $x$ is of the form $x'' \mathbin\| 0^{|x|/2}$, return $h(x'')$. In all other cases, return $g(x)$.

So, as you can see, $f$ maps $n$-bit inputs to $n/2$-bit outputs when $n$ is even, and to $2n$-bit outputs when $n$ is odd. I think that one can prove that $f$ is indeed an OWF by picking an appropriate function $g$ whose image does not intersect with $\{0\}^n \times \{0,1\}^n$ so that on a random input $x$, the probability that $g(x)$ is of the form $x' \mathbin\| 0^{3|x|/4}$ is very small (as this is the "easy to invert" case).

Now, let $n \equiv 2 \bmod 4$ ($n$ is even, and $n/2$ is odd). Then when you receive $y = f(x)$ for a random $n$-bit input $x$, it is easy to invert $y \mathbin\| f(y)$: with very good probability, $x$ is not of the form $x'\mathbin\|0^{3|x|/4}$, hence $f(x) = g(x)$ (which is of odd length $n/2$). In this case it holds that $f(y) = 0^{n/2}\mathbin\|h(y)$. But this makes inverting $y \mathbin\| f(y)$ trivial:

$$y\mathbin\|f(y) = y\mathbin\|(0^{n/2}\mathbin\|h(y)) = (y\mathbin\|0^{n/2})\mathbin\|h(y) = f(y\mathbin\|0^{3n/2})\mathbin\|f(f(y||0^{3n/2}))$$

Hence one can simply return $y\mathbin\|0^{3n/2}$ to successfully invert $f':x \mapsto f(x)\mathbin\|f(f(x))$. So unless I'm missing something / making a mistake, $f': x \mapsto f(x)\mathbin\|f(f(x))$ is not necessarily a OWF when $f$ is not length-preserving.

EDIT: corrected mistakes in the previous version of my counter example.


How does the key size per data bit influence the security? The likelihood of breaking, for instance, an AES-128 cipher is 100% after $2^{128}$ tries in brute force, meaning that I've got to try $2^{128}$ keys to certainly break it.

What if I (hypothetically) had recorded $2^{128}$ bits of data encrypted with the same AES-128 key? How does this help in cryptoanalysis?

And how is the situation differently if or if not a part of this data (e.g. word file headers, specific telnet handshakes, whatever) was known plaintext?

Quite apart from the correction that Reid made (it takes $2^{127}$ attempts to achieve a probability of 50% of finding the right key; with $2^{64}$ attempts, the probability of success is $2^{-64}$), with AES, there is no known way to take advantage of known (or even chosen) plaintext to speed up any brute force search; even with $2^{64}$ chosen plaintext/ciphertext pairs, the best known attack is to pick one pair, and apply a brute force search on that pair.


How to detect duplicate values of sensitive data that needs to be encrypted This was a question that was posted on the information security exchange but was suggested I may get a better answer here.

The link suggested in the original post is similar, but I think a search index for a simple comparison here is potentially not efficient.

I have a scenario where text values that are considered sensitive (not passwords) need to be encrypted for persistence onto a database.

The key requirement here is being able to identify if a value being received has been received in the past.

One solution that is being considered is to Encrypt the each value using the AES encryption algorithm with the same key and IV to generate the same cipher for each value received making it easy to detect if this value has been received in the past. However I have concerns regarding the strength and security of this solution.

The amount of data to be encrypted is quite small, < 50 characters

So the question is, what other options are available to meet these requirements in a better way?

First, it is important to note that one important property of encryption is that you cannot determine if the same ciphertext is encrypted twice. However, assuming that you wish to give up on this property but you want it to be completely secure otherwise, then you still have to be careful.

Using regular encryption with the same IV is problematic. If you are using CTR mode then this completely breaks the encryption. If you are using CBC mode then if the first block is the same but the second is different, then you will be able to detect this.

The best solution is to use the AES-SIV or AES-GCM-SIV modes of operation with a fixed IV/nonce. These modes have the property that when encrypting different messages with the same IV, then you cannot learn anything apart from the fact that the plaintexts are different. Of course, if you encrypt the same message with the same IV then you get the same result.


Is it possible to construct a multiplicative group from $\mathbb{Z}_n$ if $n$ is not a prime number? With $n$ being a prime number I know we can generate groups over multiplication. Is it possible the other way around ($n$ not being a prime)?

Yes. The subset of $\Bbb Z_n$ of integers that are relatively prime to $n$ (otherwise said: the set of $x$ in $\Bbb Z_n$ with $\gcd(n,x)=1$ ) form a group under the multiplicative law of $\Bbb Z_n$ (multiplication modulo $n$ ).

That finite group is noted $(\Bbb Z_n^*,*)$ or just $\Bbb Z_n^*$, or $(\Bbb Z/n\Bbb Z)^\times$. It has $\varphi(n)$ elements, where $\varphi$ is the Euler totient.

That group is cyclic (otherwise said: generated by a single element) iff $n$ is in one of three forms: $4$, $p^k$, $2p^k$ (for $p$ an odd prime and $k\in\Bbb N$, including $k=0$); that is for $n$ in A033948.

Thanks to Poncho for a useful comment.


XMSS MT for height 80 The XMSS RFC supports only tree heights of 60, which makes the chosen keypair to sign up to 2^60 messages, which is not practical for the use of SSL and so on. The paper https://eprint.iacr.org/2017/966.pdf mentions that it is possible to increase the 60 number to 80, which would be sufficient for SSL use. Why is this treeheight not supported in the RFC?

Why is this treeheight not supported in the RFC?

I'm not Andreas, and he did not mention this to me specifically.  He has mentioned that the CFRG did ask him to limit the number of parameter sets he defined.  My speculation is that he couldn't imagine any situation that would need more than $2^{60}$ signatures generated from a single private key.
Do you have such a situation?  Even if you were able to generate a signature in a nanosecond (which is far faster than what is achievable today), it would take over 36 years to use up all $2^{60}$ signatures - do you have a use case that would go beyond that?

he XMSS RFC supports only tree heights of 60, which makes the chosen keypair to sign up to 2^60 messages, which is not practical for the use of SSL and so on

Why would $2^{60}$ signatures not be sufficient for TLS?


correct a corrupted shared key Suppose we have an almost shared secret. For example if we have a noisy connection to a shared secret source of randomness.
So Alice has $k_1$ and Bob has $k_2$ similar but not necessarily identical to $k_1$. One formalization could be:

$\operatorname{hammingDistance}(k_1,k_2) << \operatorname{length}(k_1)=\operatorname{length(k_2)}$

If the keys are similar in absolute terms we could have Alice send a message with Mac and Bob brute force small variations of his key.

Can we do better? Perhaps ending up with a shorter shared key.
Obviously I would not want to rely on other key exchange or asymmetric primitives.

If the maximum Hamming distance $d$ between the keys is small enough (and to a lesser degree if the key size $n$ is bits is small enough), one obvious technique is that Alice computes $H(k_1)=h$ for $H$ some cryptographic hash, e.g. SHA-256; and sends $h$ to Bob. He explores $x$ of small Hamming weight until $H(k_2\oplus x)=h$, and when he finds such $x$, he knows $k_1=k_2\oplus x$. There are $\displaystyle\sum_{i=0}^d{{n}\choose i}$ values to try. That's $2^{\approx40.5}$ hashes for a $n=128$-bit key with up to $d=8$ garbled bits, which is already inconveniently slow/costly for Bob, thus that does not work at all for sizably larger $d\log_2(n)$.

If the key has enough entropy and thus can't be enumerated (e.g. it has $n\ge128$ uniformly random and independent bits) and is used to key some fast cryptographic algorithm unrelated to $H$ (e.g. AES when $H$ is SHA-256), this reveals nothing useful about the key. However, beware of interactions! As an extreme example, if the key is used as an HMAC-SHA-256 key, and $H$ is SHA-256, and $n>512$, then $k_1$ is entirely compromised, because by definition of HMAC for long keys, $\forall M,\,\text{HMAC-SHA-256}(k_1,M)=\text{HMAC-SHA-256}(H,M)$.

Note: this is essentially the question's brute force method, except that by processing the key thru a hash independent of the normal use of the key, we avoid using the key in one of its possible intended later way. A more formal approach could always use $k_1$ as the key of a Key Derivation Function, with one derivation parameter reserved for repairing $k_1$.

If the key is large with aplenty entropy (e.g. 256-bit or more), and the above can't be applied because $d\log_2(n)$ is too large, or we want no guesswork for Bob, another option is to use Forward Error Correction: Alice computes and reveals $C=\text{FEC}(k_1)$ of $c$ bits, with $c$ large enough to correct the expected error knowing $k_2$, but still a small fraction of $n$.

It must be used a FEC system where the message normally sent for payload $M$ is $M\mathbin\|C$ with $C=\text{FEC}(M)$, which is common, and includes some Turbocode (as used in 3G/4G mobile communications). The FEC should have little or no extra error-detection capability after correction.

Alice computes and sends $C\gets\text{FEC}(k_1)$, and $h\gets H(k_1)$ as before.

Bob receives $C$ and $h$, applies the FEC recovery to $C$ and $k_2$ to get a tentative $\widetilde{k_1}$, and if $H(\widetilde{k_1})=h$ concludes that $k_1=\widetilde{k_1}$.

Compared to the previous scheme, at most $c$ bits of entropy have leaked about $k_1$, and for a full-entropy $k_1$, we are safe as long as $n-c$ remains large enough to make $k_1$ unguessable; and the FEC, $H$, and the algorithm used for $k_1$ do not interfere.

If we again allows some guesswork for Bob, we can reveal less about the key, as follows.

Alice

computes $C\gets\text{FEC}(k_1)$ as above
optionally applies some public pseudorandom permutation $P$ to $C$, yielding $C'$ (or just $C'=C$)
splits $C'$ into $C_1\|C_2=C'$, with $C_2$ of $r$-bit, e.g. $r=32$ (or smaller, down to possibly $1$);
computes $h\gets H(C_2\mathbin\|k_1)$
sends $C_1$ and $h$

Bob

recovers $C_1$ and $h$
for up to $2^r$ values of $\widetilde{C_2}$

deduces the corresponding $\widetilde{C}=P^{-1}(C_1\mathbin\|\widetilde{C_2})$ (or just $\widetilde{C}=C_1\mathbin\|\widetilde{C_2}$ for no optional pseudorandom permutation)
applies the FEC recovery to $\widetilde{C}$ and $k_2$ to get a tentative $\widetilde{k_1}$
if $H(\widetilde{C_2}\mathbin\|\widetilde{k_1})$ matches $h$

concludes that $k_1=\widetilde{k_1}$, and proceedq to use that with Alice.

if no match is found, stops with failure.

$C_1$ was $c-r$-bit, thus at most that much entropy has directly leaked. The pseudo-random permutation allows a simple security argument that the attacker's best strategy has cost $O(2^{n-c+r})$ operations for full-entropy $k_1$ even for pathological FEC, but is probably not necessary in practice.

If $k_1$ is not full-entropy, then $O(2^{\text{Entropy}(K_1)-c+r})$ work must remain infeasible to the adversary, and if we want a simple security argument (including if $k_1$ is used only in part), we can pass $k_1$ thru another public PRP before applying the whole scheme, and pass it thru the inverse permutation in the end.

If wanted, the PRPs can be built from a MGF as in OAEP.


How do I demonstrate that a PRNG not designed for cryptography is not suitable for generating passwords? This is a replication of this question on Stack Overflow. There's class Random in .NET runtime which is designed for use as a cheap fast source of pseudo-random numbers for simulation - very fast, seed can be passed in explicitly, emits easily reproducible sequences.

This class is often misused for generating passwords and similar secret stuff. Here's a question showing one possible attack on this PRNG, but it only works in a very specific scenario (when a lot of data is emitted in series) and also takes some time - up to a year on a single CPU.

Is there a clearer and faster way to show that passwords generated using data from class Random() are much weaker than typically expected?

There are two key things that a secure PRG should have that you probably won't have with Random in this case. A secure PRG should not allow someone with access to some of the output to learn more about any of the other output, and it should be securely seeded.

On the first point: If you're generating passwords that are supposed to be independently secure, you have to assume that the other passwords are going to be known to a malicious adversary at some point. (Perhaps the attacker is actually a user of your program and thus given these passwords directly.) If an attacker somehow learns a large number of passwords, it raises concern that he could derive (fully or partially) other passwords he should not know. I don't know much about Random's PRG in specific, but this is why an attack like one mentioned by Ilmari would be important.

On the second point: The seed space is pretty much guaranteed to be insecure. The default constructor for Random says:

  "The default seed value is derived from the system clock [...] different Random objects that are created in close succession by a call to the default constructor will have identical default seed values".

This implies that the seed is determined purely based on the timestamp.

However: Any PRG seeded only by a timestamp is insecure. There is a temptation to think that it's hard for an attacker to guess exactly what time a timestamp was generated, but this is not true. If the attacker has any idea about the time frame when the timestamp seed was created, it limits the range of seeds they need to attack (because they will only need to test timestamps from the interval of time that the seed was generated from). But modern timestamps on personal computers do not have a small enough resolution to provide a total space that is large enough to resist brute-force attacks.

For example, assume you can get a timestamp accurate to one microsecond (a thousandths of a millisecond). That's better than any modern PC (that I am aware of) will provide. That provides 1,000,000 possible timestamps per second, which yields 86,400,000,000 timestamps per day, which is roughly 37 bits of total space. This is not cryptographically secure and easily brute-forcible if the attacker knows a 24-hour time frame the seed was generated. Over the course of an entire year, the timestamp space is still only about 45 bits, which also not cryptographically secure. If the attacker merely knows the year the seed was generated for the PRG, they can still brute-force it.

The numbers are more bleak with a more realistic timestamp resolution of only 1,000 timestamps per second. (Ilmari's answer suggests C# may only be as accurate as a millisecond.) That yields a timestamp space of only about 35 bits per year. (For reference, I think my old laptop can attack that in less than two weeks.)

It gets worse: The constructor for Random that takes a user argument as the seed only takes a 32-bit integer. This prevents you from possibly generating your own superior seed and using that, because you can only provide 32 bits of a seed. It also implies that the internal seed is limited to 32 bits for the default constructor case. 32 bits is not cryptographically secure, and would allow the attacker to brute-force the seed regardless of whether he knows the original time it came from.

In contrast, the secure PRG provided by C# should resist attacks using known output and should consult a good entropy source (it may be a wrapper to the same source as CryptGenRandom) for the seed.

So ignoring the cryptographic strength of the actual PRG implemented in class Random, I would say that it is insecure based on it's seeding alone. The default seed is too predictable and is not large enough.


How to Share One Time Pad? Supposing I wanted to send a one-time pad to a friend. What would be a good way to do that, supposing that it could be intercepted? At first blush, encrypting it would seem safe, because the encryption would seem impossible to crack, given that what it encodes is random (result of unsuccessful decryption is not obviously indistinguishable from successful deception). Yet perhaps there is still a risk is if the encrypted one time pad and a message encoded with it were intercepted.

The strength of the scheme cannot be higher than its weakest element. Using OTP can give an impression of unbreakable strength, but actually the whole strength is the same as the strength of the encryption method used to share OTP keystream (AES?). Thus, the usage of OTP in such a scheme gives not more security than using normal encryption.

To your question How to share... ? For instance, you could deliver the OTP keystream to your friend in person, or your friend picks it up in person.


Selecting a large NUMS Safe prime Suppose I want to use the following simple hash function.
For a mesage $m$, take some public $a$ and prime $p$ and raise $a^m \bmod p$ (never mind the computational expense of this operation).

This hash function is secure because the discrete log problem is hard, but only if $p-1$ has a large prime factor (to avoid being broken by index calculus). However, I figure if everyone's going to use the same $p$, I might as well choose $p$ so it's largest factor is as large as possible, in other words choose $p$ to be a Safe prime (meaning $\frac{(p-1)}{2}$ is also prime).

So how can I choose p to be a Safe prime, but also make it a Nothing-Up-My-Sleeve number for the purpose of constructing a good cryptographic hash protocol.

Then I'll choose $a$ to be the smallest generator $\bmod p$ (that's easy to check for Safe primes because all I need to do is find the smallest $a$ for which $legendre(a,p)=-1$).

Well, the obvious answer to 'how to find a Safe prime that is also a Nothing-Up-My-Sleeve' number would be to take one of the primes listed in RFC 3526.  These primes (which come in several sizes) are all of the form $p = 2^n - 2^{n-64} - 1 + 2^{64} \cdot ( \lfloor 2^{n-130} \pi \rfloor + i )$, where $i$ is the smallest nonnegative integer such that both $p$ and $(p-1)/2$ are prime.  Having most of the bits within the modulus be from the binary expansion of $\pi$ would appear to satisfy the Nothing-Up-My-Sleeve property.

Also, I don't know if it is wise to pick a generator; after all, from the hash $a^m \bmod p$, the attacker can deduce the value $m \bmod 2$ if $a$ is a generator.  It would seem more prudent to have $a$ be a quadratic residue (and with the RFC 3526, along with any safe prime that is $p \bmod 8 = 7$), $a=2$ is such a quadratic residue, as well as making the exponentiation operation slightly cheaper.


Random numbers used for ECC Diffie-Hellman As the first step for generating a secret DH key a uniformly distributed random number $k$ must be generated, which is used to calculate the $k$-th exponent of the basepoint $A$. Depending on the group order $n$, $k$ can be between $1 \ldots n-1$ .

The binary representation length of the group order is 32 Bytes in my case, but not all bits of those $32 \cdot 8=256$  bits are used, since the group order is slightly smaller than the prime $p$, and also $p$ is smaller than $2^{256}-1$ . Therefore if I generate a 32 Byte random number $k$ , sometimes it is larger than $n$. When this happens, is it allowed to take the modulo $n$ of this number to get a new randon number

$k' = k \,\, mod \,\, n$

and use that instead? I was told to do it in that way.

First I was tempted to confirm that, but then I see that the upper end of the intervall $1 \ldots 2^{256}-1$, namely $n \ldots 2^{256}-1$ is mapped back into $1 \ldots 2^{256}-1-n$ . And therefore the distribution of random numbers for the target interval is not uniform anymore, since each representative within the interval $1 \ldots 2^{2561}-1-n$ is double-weighted - one time from the original interval and another time from the mapped back interval, so the odds for this interval are doubled as compared to numbers outside the interval. And what to do with $k'=0$, when $k=n$ ?

The other option would be to generate a random number exaktly between 1 and n-1.

Since I'm not 100% sure but this was a tip from a really experienced crypto-programmer I'm wavered between the two options...

Your analysis is correct, generating a random 32 Bytes number and reducing it modulo $n$ gives an incorrect distribution (in general). I see three natural solutions to this issue: (I'm not a programmer and do not know which one would be the most suited for efficiency)

1) Generate the random number directly between $1$ and $n-1$ as you suggested

2) Generate a random $32+\kappa$ Byes number, where $\kappa$ is a security parameter (e.g. $\kappa = 10$ for 80 bits of security), and reduce it modulo $n$. This gives a distribution statistically close to uniform over $[1, n]$

Explanation: so, you have this $256$ bit modulus $n$, and you pick (say) a random $336$ bits integer. You do not obtain a uniform distribution by reducing it modulo $n$, but "almost": let us write $2^{336} = n \times N + R$, with $R < n$ ($N,R$ are the quotient and remainder of the Euclidean division by $n$). Intuitively, if we had generated our number between $1$ and $n \times N$, we would indeed have obtained a uniform distribution when reducing it modulo $n$ (as it is a multiple of $n$). The bad case happens when the random number we generate is between $n\times N + 1$ and $2^{336}$. But this happens with probability at most $R/2^{336} < 2^{256}/2^{336} = 2^{-80}$, which is extremely unlikely. Thus, by adding some security parameter to the size of the sampled bit strings, you ensure that you'll get a distribution statistically close to uniform.

As poncho pointed out in a comment, when $n$ is already chosen very close to $2^{256}$, then there is no need to add such "security bits", taking a random 256 bits number will already give something close to uniform (my answer focused on the most general case).

3) Generate 32 Bytes integers and use rejection sampling: if a number is higher than $n$, ignore it and restart until you get a number smaller than $n$. This gives a uniform distribution over $[1,n]$ and is efficient if $n$ is very close to $2^{256}-1$

Any of those solution should be a proper fix to the problem; the direct modulo reduction seem theoretically unacceptable to me (but might be accepted on the basis that it still provides some good security level in practice, enough at least to circumvent any known attack, even though it's a bit dirty).

EDIT: the case $k'=0$ when $k=n$ that you mention is not a problem as it has a negligible probability to happen.


Can I save space for short messages by using encryption with private key instead of a signature? Let's say I have a message, a Private Key and a Public Key.

Normally if you want to see if the message is unaltered and is from the sender you would have the message part + signature part, which you can verify using the senders Public key.

This will lead to some extra data, which I want to work around

[ message (1 kb) ] [ verification part (?? bytes) ]

My solution to this problem is to encrypt the message using the private key, and to decrypt it using the public key.

This way it should be certain that:

The message is unaltered
The message is really from the sender

In short:

Sender:
Encrypt Message using Private Key

Receiver:
Decrypt Message using Public Key

Is this safe? So is this a way to:

Check the senders identity (is it really from the sender (is it really signed by the Private Key))
The message is unaltered

In general, no.

First, with an arbitrary public key scheme, the public and private keys might have quite different formats, and there might be no such thing like "encryption with a private key".

For example, with (generic) ElGamal, the public key is a member of the group, the private key is a natural number used as exponent.

With RSA, the public and private keys both consist of the same modulus, and additionally a public or private exponent. (The public exponent is usually something small like $3$ or $2^{16}+1$, while the private exponent is of the same order as the modulus.) The core of an encryption or decryption operation is a modular exponentiation with the (public or private) exponent, and yes, this part is easily swapped around, so you can use a private exponent for something which resembles encryption (and you then can use the decryption operation with the public key to undo it). And as is known, the core of the RSA signature operation is just this exponentiation with the private exponent, while verification uses the exponentiation with the public exponent.

Note that this is not a secure use of encryption, i.e. does not provide confidentiality. Does it provide integrity and authentication?

Real live RSA is not only the core exponentiation operation, but additionally a padding operation, to destroy homomorphic properties. There are several padding schemes, both randomized and deterministic, but these padding schemes are different for signature and encryption, for a reason.

Note also that usually public-key encryption is used in a hybrid scheme: encrypt a random symmetric key using the public key algorithm, then encrypt the actual message using the symmetric key. The resulting message thus will have this format:

[ encrypted key ][ encrypted message ]

The encrypted key has (for RSA) a size same as the modulus (which is the same as a signature), the message itself will have about the size of the plaintext message (maybe also including some padding, and hopefully a MAC). This means you will not save anything compared to the standard signature scheme.

What you actually need is a signature with message recovery, i.e. a signature from which (the unknown part of) the signed message can be extracted.
But this only works (or saves space) for a message which is small enough to fit in the signature (and often a bit smaller due to overhead), so for your 1 KB message you would need an RSA key of similar size. I suppose these schemes are only useful for small messages, like in implicit certificates, where the message is the public key to be certified.


Does this ECIES scheme make MAC redundant? I've implemented ECIES (see the below pseudo-Python).

r = urandom(32)
p_r = x25519(r, BASE_POINT)
shared_secret = x25519(r, x25519_public)
iv = urandom(12)
key = sha256(p_r + x25519_public + shared_secret +
iv)
plaintext_sig = ed25519_sign(eddsa_secret, plaintext)
ciphertext, tag = chacha20_poly1305_encrypt(key, iv, plaintext) # as per RFC
output(p_r, iv, plaintext_sig, ciphertext, tag)

As you can see, the plaintext is signed to provide authentication.
Does this signature make the Poly1305 MAC redundant?

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

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


Negilible Function $\frac{1}{n!}$ Is $\frac{1}{n!}$ a negligible function where $n$ is a security parameter?

Application: I have a vector of n>100 elements. I permute it and give it to an adversary. The adversary can break it if it can find the original oder of vector. Its probability to succeed is: $\frac{1}{n!}$. Thus, I need to know whether this probability is negligible.

Hint: you can notice that $n! > 2^n$ (except for very small $n$).


what is number of invertible matrix m*m on$ z_n$?

  please help me what is number of invertible matrix $m*m$ on Group $\mathbb{z}_n$ ?, assuming we know this number in $\mathbb{Z}_p \quad$ (p is prime) is   $(p^{n}-1)(p^{n}-p) \cdots (p^n-p^{n-1})$

Assume you know the number of invertible $m \times m$ matrices over $\mathbb{Z}_{p^k}$ for $p$ prime. Call this number $N(p^k)$.

By the Chinese Remainder Theorem, $N(\prod_{i=1}^l p_i^{k_i}) = \prod_{i=1}^l N(p_i^{k_i})$ because a matrix is invertible iff every component in its CRT decomposition is invertible. For $m = 1$, $N$ is just the $\phi$ function.

Finding $N(p^k)$ is another matter.


ECIES: ECDSA with Kmac and without MAC I have couple of questions about ECIES. I understand how ECIES work and what I must do if I want to have ECIES with ECDSA for authentication (I understand that for full authentication I have to have PKI, but for simplicity in these examples I will not use PKI). I can use sign-encrypt-sign (as described here ECIES with ECDSA):

ECIES(Bob's public key, M || ECDSA(Alice's static private key, M))

And in this case I have structure of message for sending:

[Alice's ephemeral public key, Alice's static public key, ciphertext, Mac's tag]

I understand that this is secure, but for example Alice do:

fetch Bob's static public key
generate ephemeral key pair
SK = ECDH(Bob's static public key, Alice's ephemeral private key)
Kenc || Kmac = KDF(SK)
Ciphertext = Encrypt(Message, Kenc)
ECDSA's tag = ECDSA(Ciphertext, Alice static private key)
HMAC's tag = MAC(Alice's static public key || Ciphertext || ECDSA's tag, Kmac)

Alice make ECDSA's tag first and after that make MAC's tag based on Alice's static public key, Ciphertext, and ECDSA's tag. Alice have structure of message:

|Alice's ephemeral public key, Alice's static public key, Ciphertext, ECDSA's tag, MAC's tag|

I think this is secure as sign-encrypt-sign, because ECDSA's tag is signed by Kmac and Eve can not just take this message, throw away Alice's ECDSA tag, sign the ciphertext with Eve's own key because after that she need to make MAC's tag and she can not, because she do not know Kmac.

Do I correct understand that this is secure as sign-encrypt-sign?

If this correct, I am not sure that MAC's tag is necessary in this scheme. Alice would do:

fetch Bob's public key
generate ephemeral key pair
SK = ECDH(Bob's public key, Alice's ephemeral private key)
Kenc || Kmac = KDF(SK)
Ciphertext = Encrypt(Message, Kenc)
ECDSA's tag = ECDSA(Alice's public key || Ciphertext || Kmac, Alice's static private key)

And Alice have structure of message for sending:

|Alice's ephemeral public key, Alice's staic public key, C, ECDSA's tag|

I think Bob can use ECDSA's tag for verifying that message was not changed and that this message was sent by Alice. Eve can not compromise the message because she have to know Kmac which is used to make correct ECDSA's tag, is not it?

Or, for example, can I use last scheme only for handshake message and after that encrypt next messages by using symmetric cipher and MAC?

There are issues in the question, some serious. In reading order:

ECIES(Bob's public key, M || ECDSA(Alice's static private key, M)) is sign-then-encrypt, which is perfectly fine. But count the signatures, there's only one (ECIES does not sign). Therefore this is not "sign-encrypt-sign" as described elsewhere.
If we wanted to make sign-then-encrypt-then-sign, just replace the resulting ECIES result X by X || ECDSA(Alice's static private key, X). But take care that the final signature leaks who the signer is, when sign-then-encrypt keeps it confidential to all but the holder of the decryption private key.
The "message for sending" is said to be [Alice's ephemeral public key, Alice's static public key, ciphertext, Mac's tag]. That's not matching the form of an ECIES cryptogram per SEC 1 Ver. 2.0, 5.1.3 Action 9, where Alice's static public key is not part of the output. Strictly stick to ECIES, or use another name. The ECIES result is [Alice's ephemeral public key || Ciphertext || Mac's tag]. If Alice's identity or public key or certificate is needed, it can be part of the message itself.
What's hashed in Kenc || Kmac = KDF(SK) should be the (bytetring representation of the) $x$ coordinate of SK (per 5.1.3 Action 4), without the $y$ coordinate or parity bit. I would note Kenc || Kmac = KDF(SKx) to make the distinction explicit.
In Ciphertext = Encrypt(Message, Kenc) it is not stated what Message is. If that's M, then M is not signed. That Message must be M || ECDSA(Alice's static private key, M) in order to match 1. It is critical that the ECDSA signature is encrypted, else confidentiality of the message is largely jeopardized (it becomes trivial to check a guess, e.g. of a coin toss, name, card number..)
ECDSA's tag = ECDSA(Ciphertext, Alice static private key) comes as a surprise at this point, since Ciphertext is currently ECIES's internal symmetric ciphertext (denoted $EM$ in 5.1.3 Action 7), and not accessible externally from the ECIES black box. That makes reuse of proper ECIES code hairy: it's result must be parsed to extract the Ciphertext portion (as an aside, the question's notation is inconsistent on order of parameters, and use of possessive for asymmetric keys).
HMAC's tag = MAC(Alice's static public key || Ciphertext || ECDSA's tag, Kmac) deviates from ECIES (5.1.3 Action 8). It should be replaced by HMAC's tag = MAC(Ciphertext, Kmac) (or HMAC's tag = MAC(Ciphertext || Sharedinfo2, Kmac) where Sharedinfo2 could be some externally agreed-upon bytestring; that could be Alice's static public key, but I do not see the point).
The order is wrong in "Alice make ECDSA's tag first and after that make MAC's tag based on Alice's static public key, Ciphertext, and ECDSA's tag". For sign-then-encrypt that should be: Alice

makes ECDSA's signature/tag of M (this is typically first, but is independent of the next step and thus order is immaterial);
draws an ephemeral asymmetric key pair, multiplies Bob's public key by the ephemeral private key and forgets the later, extracts the $x$ coordinate of the result, derives from that the symmetric encryption and MAC keys used in the next two steps;
then symmetrically enciphers the concatenation of M and that signature/tag (with said concatenation denoted Message in the question), yielding ECIES's internal symmetric ciphertext (denoted Ciphertext in the question and $EM$ in 5.1.3 Action 7);
then makes MAC's tag based on Ciphertext, and optionally Sharedinfo2;
then concatenates the ephemeral asymmetric public key, Ciphertext, and MAC (not the optional Sharedinfo2) into the ECIES result.

|Alice's ephemeral public key, Alice's static public key, Ciphertext, ECDSA's tag, MAC's tag| is wrong if we are making ECIES, as explained in 2. That should be [Alice's ephemeral public key || Ciphertext || HMAC's tag], per 5.1.3 Action 9 (with the necessary conversion from public key to bytestring implicit), yielding the output of ECIES, which is ECIES(Bob's public key, M || ECDSA(Alice's static private key, M)) of 1.
I fail to parse "this is secure as sign-encrypt-sign". Leaving aside "secure as", it does not hold. With the changes indicated, it is made sign-then-encrypt, which is secure. Without the change, this is encrypt-then-sign-the-symmetric-part-of-the-ciphertext-and-include-that-in-the-MACed-data, this is not ECIES, and while I do not immediately see any attack, that's not a valid indication of security.
"I am not sure that MAC's tag is necessary in this scheme": the MAC is necessary at least for the encryption to be what's named ECIES, and to benefit of its security argument. It also serves as a protection against poor implementations on the receiving side.
In ECDSA's tag = ECDSA(Alice's public key || Ciphertext || Kmac, Alice's static private key), again I do not see why Alice's public key is part of what's signed; and Ciphertext is an internal variable of ECIES, which is dubious.
A reading of the question is that Alice reuses the same private key for ECDSA signature and ECIES decryption, which conceivably could have security implication. Formally, it makes ECIES's security argument invalid, and is explicitly against the ECDSA specification in FIPS 186-4:

  ECDSA keys shall not be used for any other purpose

Summary: The alternative proposed essentially replaces ECIES's MAC with an ECDSA signature (with ECIES's MAC key entering the data signed), and makes a number of other variations of the standard ECIES (at least, including the public key, and hashing the whole ephemeral public key rather than its $x$ coordinate). That's functionally encrypt-then-sign, with something that is not exactly ECIES and does not benefit from its security proof (though I see no attack). Beware however than any encrypt-then-sign reveals the identity of the signer, when the question started with the equation of sign-then-encrypt with ECIES, which demonstrably keeps the identity of the signer confidential until decryption. The question states that it performs sign-encrypt-sign, when it appears that it does not (unless Message is assumed to be M || ECDSA(Alice's static private key, M) ). The question does not state use of separate key pairs for signature and encryption, as required by standards and the security argument of ECDSA and ECIES.

Recommendations:

First decide if functionally the need is to have the signer's identity apparent to anyone by examination of the final cryptogram, or revealed only to the holder of the deciphering private key. For asymmetric/hybrid encryption and signature:

if the signer's identity is to be kept secret, or if in doubt, sign-then-encrypt;
if the signer's identity is to be apparent, encrypt-then-sign (sign-then-encrypt-then-sign also works here, but is not necessary for security when the next two recommendations are applied; it is however sometime justified, for example if cryptograms normally carrying the signer's ID must be transformable into anonymous ones by merely stripping the external signature, but should remain signed and non-repudiable after decryption).

In the above, encrypt should be precisely ECIES, including its ephemeral key generation, symmetric encryption, MAC, and concatenation to yield the result.
In the above, when using ECDSA, sign should be computing the ECDSA signature (including at least one hash step of the whole input) then adding the signature to the input (that can be either by appending or pretending it, as long as it can be unambiguously extracted on verification without risk of triggering implementation bugs).
If the identity, public key, or certificate of the sender needs to be included, add it immediately after or immediately before performing one signing step (or both); that can be either by appending or pretending the information, as long as it can be unambiguously extracted without risk of triggering implementation bugs.
When possible: one purpose, one key.

Nothing in this answer should be construed as an endorsement of anything by anyone.


Partial encryption of a file? I want to partially encrypt a large block of data using AES. Meaning: given plaintext[0:1100], I would like to encrypt plaintext[0:1023]. The plaintext is generally machine code, but might have snippets of text.

Does this expose what I encrypted to any realistic challenges in the context of my application (for example: copy protection)?

No, it doesn't have to expose information. Of course, any data in the last part of the file can be used to deduct information about the encrypted plaintext. Furthermore, it seems you want to perform in-place encryption. That's fine, but ciphers generally require an IV to make sure that the ciphertext is random even on identical plaintext. Using an IV generally means expanding the ciphertext size compared to the plaintext size.

There is one mode of operation that is perfect for encryption like this: CTR or counter mode (it may have even different names in other libraries). Here a counter is encrypted, and the resulting block is part of the key stream. You can simply XOR that key stream with the plaintext at the same offset to create the ciphertext. There is one big "but" (yo' mamma): CTR mode is completely unsafe if the counter is ever repeated, and the initial counter value is the IV. So you do need to store the IV somewhere where it can be related to the ciphertext. Possibilities are storage at the beginning or end of the file or in the meta-data of the (modern) file system.

It is also possible to calculate the IV, e.g. by performing a SHA-256 of the full path of the file name, and then taking the leftmost 128 bits. But note that any movement of the file will lead to corrupted plaintext (and possibly no way to decrypt if the path cannot be reconstructed).

If copy protection is used then leaving part of the file encrypted may indeed destroy the copy protection, if the bytes are taken into account e.g. for signature generation, using a hash over the encrypted data. However, without more info about copy protection (which comes in many forms) then we cannot tell for sure. Of course if you can fully restore the file before copyright protection takes place I presume you are secure.


Can substrings of a long string be efficiently authenticated? Suppose one has a (strong) shared secret key and wishes to authenticate a very long string in a way that will allow the verifier to verify  small substrings without reading much of the stored data and without much storage overhead.

The trivial way to do this is to have a nonce, divide the string into chunks, MAC each chunk along with its position and the nonce, and then MAC the string length along with a special indicator.

Is there any better way to do that?

Here's a better solution, using a Merkle tree.

Suppose the string $S$ is $n$ letters long.  Build a binary tree with $n$ leaves, with each leaf corresponding to one letter in the string.  Then, each node corresponds to a substring: the $i$th leaf corresponds to the $i$th letter in the string, and an internal node $x$ corresponds to the substring obtained by concatenating all of the leaves that are descendants of $x$.  Now, you can store at each node of the tree the MAC of the substring it corresponds to.  This is all done in a precomputation.

Once you've precomputed the binary tree, you can authenticate any substring $T$ of $S$ as follows: $T$ can be written as the concatenation of the strings at $O(\lg n)$ nodes in the tree.  Therefore, to authenticate $T$, you send the MACs at those nodes.  In this way, the authenticator is $O(\lg n)$ in length.  This is better than your trivial solution, in terms of the length of the authenticator (as your trivial solution requires an authenticator that is $O(|T|)$ in length).  In your storage setting, the length of the authenticator corresponds to the amount of data that must be read from storage to authenticate a particular substring $T$.

If your goal is solely to optimize the length of the authenticator, You might be able to build an even shorter authenticator using set accumulators, though the performance cost would likely be much higher.  Given a string $S$, you construct a set of pairs $\langle i, S_i \rangle$, then use a set accumulator construction to sign that set; now it is possible to derive a signature on any subset, such as one corresponding to a substring of consecutive letters from $S$.

Another alternative might be to use hash chaining or MAC chaining.  For MAC chaining, you could do the following: let $Y_i = MAC(Y_{i-1} || S_i)$, for each $i$.  You can store all of the $Y_i$'s alongside the string.  Then, to authenticate a substring $S_{i..j}$ of $S$, you read $Y_{i-1}$, do $j-i$ MAC operations to run forward along the substring, and check that the result matches $Y_j$.  Of course, as an engineering optimization, it would be possible to store the $Y_i$ values for only every $k$th index $i$, for some $k$.  I don't know whether this will be better in any sense than the other schemes.

You might also be interested in the following research papers:

Homomorphic signature schemes.  Robert Johnson, David Molnar, Dawn Song, and David Wagner.  RSA 2002, Cryptographer's Track.  See particularly Section 4, redactable signatures.
Sanitizable Signatures.  Giuseppe Ateniese, Daniel H. Chou, Breno de Medeiros, and Gene Tsudik.  ESORICS 2005.

Given that you are focusing on stored data, you might also like to look at the line of research on memory integrity checkers, e.g.,

Checking the correctness of memories.  Manuel Blum, William S. Evans, Peter Gemmell, Sampath Kannan, and Moni Naor.  Algorithmica, 12(2/3):225–244, 1994.
The Complexity of Online Memory Checking.  Moni Naor, Guy N. Rothblum.  FOCS 2005.


XMSS - creation of authentication path The reference uses treeHash algorithm everytime a signature is generated, thus generating authentication path AND the root, which is not necessary, as the root has only to be generated once. Generating root with every new signature is not efficient, but are there more efficient ways to generate the authentication path without recomputing the xmss root?
My first approach is to save all the xmss leaves during root computation, then create authentication path out of them if needed, but this requires a lot of memory for bigger tree heights.

are there more efficient ways to generate the authentication path without recomputing the xmss root?

Yes (and without using large amounts of memory to store the entire tree).
These are Merkle tree walking algorithms; these are algorithms which output the 'next' authentication path for a Merkle tree - they store some number of internal nodes, and recompute some small number of leaf nodes while generating an authentication path.
The best known (and best described, if not the simplest) would be the BDS algorithm, which generates the next authentication path in $O(h)$ time and storing $O(h)$ intermediate nodes (where $h$ is the height of the tree).
Another (simpler approach) would be the Fractal algorithm (which isn't well described in the paper); this uses more internal storage, but it requires fewer numbers of computations per authentication path generated (and hence may be a better trade-off, depending on which you are trying to minimize)
These are not the only two; google can point you to others...


MLWE (and RLWE) to LWE reductions proof In  crypto papers, cryptanalysis of MLWE/RLWE/etc. is often reduced to LWE. Why can we do this? Is there strict proof of such reductions?

There is no known reduction from LWE to MLWE (or to RLWE). That is, it could be that both MLWE and RLWE are broken, yet LWE is secure.
However, this seems highly unlikely. To support the security of LWE, we have reductions showing that breaking the average-case hardness of LWE requires breaking the worst-case hardness of some lattice problems - which would be (in the language of Brakerski et al.) "earth-shattering". Now, similar reductions hold for both MLWE and RLWE (see also this): both can be based on the worst-case hardness of lattice problems. The main difference is that RLWE requires worst-case hardness over ideal lattices, and MWLE requires worst-case hardness over module lattices.
Some notes about the above:

everything strongly depends on the parameters. LWE-style assumptions are heavily parametrized, and saying "reduction" does not say much if we do not make explicit the parameters for which the reduction works. The reductions I mention above are for the most standard choices of parameters (e.g. polynomial modulus).
Worst-case hardness over module lattices sounds more plausible than worst-case hardness over ideal lattices, for a variety of reasons. Yet, up to some important loss in the reduction, we actually do have reductions of RLWE to MLWE. This further illustrate while being precise with the parameter choices is important when discussing this topic.
The main reason why cryptographers prefer using MLWE or RLWE over LWE is because they lead to much more efficient schemes. However, RLWE is parametrized by some polynomial, and requires hardness assumptions tailored to this very specific polynomial. This is a bit unsatisfying, because we don't really understand well the impact of the choice of polynomial on security. However, recently, a new problem was introduced, middle-product LWE. The latter gives us the best of both world: it allows essentially the same efficiency gains as standard RLWE or MLWE in many applications (see the paper, but also its follow-ups), yet it is as secure as RLWE with respect to any polynomial - hence to break it, you would need to break RLWE for every possible choice of the polynomial. This gives a very satisfying ground for the security of this assumption.