Security of a given hash function We have a message denoted $M$. Let us suppose that we have a collision-resistant hash function $h_0$ with output length $n$. We then consider two other independent (different) hash functions $h_1$ and $h_2$, with output length $n/2$. For instance, we can choose SHA-256 for $h_0$, and SHA-256 with a truncated output (128 bits) for $h_1$ and $h_2$. Note that $h_1$ and $h_2$ are obtained by domain separation, i.e. $h_1=\operatorname{lsb}_{128}(\mathrm{SHA256}(M\| 1))$ and $h_2=\operatorname{lsb}_{128}(\mathrm{SHA256}(M\|2))$.

We now consider the hash function $h_3$:
$$h_3(M)=h_1(h_0(M)) \| h_2(h_0(M))$$

I have read that the concatenation of two independent hash functions appied on the same message does not increase the security when the message is long. What about the above $h_3$ function, when compared to $h_0$? In terms of collision-resistance and second-preimage resistance.

$h_3$ is at most as collision and 2nd-preimage resistant as $h_0$.

Proof:
Suppose we have a collision for $h_0$, that is, we know $x\neq y$ with $h_0(x)=h_0(y)=h$. Now observe that $h_3(x)=h_3(y)$ as follows: $$h_3(x)=h_1(h_0(x))\parallel h_2(h_0(x))=h_1(h)\parallel h_2(h)=h_1(h_0(y))\parallel h_2(h_0(y))=h_3(y)$$

Now that we have established that $h_3$ cannot be more secure than $h_0$, let's look at the "lower bound". Let $c_i$ be the boolean variable that indicates that a collision on hash function $h_i$ is known. Then the following holds:
$$c_3\rightarrow c_0\oplus(c_1\land c_2)$$
(with $\oplus$ denoting XOR)

That is, $h_3$ is at least as secure as $h_0$ or ($h_1$ and $h_2$). This assumes there are no subtle interactions between the hash functions which would facilitate a structure-lead collision search.

Suppose we have a collision on $h_3$, that is we know $x\neq y$ such that $h_3(x)=h_3(y)$. $h_3(x)=h_3(y)$ implies that $h_1(h_0(x))=h_1(h_0(y))$ and $h_2(h_0(x))=h_2(h_0(y))$ (by simple decomposition) and so we would have found a collision on $h_1$ with the values $h_0(x)$ and $h_0(y)$ and a collision on $h_2$ with the same values. This assumes that $h_0(x)\neq h_0(y)$ is allowed to be called a proper collision. If this is not the case we would have found a collision on $h_0$ instead. So we have $c_0\oplus (c_1\land c_2)$ being true, deduced from $c_3$ being true.

Actually the right-side of the found collision is worth "more" than a normal collision on a hash function. Because we have found a collision on both hash functions, which is equivalent to finding a collision on $h'(M)=h_1(M)\parallel h_2(M)$ which with the constraints given in the question has $n/2$ bit security.

So what does all of the above mean?

If you can break $h_0$ you can break $h_3$.
If you can break $h_3$ you can either break $h'$ or $h_0$.
If either $h_1$ or $h_2$ is a permutation, then breaking $h_3$ is exactly as hard as breaking $h_0$.
If you can break $h'$ you can trivially break $h_1$ and $h_2$.
Two "normal" collisions on $h_1,h_2$ are very likely not sufficient to break $h'$.
A collision on $h'$ very likely does not yield a collision on $h_3$ (because you would still need to find a pre-image with respect to $h_0$).
If $h_0,h_1,h_2$ lack structural weaknesses, $2^{n/2}$ operations are required to break $h_3$ (which is the expected value).

Reading hint for the uninitiated: "if you can break x then you can [logical formula involving breaks of $y_i$]" needs to be negated on both sides and then the sides need to be swapped for a security statement. That is "if [negated logical formula] is secure, so is x".


Divide data into parts and restore from them I'm not much familiar with cryptography, so please guide me in the right direction on the following question:

Let's say I have some data (array of bytes) $D$. I want to convert it into $N$ pieces (arrays of bytes) in such a way that

if someone knows at least $m$ of those pieces ($m \le N$) then it should possible to restore the original data, i.e. $D = f(p_1,...p_m)$. It's important that any $m$ pieces should suffice to restore $D$, not necessarily $m$ consecutive pieces
if someone knows $k \lt m$ pieces then there's no way (computationally difficult) to restore $D$ or any part of $D$

Example: if $N=3$ and $m=2$, it should be possible to restore $D$ from $(p_1, p_2)$ or $(p_2,p_3)$ or $(p_1,p_3)$ but not from $p_1$ or $p_2$ or $p_3$ alone.

The problem you are describing is called Secret Sharing
And the common algorithm to solve the m of N is https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing

It is not only computationally difficult, it is information theoretic impossible to discover the secret without the required number of shares.


PBKDF2 with the same salt for all IDs I have a unique identifiers that I would like to keep secure and provide information about it through tokens. These tokens should be verifiable after using the same algorithm on other end system with presented ID and comparing these values.

I am thinking to use PBKDF2 as a one-way function to get such tokens from IDs. But to be verifiable  I should use the same SALT everywhere.

Are there any security issues related to use the same SALT in PBKDF2 for all IDs?

Are there any security issues related to use the same SALT in PBKDF2 for all IDs?

Yes, you can build a rainbow table or brute force the ID's.

An attacker could build up a table with tokens. Once the table exists the attacker can try all possible ID's until one of them matches. That way the function is reversible and your requirement to keep the ID secure has faltered.

Of course if the ID has enough entropy then the brute force attack will be impossible. But in that case you would not need the PBKDF2 function in the first place.

I don't see why you could not store a salt with a specific token by the way. Generally tokens are short lived.

Disclaimer: this is just a direct answer to the question, not a protocol analysis.


Safely store data before moving to air-gapped machine This is related to an earlier question, Is it possible to use an algorithm to generate an OTP?

I have two machines: A, and B.  A is connected to the internet and files are uploaded regularly.  B is air-gapped.

When files are uploaded to A, I want to encrypt and store them in the most secure way possible.  They will then be transferred via USB to machine B, where they can be decrypted and read.  What's the most secure method of going about this?

My understanding is that this is a pretty standard encryption problem.  However, as far as I can see, the nonce for each message is transferred along with the message itself.  I would rather some method where the nonce could be generated by an algorithm that both A and B knew, with a seed that was secret shared between them.  Is this possible?

However, as far as I can see, the nonce for each message is transferred along with the message itself.

Yes, this is typically what happens nowadays when encrypting something using symmetric encryption.

Notice this is not necessarily the case if you're using asymmetric cryptography, since then the randomness used (which can be considered to be a "nonce") is usually encrypted along the message.

Probably the easiest way: asymmetric crypto

If you are only transferring data from one machine A to the other machine B and do not necessarily need to decrypt the data again on the first machine A, I would strongly recommend you to check out public-key encryption:

You could have a strong private key on your machine B and let machine A know the public key
Machine A could then encrypt everything you need to transmit to machine B using the public key of machine B, without leaking the secret key or anything that might allow someone to decrypt your data on machine A.
Machine B could then use its secret key to decrypt the data.

This is especially true if machine A is not air-gaped, while machine B is: you could consider machine A to be already compromised and as such all the keys, IV or passwords you might have on machine A might leak, whereas using public-key encryption, your data could not be decrypted by only looking at the secrets that went through machine A (even if the said data could be arguably already leaked while unencrypted).

(This can even work if you want machine A to be able to decrypt the data again, by encrypting the data for both the public key of machine A and B.)

About the air-gap

Notice that the air-gap in the end does not necessarily change things, as it boils down to two different scenarii:

Machine A is compromised and all the secret key, IV, nonces, and (most dramatically) messages that go through machine A can then be considered compromised
Machine A is not compromised and then we are fine

But maybe the air-gaped machine is compromised as well by a physical attacker, who knows? So there are more scenarii...
And in the end we have the same kind of scenarii than whenever we have two machines and we want to transmit data between them.

There is nothing in crypto that can help you protect your data from a compromised machine if the plaintext is on the compromised machine...

Yet, it is not because of this dichotomy (either compromised or not) that you don't need encryption.
Indeed, encrypting your data is still useful to protect the data when:

it's at rest, so that even if somebody access your machines and copy your data, they won't be able to read the data.
it's in transit, so that even if somebody intercepts your data, it will be encrypted and undecipherable for the attacker.

Even more so since it might be possible to recover erased data from a USB stick, or whatever transportation method you are using for your data...

And if the attach is not permanent, but occurs for example only when you're away ("evil maid attack"), then having encrypted data makes also sense.

Now, if you really want to do what you're discussing

  I would rather some method where the nonce could be generated by an
  algorithm that both A and B knew, with a seed that was secret shared
  between them. Is this possible?

Now, if you really want symmetric encryption, this is still possible and readily supported by Openssl, actually! (But not by other common tools such as GnuPG.)
If we take a look at the documentation of Openssl's enc feature, we can see the following:

  -K key

  The actual key to use: this must be represented as a string comprised only of hex digits. If only the key is specified, the IV
  must additionally specified using the -iv option. When both a key and
  a password are specified, the key given with the -K option will be
  used and the IV generated from the password will be taken. It does not
  make much sense to specify both key and password.

  -iv IV

  The actual IV to use: this must be represented as a string comprised only of hex digits. When only the key is specified using the
  -K option, the IV must explicitly be defined. When a password is being specified using one of the other options, the IV is generated from
  this password.

  -pass arg

  The password source. For more information about the format of arg see "Pass Phrase Options" in openssl(1).

So you could typically have a key specified using the -K argument, and derive the IV from a shared "password" file using the -pass file:pathname argument.
Notice you can choose how to derive the password, I would recommend you going with -pbkdf2 and setting a certain number of iterations:

  -iter count

  Use a given number of iterations on the password in deriving the encryption key. High values increase the time required to brute-force
  the resulting file. This option enables the use of PBKDF2 algorithm to
  derive the key.

BUT!
There are a couple issue with this method:

this will make it "easy" to reuse an IV, since if you are using the same password twice with the same number of iterations you should get the same IV, right? Well, not exactly, because Openssl got you covered. The password derivation algorithm is relying on a "salt" that gets passed on the first line of the encrypted file, just like you would usually pass the IV. I guess you could complain this is basically the same as passing the IV, but it is not, since the salt is used with a "secret" password to derive the IV.
this makes it easy to use too short keys!! This is really a problem, because if you are using a key that is not of the right size, Openssl will pad the key with zeros to achieve the right length!
using Openssl manually on the command line is a bit painful.
it is easy to use a "bad" parameters.
and finally, and most annoyingly: this does not allow the use of authentication encryption! This is justified in the documentation as follow:

  The AEAD modes currently in common use also suffer from catastrophic failure of confidentiality and/or integrity upon reuse of key/iv/nonce, and since openssl enc places the entire burden of key/iv/nonce management upon the user, the risk of exposing AEAD modes is too great to allow.

And this is true: key, iv and nonce management are considered difficult, and we do not recommend you to do it yourself! You can if you really want to, but it is typically not something we will tell you is "the most secure method" to do any kind of cryptography.

Notice that my last point is a problem: the lack of authentication means somebody could change your encrypted data without being detected, but you could solve it by performing a MAC after encryption, in the "Encrypt-then-MAC" style. This is possible using openssl mac or openssl dgst depending on your version.  Or you might solve it by using instead LibreSSL openssl that's including AHEAD mode in its enc command... You just need to pick an authenticated cipher.

TL;DR: don't do it.

However as you can see: the more we are digging that hole, the more we need to dig to try and have something "secure"... As such, this is typically not something you want to do "manually".

We usually recommend using symmetric or asymmetric encryption (using typically GnuPG), and not caring about managing the IV, and the "gory details" such as the need for authentication, etc. (Notice GPG --sign will use public-key signatures, so you would need to generate a key and share the public key with the other machine even if using the --symmetric mode.)

Also, if you are now considering "rolling your own" crypto, to solve your problems, you might as well try and take a look at what other have already done when facing a bit the same kind of problem as you do, there are many tools out there.
One of the "simplest" tool is probably "Enchive" which is using an interesting shared key generation algorithm based on Diffie-Hellman, but is still quite minimalist.

I also recommend you following the development of "Age" that has been recently designed and created by very good cryptographers, and should allow you to have high security, with good usability to do you want to do, without having to care too much about IVs, etc.

Notice how really nobody, even when "rolling their own" is letting users manage their nonces/IV, this is done for reasons... And I don't recommend you doing it neither.


Is it secure to encrypt a 1 GB data file with AES-CTR by ECIES? I have a file system with share resources over the network (like a shared FTP)

Is it possible to use the client's ECC public key to encrypt the AES key, and then use the AES in CRT mode for the file encryption?  File size can be 1GB to 1TB.

I do not believe there would be any issues, as long as:

The problem you are attempting to solve is that you want to encrypt a file so that the client can decrypt it, but no one else can
The client has a public/private key pair
The encryptor has the client's public key and you somehow know that it's the client's public key
The encryptor has access to randomness (as the security of ECIES depends on it)
You add some integrity transform (along with the AES-CTR), to make sure that no one can modify the encrypted message without being detected.  If you need a suggestion about which integrity transform to use, perhaps HMAC-SHA256 would work; alternatively, you could replace AES-CTR with (say) AES-GCM.

You appear to be concerned about the size of the file being encrypted; the public key portions could care less about how long the message is (it does the same thing regardless), and the AES-CTR portion can easily handle a terabyte without an issue.

You may want to consider breaking the file up into smaller pieces and encrypt and send each piece separately, but that is for purely practical reasons (e.g. if one of the smaller pieces get corrupted, the receiver can ask for that specific piece to be resent, and not the entire 1Tb file); however the cryptographical security would not depend on that.


Your computations are correct.

For each valid $x$ coordinate there are 2 valid $y$ coordinate, $+y$ and $-y$, as you correctly said.

But note that numbers in a field $\mathbb{F}_p$ are usually written $\mod p$, which means they lie in the interval $[0,p-1]$, so without the "-" sign.

So, when you write the $y$ coordinate of your $-10G$, which you call $10*G (Inverse)$ but obviously $10*(-G)=-10*G$ so it's equivalent, you write it as:
-62070622898698443831883535403436258712770888294397026493185421712108624767191
but this can be written as a field element as p - 62070622898698443831883535403436258712770888294397026493185421712108624767191 with $p$ being the prime defining the field.
This results into 53721466338617751591687449605251649140499096371243537546272162295800209904472 .

Plugging the coordinates into the curve's equation is the correct way to verify that points are on the curve, and yours are on the curve.

For example: your $2G-10G$ and $8G$ share the same $x$ coordinate, in fact, $2G-10G=-8G$ so they are opposite points. You can get the value of the $y$ if you subtract one's value from $p$. E.g.

p - 41749993296225487051377864631615517161996906063147759678534462689479575333124
= 74042095941090708372193120377072390691273078602492804360923121318429259338539


Generic group model: use of polynomials in the proof of the master theorem I've been looking at the paper of Boneh, Boyen, Goh Hierarchical Identity Based Encryption with Constant Size Ciphertext
which contains a general theorem (Theorem A.2) about the advantage of an attacker in the generic group model. It seems to be based on the idea that in the generic bilinear group model, we can only compute things that are linear combinations of the given inputs as well as multiply linear polynomials once when computing a pairing. What they argue is that if the randomly sampled inputs are $x_1,\ldots,x_n$ and we have computed two (at most quadratic) polynomials $L_i(x_1,\ldots,x_n)$ and $L_j(x_1,\ldots,x_n)$, then the equality check for

$$L_i(x_1,\ldots,x_n)=L_j(x_1,\ldots,x_n)$$

can be replaced by an equality check

$$L_i(X_1,\ldots,X_n)=L_j(X_1,\ldots,X_n),$$

i.e. we check for equality as polynomials, not as evaluated polynomials.

The general idea of the proof is then that we may afterwards check what the probability is that the adversary could have seen a difference between these two cases. This seems to be based on the idea that for random polynomials, we have an upper bound for the probability that a randomly sampled point is a root.

My issue with this proof is that since the polynomials that show up in the computation depend on information the adversary has gained from previous oracle queries, the list of polynomials $L_1,\ldots,L_q$ has been adaptively constructed. Therefore, the list is not independent of the sampled values $x_1,\ldots,x_n$. I don't see how this is taken into account in the proof? Anyone care to explain this in more detail, since all later papers with similar theorems seem to sidestep this issue too.

The problem can be simplified to the following problem, since the standard argument doesn't really take into account that you can't generate all the polynomials of the given maximum degree :

Assume that we have sampled a random point $\vec{x}\in \mathbb{F}_p^n$. We let an adversary adaptively choose polynomials of degree at most $d$ and after each choice we tell whether $\vec{x}$ is a root of the chosen polynomial. Then after $q$ queries, the probability that the attacker has found a polynomial for which $\vec{x}$ is a root is bounded above by
$$\frac{qd}{p}.$$

What we know is that the probability that a random element in $\mathbb{F}_p^n$ is a root of some polynomial of degree $d$ is bounded above by $d/p$. Therefore, the attacker is essentially choosing subsets of size at most $d/p\cdot p^n$, since we only care about roots, not the actual polynomials. Thus, the problem is equivalent to the following:

Assume that we have chosen a random point $x$ in a set $S$ of size
$p$. We let an an attacker adaptively choose $d$ points at each round
and then tell the attacker whether or not $x$ is among the $d$ points.
Then the probability that after $q$ queries we have chosen a set of points containing $x$ is bounded above by $qd/p$.

We prove by induction that the upper bound is given by $qd/p$. This clearly holds for one query, since on the first attempt we're just picking a set of size $d$ and the probability of $x$ being in this set is $d/p$. Now assume by induction that the winning probability on $q$ queries is $qd/p$. Now with $q+1$ queries, we either win during the first $q$ queries or we don't and win on the $q+1$st. It follows that we get
$$\frac{qd}{p}+\frac{d}{p-dq}\left(1-\frac{qd}{p}\right)=\frac{(q+1)d}{p}$$
It's correct, however, that none of the existing proofs in the literature discuss the point that the adversary chooses polynomials adaptively. All the proofs just say that at the end we have $(s+q)^2$ possible polynomials and the chance of a random element being a root of one is $(s+q)^2d/p$, which is not really a valid argument in this case, although you get the same bound.


How to design a deliberately weak PRNG for experimentation? I'm looking for a PRNG that is deliberately weak, that is, follows a set of rules stochasticly.

For example:
Encounters a set of bits that is a multiple of X, starts exhibiting bias, or starts to oscillate somewhat. etc...

The weaknesses need to both be simple and complex, the experiment would consist of trying to identify those weaknesses to attain some probability P of predicting future output information using various machine learning methods.

I'd suggest starting with the dieharder suite of generators, as that list covers a lot of popular generators with known weaknesses, and the application can emit bitstreams from each generator.

The most famous bad RNG (other than the xkcd comic one) is RANDU.  That's very low-hanging fruit as a warm-up exercise.

Typically these generators produce something like a 32-bit or 64-bit word, and to treat this as a bitstream from a black box you just append all the words.  This implies that the bitstream is likely to show patterns with respect to every 32nd or 64th bit; and a naive test might be confounded by simply emitting 31 bits instead of 32 (this can be perfectly sensible in hardware, but rare in software).

What I don't see in that list (or may simply fail to recognise in their abbreviated names) are LFSR and xorshift generators.  These have an upper limit on the number of zeroes they can emit in a row (commonly 32 or 64) and their output is always a fairly simple bitwise transform of bits seen recently, but at least xorshift can still pass a lot of statistical tests.

Linear congruential generators have high-frequency periodicity in their low-order bits (the least significant bit can only oscillate between 0 and 1, the next bit cycles through four states before repeating, etc.); some generators discard the low order bits so that the least-significant bit might repeat on a period of 65536.  There's a bunch of heavier mathematics I've never bothered to think about which might be interesting to you.

Any of the dieharder tests that fail dieharder's own testing obviously do have a pattern, and that'd be a good place to look.  In that sense I suppose dieharder documents your options better than I ever will.

Of those that pass all statistical tests, most are still considered insecure when you have insight into how the generator might work.  dieharder is not a cryptographic tool.


pgpdump alternative for gnupg 2.x I want to see gpg2 key parameters packets. pgpdump v0.32 doesn't support gpg2 (especially elliptic curve cryptography packets) and "gpg2 --list-packets" doesn't show "secret" key parameters.

Is there any way to see (secret) key parameters (d, q and curve) of elliptic curve crypto algorithms in gpg2 exported secret subkeys?

Note: I read OpenPGP Public-Key algorithm but this is not my answer.

When I use --verbose --list-packets on an export of a secret key it displays all the fields in the secret key (sub)packets. At least it looks like it is complete.

It does not open key encryption, so I have to export the key with a empty passphrase (unfortunatelly there is no export option for that anymore so I had to edit the key).

In this case it uses a named curve, the curve parameters are publically known and not exported.

> gpg.exe --verbose --list-keys
pub   brainpoolP384r1 2017-12-09 [SC]
      971D76C158AFD6D6AC53205327C195C6F0FB0EDA
uid        [ ultimativ ] Bernd Eckenfels (test) <ecki@zusammenkunft.net>
sub   brainpoolP384r1 2017-12-09 [E]

> gpg.exe --export-secret-key > secret.pgp

> gpg.exe" --verbose --list-packets secret.pgp
...
# off=0 ctb=94 tag=5 hlen=2 plen=168
:secret key packet:
        version 4, algo 19, created 1512840291, expires 0
        pkey[0]: 092B240303020801010B brainpoolP384r1 (1.3.36.3.3.2.8.1.1.11)
        pkey[1]: 042B9980A50F01AE91CA7B5A6ABDD350B3FE6BB8E7F44E561FDCB45354BA0D721DA4D9E3DB9B8CD96E248F2099E643E0073649E6D97DB9FCF67B1060F8F36EE0F12F3CEAC68F0D7DAC811DA290693F7620640F87A398901E6D2BDBEA6D4A7251E4
        skey[2]: 40223083F5447B9C109A2F063EAF45FFA7D3DDC48AF71F061B4E95CA475775CF488095D4EDE4109B9539DFD036AE4DB7
        checksum: 1872
        keyid: 27C195C6F0FB0EDA
...
# off=397 ctb=9c tag=7 hlen=2 plen=172
:secret sub key packet:
        version 4, algo 18, created 1512840291, expires 0
        pkey[0]: 092B240303020801010B brainpoolP384r1 (1.3.36.3.3.2.8.1.1.11)
        pkey[1]: 0467F588651ACAB96B80CA052030B3337E8374586C86B3D4386D5569D6C548C0D76662EB112438300B73275FB81809CE6642D3B1878292729B1F3FD1AE2C246AE7064A7B9464446E7A4E0C16B25FD933556371271862C6EEFDFE01087BEEB3CFF9
        pkey[2]: 03010909
        skey[3]: 15FCB0053B11FD8E4E907E9E7ED937F0E226AE0DF4D79D333ED18BF396191628E8A82241BF26B1C1FBD9F5984636A495
        checksum: 19cb
        keyid: 80C1909634D5FC1B

18  ECDH public key algorithm   [RFC6637]
19  ECDSA public key algorithm  [RFC6637]

pkey[0] is the curve OID. Parameters of the curve are public known and not part of the key format.

pkey[1] is the public point (uncompressed format starting with 04 and then two 384bit scalar integers as coordinates).

According to RFC 6637 there is only a single secret algorithm specific parameter for ECDH and ECDSA keys: a MPI scalar. The above example lists them as skey[2] for ECDSA main key. In my case is a 0x017f bit long scalar (48bytes).

BTW: If exported with password protected keys, it looks like:

# off=0 ctb=94 tag=5 hlen=2 plen=214
:secret key packet:
        version 4, algo 19, created 1512840291, expires 0
        pkey[0]: 092B240303020801010B brainpoolP384r1 (1.3.36.3.3.2.8.1.1.11)
        pkey[1]: 042B9980A50F01AE91CA7B5A6ABDD350B3FE6BB8E7F44E561FDCB45354BA0D721DA4D9E3DB9B8CD96E248F2099E643E0073649E6D97DB9FCF67B1060F8F36EE0F12F3CEAC68F0D7DAC811DA290693F7620640F87A398901E6D2BDBEA6D4A7251E4
        iter+salt S2K, algo: 7, SHA1 protection, hash: 2, salt: 70B08AE0E115EFEE
        protect count: 1507328 (167)
        protect IV:  98 be 19 56 65 43 7c 32 0a ff 4f 21 5b eb 47 af
        skey[2]: [v4 protected]
        keyid: 27C195C6F0FB0EDA

The examples have been created with win64 gpg 2.3.2 (libcrypt 1.8.1).

Here is the test key: https://gist.github.com/ecki/8adb287fa64347bfba218a6fd9e21d0f and details.


What is the expected number of different sequences of bits in the collection that contains $2^{800}$ elements? Let $F$ denote a function that returns the first $800$ bits of the input.

Let $G(N)$ denote a function that returns the last $800$ bits of the binary encoding of the given number $N$. For example,

$$\begin{array}{l}
G(0) = 00\underbrace  \ldots _{{\rm{796\;zeroes}}}00,\\
G(1) = 00\underbrace  \ldots _{{\rm{796\;zeroes}}}01,\\
G({2^{800}} - 2) = 11\underbrace  \ldots _{{\rm{796\;ones}}}10,\\
G({2^{800}} - 1) = 11\underbrace  \ldots _{{\rm{796\;ones}}}11
\end{array}$$

etc (we are only interested in the interval $0 \le N \lt {2^{800}}$ ).

Let $P$ denote Keccak permutation function that operates on $1600$-bit blocks.

Choose (arbitrarily or randomly) any 800-bit sequence. Denote it by $S$.

Consider the following collection (set) of bitsequences:

$$\begin{array}{l}
{C} = \{ &F(P(G(0)|| S)),\\&F (P(G(1) || S)),\\&F(P(G(2) || S)),\\&\ldots ,\\&F(P(G({2^{800}} - 2) || S)),\\&F(P(G({2^{800}} - 1) || S))\;\;\}
\end{array}$$

(it contains $2^{800}$ elements, and each element is a $800$-bit sequence).

Let $Y$ denote the number of different (unique) elements in $C$.

Question: what is the expected value of $Y$? And why?

Edit: I have read Expected number of different birthdays, and found the following formula:

$$\begin{array}{l}\\&
D = 2^{1600},\\&
n = 2^{800},\\&
\varphi = (D-1)/D,\\&
Y = D\times (1-\varphi^n)
\end{array}$$

Is this the correct formula for $Y$?

Every input $G(i) \mathbin\| S$ to $P$ is distinct.  If $P$ were a uniform random permutation, the random function $x \mapsto F(P(x))$ would have almost uniform distribution.  So the answer can't be much different from the number of distinct 800-bit strings in an independent uniform random sampling of $2^{800}$ of them, which is a fraction of $$1 - (1 - 1/2^{800})^{2^{800}} \approx 1 - e^{-1}$$ of them by the usual reason.  The fact that $S$ is chosen independently at random is not relevant to this analysis; the same analysis would apply if $S = 0$.


Solving a system of equations using both arithmetic and bitwise operations At first I asked this question on Stackoverflow, where I was advised to ask here. So there is the question:

I have a system of pretty simple equations:

$x + y = A$
$f(x,y) + y = B$

$A, B$ are known. All of the variables are 64-bit positive integers, including $f(x,y)$.

But the problem is that $f(x,y)$ uses bitwise operations:

$$f(x,y) = x \oplus (x \ll 3) \oplus y \oplus (y \gg 14)$$

I tried to solve this by representing arithmetic addition with bitwise opperations and carry-bits. I also tried to represent each bit as a boolean value and then solve a system of boolean equations. I didn't succeed any much. So is there any method of doing this properly?

So is there any method of doing this properly?

Here's the most obvious method:

Iterate through the lower 14 bits of $y$, that is, you'll perform the below steps for each of the 16384 possible settings of the lower bits of $y$
Compute what the lower 14 bits of $x$ are, using $x = A - y$ (because the subtraction is modulo $2^{64}$, we can ignore everything higher than bit 13)
Compute what the next 14 bits of $y$ must be, using $y >> 14 = (B - y) \oplus x \oplus (x << 3) \oplus y$
Compute what the next 14 bits of $x$ are, using $x = A - y$ (only this time, because we know 28 bits of $y$, we can reconstruct 28 bits of $x$)
Compute what the next 28 bits of $y$ must be...
Keep on doing this until we start predicting bits of $y$ above 63; because the right shift shifts in 0's, the prediction must be that they are all 0 (and if it predicts something else, we can reject the original guess of the lower 14 bits of $y$).

This involves iterating through 16384 different possibilities; a tad tedious by hand, but fairly trivial for a computer program...

I threw together a quick C routine to do the above search:

typedef unsigned long long num;
void solve_it(num a, num b) {
unsigned lower_14_y;

for (lower_14_y = 0; lower_14_y < (1<<14); lower_14_y++) {
    num y, x, upper_y = 0;
    int i;

    for (i=1;; i++) {
        y = (upper_y << 14) + lower_14_y;
        /* Lower i*14 bits of y are accurate */
        x = a - y;
        /* Lower i*14 bits of x are accurate */

        if (14*i >= 64) break;  /* Got all the bits */
        upper_y = (b - y) ^ x ^ (x << 3) ^ y;
    }

    if (b != y + (x ^ (x << 3) ^ y ^ (y>>14))) {
        continue;
    }
    printf( "Found solution %llx, %llx\n", x, y );
}
}

On my machine, it takes 80usec to run, and as kelalaka suspected, sometimes there aren't any solutions, and sometimes there are multiple (e.g. for a = 0x6c, b = 0xee, there are 7 solutions)


Why Bulletproofs protocol needs to raise $u$ to power $x$ in Protocol 1? The paper on the Bulletproofs Zero-Knowledge proof protocol states in paragraph 3:

  In Protocol 1 the element $u$ is raised to a verifier chosen power $x$ to ensure that the extracted vectors $a, b$ from Protocol 2 satisfy $\langle a, b\rangle =c$.

I can't make sense of this.

I guess it is because the scalar $u$ is not given in the relation, thus the value $P'$ can be computed incorrectly. Am I right?

Also I wonder assuming $u$ is public and given in the corresponding relation, if we can omit this step and directly run Protocol 2?

One of the authors give an anwser:

  Protocol 2 proves the following statement: "given a point P, there
  exist vectors a and b such that P = aG + bH + *G". This problem
  is that this statement isn't very useful. If I give you a point P,
  it's nice to know that I can deconstruct it into some sort of inner
  product thing, but in practice you typically know what  should
  be, and you want a proof that it's the correct thing. We'll call the
  statement being proved here Statement 1.

  So the statement we really want is "Given P and c, there exist vectors
  a and b such that P = aG + bH and c = ". Same as above, but I've
  moved the actual inner product "out of hiding" by taking it out of P
  and making it explicit. Call this Statement 2.

  The obvious way prove Statement 2, which we want, given only a proof
  system for Statement 1, which we have, would be for the verifier to
  compute "P' = P + cG" and ask for a proof of Statement 1 on P'. This
  doesn't work, because a malicious prover could simply prove Statement
  1 on a point P', then choose c to be whatever he wanted and provide c,
  P = P' - cG to a verifier.

  There are a few ways to prevent this. The tactic chosen in the paper
  is to force the prover to choose P before he learns what G is. Then he
  can't set P = P' - cG; for a given P' this is either true or it isn't!
  Instead, the prover is forced to choose P' = P + cG, which is exactly
  what we want him to.

  So how can we force the prover to choose P before knowing G? Easy,
  hash P to get a new value x and replace G with xG.


Why use CBC-MAC? Why not just apply hash function on the whole message? Why not just apply hash function on the whole message? Why convert that message into blocks and hash those blocks? To avoid collisions?

A hash function is not a MAC, although you can turn it into a MAC (see e.g. HMAC).

The purpose of a MAC is message authenticity / integrity -- to prevent attackers (i.e. people who don't know the secret key) from modifying the message or forging fake messages.  A hash function trivially cannot fulfill the function of a MAC, because hash functions are unkeyed -- thus an attacker can always forge fake messages because they can calculate the digest of any message as easily as the legitimate parties.

With a MAC, such as CBC-MAC or HMAC, only the people who know the secret key can easily calculate the authentication 'Tag' for a given message, so if a message is sent accompanied by the correct Tag for that message then the receiver knows the message was almost certainly sent by someone who knew the key, and has not been altered (i.e. changed to a different message) in transit.


Generating dataset for LFSR stream cipher I have implemeneted the code for cryptanalysis of LFSR stream cipher . But I have a problem with generation of dataset i.e to get valid  pairs using LFSR stream cipher. In the stinson book it is mentioned that if coefficients $$(c0,c1,\dots,cm-1)$$ are chosen in suitable way and if non-zero $$k=(k1,\dots,km)$$ is chosen then we will get a periodic stream cipher with period $2^{m-1}$.

What should be the values of $$c0,c1,\dots,cm-1$$ that I should choose?

Firstly using an LFSR output as a keystream generator is insecure, due to the Berlekamp-Massey attack which only needs $2m$ bits of known or guessed plaintext to break the stream with period $2^m-1.$

The coefficients  you are asking about, must define a polynomial $$c(x)=c_0+c_1 x +c_{m-1} x^{m-1}+x^m$$ with $c_0=1,$ and $c(x)$ must be primitive. See Wikipedia here.


Are there any practical differences between running a PRNG on a subset of bits from an RNG compared to running the RNG? Given an RNG and a PRNG.

We define RNG(k) to mean that the RNG produces k random bits.

We define PRNG(k, seed) to mean that the PRNG uses seed to produce k pseudo-random bits.

Case 1: - Generate n random bits using just the RNG.

bits = RNG(n)

Case 2: - Generate n random bits using the PRNG, and using the RNG as a seed

seed = RNG(n/2)

bits = PRNG(n, seed)

My question is whether there is any practical or even theoretical difference to these in terms of security?

From an outsider, I am assuming that both would seem to be completely random bits.
How does the amount of random data fed to the PRNG from the RNG affect the randomness? My intuition is that if the PRNG is fed less than 256 bits of random data, then the result from the PRNG can be calculated by brute force.

In 99% of cryptography there is no practical difference between your cases as long as $ |seed| = \frac{n}{2} \ge 128$.  Computational indistinguishability means that the streams from both cases will appear properly random. Our current knowledge is insufficient to invert a good well seeded CSPRNG (your PRNG). Information theory suggests that inversion can't be ruled out, but we can't do it as yet. Perhaps tomorrow or the day after. See P=NP and Kolmogorov/algorithmic complexity.

The missing 1%.  For the truly dedicated who use one time pads (OTPs), there is a huge difference between the cases.  Information theory dictates that case 1 can create a OTP.  Case 2 specifically requires $ |bits| < \frac{n}{2} $.  Otherwise the output is theoretically invertible. In this case though, the above theorem implies that the output from PRNG need only to not introduce bias.  It need not be cryptographically secure, nor even a dedicated PRNG. A simple random matrix will do.  But it begs the question of why bother if you already have a functional TRNG running at a similar rate?

Consequently, your RNG is more random than your  PRNG from a certain perspective.  It's the same differentiator that separates /dev/random from /dev/urandom in blocking *nixes.


Is it possible to calculate the random factor $r$ from a encrypted message and the private key in a Paillier cryptosystem? I have already done my research and found various sources that state that it is possible but there are also a lot of them that says it is not possible to recover $r$. This Q/A on this site for example even states the formula to get it. I don't know if it is wrong or I am missing something since I was not able to make a working implementation of it.

Some friends told me it is impossible to get $r$ back since it was raised during encryption to the $n$-th power and ended up in a smaller subgroup which results in a loss of information that renders it unable to be recovered.

I asked on reddit and got told the following:

$r$ is choosen to be between 0 and $n^2$. The plaintext can be between $0$ and $n$. The Ciphertext is however also between $0$ and $n^2$. Since the plaintext is fully preserved, the same is impossible for the randomness, as this would otherwise violate the theorem that lossless compression is impossible.

I would like to know whether it is possible to calculate $r$ and how it is computed given that I have:

$C \to$ ciphertext
$P \to$ plaintext
$N \to$ public key modulo $(p\cdot q)$

Also if it is not possible for all $r$ values to be recovered I would like to know if it would be possible to recover $r$ values smaller than $m$ bits (I know that reducing $r$ bit length makes the encryption less secure)

It is strange that Wikipedia propose to choose $r\mod N^2$ while $r^N\mod N^2$ depends on $r\mod N$ only:
$$(r+tN)^N=r^N+r^{N-1}tN^2+\ldots\equiv r^N\pmod{ N^2}.$$ It means that you can recover only $r\mod N.$ In order to do it you can use the formula from the cited answer
$$r\equiv (r^N)^M\pmod{ N}, $$
where $M = N^{-1}\bmod \phi(N)$.


What does ⊕ mean in cryptography? Can someone please help me with the question below?

Explain why 0 ⊕ x ≠ 1 ⊕ x, whatever the value of the bit x.
Hence, explain why flipping a bit in the plaintext produces a predictable
change in the ciphertext when using a stream cipher that XORs the
plaintext with the keystream to produce a ciphertext.

What is the name of the circle in the middle ?

The symbol of the circle with the + in it is one of many symbols for exclusive-or. XOR, EOR, EXOR, ⊻, ⊕, ↮, and ≢. Binary OR is true when either input is true; binary XOR is true when exactly one input is true. If both inputs are true, the XOR result is false.

One property of this is that if either input bit flips, the output bit will also flip. That's sort of the definition of XOR, so you'll have to figure out how to reword that for your stream cipher question.

A XOR B Truth Table
Input   | Output
A   B   |
________|_______
0   0   | 0
0   1   | 1
1   0   | 1
1   1   | 0

0 = FALSE
1 = TRUE


ECDSA for encryption ECDSA keys are much shorter than RSA keys, but typically only used for signing, not encryption.

Is there an accepted way of doing this?

(https://bitcointalk.org/index.php?topic=196378.0 deliberately says don't use it.)

Note: I'm only looking at encrypting tens of bytes of data, so no AES suggestions please.

The ECDSA algorithm can't be used for encryption. It's not that there's no accepted way to do it, it's that it's simply not possible to do so. Likewise, RSA signing can't be used to encrypt (there's a mandatory hash in signing that you don't want in encryption). However, RSA signatures work similarly to RSA encryption; they aren't interchangeable, but fundamentally RSA signing, verification, encryption, and decryption all revolve around running the RSA operation on some data $m$ with one of the exponents $e$ (i.e. computing $m^e\pmod{n}$). You could, by making some not-huge changes to RSA signing, get an encryption scheme.

In contrast, ECDSA looks fairly different from any encryption algorithm. Verification looks nothing like signing, and the private key and public key are different things (one's a point, one's a number), so with the public key you can't do anything that looks like signing. A change to let you encrypt wouldn't be called ECDSA, as it wouldn't particularly resemble it.

(There are ECC signing and encryption schemes both called ElGamal; ECDSA is based on ElGamal signing. However, they just share a name because that's the guy who invented both of them; they don't look particularly similar, aside from both relying on discrete logarithm. RSA encryption and signing might also have had different names if they weren't invented by the same people.)

So ECDSA simply can't be used for encryption -- it looks fundamentally different from encryption schemes. What the person on that site did was create an encryption scheme unrelated to ECDSA (but rather similar to ElGamal encryption) that happens to use the same key format. ECDSA keys, ECDH keys, ECIES keys without shared secrets, ElGamal encryption keys, ElGamal signing keys, and the keys of most other ECC systems I'm aware of look rather similar: there's a set of curve parameters (which are generally the same for everyone), and then the private key is an integer $k$ and the public key is $k$ times the generator point found in the curve parameters. This is the standard keypair for something relying on discrete logarithms; with DH and DSA, the keypair is also basically that (just replace $k\times G$ with $g^k$). In that sense, there are all sorts of ways to use ECDSA-style keys for encryption; ECIES is probably your best bet.

That said, ECDSA keys should not be directly reused as encryption keys. Using the same key for two schemes generally a bad idea (they aren't designed for that, and may interact insecurely), and there are often differences in key management between encryption and signing. However, the general structure is already used in plenty of encryption systems.


Using same key and nonce for different field of the same document I have some fields, similar to NAME, SURNAME, EMAIL, ADDRESS...
I'm using NaCl for symmetric encryption.
Is bad If I Encrypt every field with the same key and nonce?
They are encrypted and stored separately.
Thanks for help

I will assume you're asking about NaCl crypto_secretbox, although the same considerations apply everywhere ‘nonce’ appears in the NaCl API.

  Is it bad if I encrypt every field with the same key and nonce?

Yes, it is very bad.  If you reuse a key/nonce pair for two different messages, you violate the security contract of NaCl.  It is so bad that an adversary who knows the plaintext/ciphertext of one field can decrypt all the other fields, and forge arbitrarily many more fields.

Here are a couple of things you can do instead:

If you never modify a field, and you can uniquely name each field—e.g., name each field by (table name, column name, rowid), as long as you never reuse a rowid—then you could derive a key by a pseudorandom function of the field name: Given a master key $k$ and a field name $f$, use $k_f = \operatorname{HMAC-SHA256}_k(f)$ as the key to encrypt the field, with an all-zero nonce.

However, if you ever modify a field, even this is no good in case an adversary ever sees two versions of the same field, which would again violate the security contract.  If you additionally have a version number so that (table name, column name, rowid, version) is unique, you could use that instead (or use the version number as the nonce).
If you are willing to allow an adversary to see when a field value is repeated in multiple places or at multiple times, you can use a deterministic authenticated cipher.  NaCl doesn't have one built-in, but here's a relatively simple one you can make out of parts available in NaCl, which is designed to make a security reduction theorem easy to prove:

Parameters: 512-bit master key $(k_1, k_2)$, field name $f$ encoded so that no field name is a prefix of another field name.

(The field name need not be unique, but if you repeat a field name then the adversary will be able to tell when the field value is repeated.  Typical prefix-free encodings might be either (a) making sure every field name is exactly the same length, or (b) NUL-terminated field names if field names can't have embedded NULs, or (c) length-delimited field names with a prefix-free encoding of the field name's length followed by the field name.)
To store a field value $m$:

Compute the authentication tag $t = \operatorname{HMAC-SHA256/192}_{k_1}(f \mathbin\| m)$.  Here HMAC-SHA256/192 is first 192 bits of HMAC-SHA256.  (You can compute HMAC-SHA256 with crypto_auth_hmacsha256 in NaCl.)
Compute the unauthenticated ciphertext $c = \operatorname{XSalsa20}_{k_2}(t) \oplus m$, using $t$ as the nonce for XSalsa20.  (You can compute XSalsa20 encryption with crypto_stream_xsalsa20_xor.)
Store the concatenation $t \mathbin\| c$.

To load an encrypted field value $\hat t \mathbin\| \hat c$ (which may or may not be the same as what you previously stored, $t \mathbin\| c$):

Compute the putative plaintext $\hat m = \operatorname{XSalsa20}_{k_2}(\hat t) \oplus \hat c$.  (The forward and backward directions of XSalsa20 encryption are the same, so also use crypto_stream_xsalsa20_xor here.)
Check whether $\hat t \stackrel?= \operatorname{HMAC-SHA256/192}_{k_1}(f \mathbin\| \hat m)$; if not, immediately erase $\hat m$ and either drop the field on the floor or raise an alarm.  (Make sure to do this check in constant time.  NaCl provides crypto_verify_16 and crypto_verify_32 for constant-time comparison; you can use crypto_verify_32 for this if you just zero-pad the 24-byte tags up to 32 bytes.)
Otherwise, if verification succeeded, return $\hat m$ as the value of the field.

There are other deterministic authenticated ciphers on the market too, like AES-SIV and AES-GCM-SIV, but they have much smaller safe data volume limits than the one I just described, and they essentially require hardware support to avoid timing side channel attacks.


Encrypting decimal values with AES I have a column in a database table called "Amount" that will store decimal values encrypted with AES. It's highly likely that the same amount will exist in multiple rows in the table and be encrypted with the same key. Furthermore, most of the plaintext values that will be encrypted are <5000. Are there any specific factors I need to consider or be aware of that might affect security in this sort of scenario vs a scenario where I'm storing some other data type such as strings with unique and unpredictable values? More specifically, I'm wondering if this scenario is vulnerable to known plaintext attacks.

You don't normally encrypt anything with just AES.  AES is a block cipher, and needs to be used with an appropriate mode of operation in order to securely encrypt general data.

In general terms, there are two kinds of modes of operation: traditional ones, such as CBC, CFB, OFB and CTR, which only protect the data against passive attacks by eavesdropping adversaries, and authenticated modes which also protect the data against active tampering.  While a traditional mode of operation may be sufficient for your particular needs, my advice would be to always use an authenticated mode such as AES-SIV if at all possible.  It's safer, and has no real down sides.

In any case, as long as you use AES with a secure mode of operation, with a random and/or unique IV/nonce as required by the mode, and respecting any other relevant constraints such as the maximum number of plaintexts encrypted with a single AES key (e.g. up to $2^{48}$ plaintexts for AES-SIV), and take care to keep the AES key secret, then you're safe from any known-plaintext (or, for authenticated modes, even chosen-plaintext) attacks.  For details, consult the definition and any relevant standards documents for your chosen mode of operation (such as RFC 5297 for AES-SIV).

Ps. Many lists of block cipher modes of operation, such as the Wikipedia page I linked to above, also include "ECB mode".  This mode exists to provide direct access to the underlying block cipher, and generally should not be used except to implement other modes of operation (or MACs or other similar block cipher based cryptographic algorithms).  In particular, it is not generally secure against known-plaintext attacks.

In your particular use case, where all the messages to be encrypted consist of small numbers, one can define various custom schemes that can provide known-plaintext and even chosen-plaintext attack resistance without using a conventional mode of operation (and thus possibly avoiding the slight storage overhead they require).

For example, you could encode your numbers as 64-bit integers, combine each integer with a unique 32-bit nonce value (ideally, a unique ID for the database row the number belongs to) and a fixed 32-bit check string (e.g. all zeros), and encrypt the resulting 128-bit block with the raw AES block cipher (i.e. "ECB mode").  This would produce a 128-bit ciphertext which is guaranteed to be unique (as long as all your nonces are distinct), which is tied to the database row it belongs to (via the nonce), so that moving an encrypted value from one row to another can always be detected as a forgery, and which is fairly resistant to forgery attacks even if the nonce cannot be checked (since a forged ciphertext has only a $1/2^{32}$ chance of decrypting to something with the correct check value).

However, while such a scheme should indeed be secure, I would generally not recommend it, since it isn't standardized (and thus requires extra implementation effort and extra security review) and lacks the flexibility of standard modes of operation.

In particular, using AES-SIV (with the row ID as the nonce) achieves a comparable security level, requires less than twice as much storage space (128 + $d$ bits, where $d$ is the size of the field being encrypted), and allows you to also link the ciphertext with arbitrary associated data (e.g. column name, timestamp, transaction ID and/or any other relevant unencrypted metadata) and to use the same method for encrypting other data of arbitrary type and size.  It's also a standard construction provided by many crypto libraries, and hopefully familiar to anyone reviewing your design.


Comparison Affine Coordinates and Projective Coordinates Addition in Excel Kurve : EC : $y^2=x^3 + x + 1$
Generator:$(1,7)$
$p=23$

Result in Affine use Excel:
$P=(1,7)$, $Q=(7,11) \implies P+Q=(18,20)$

Result in Projective use Excel:
$P=(1:7:1), Q=(7:11:1) \implies P+Q=(15:2:9)$

$U = U_1 - U_2\ $ where $\ U_1 = Y_2 ⇤ Z_1, U_2 = Y_1 ⇤ Z_2$
$V = V_1 - V_2\ $ where $\ V_1 = X_2 ⇤ Z_1, V_2 = X_1 ⇤ Z_2$
$W = Z_1 ⇤ Z_2$
$A = U^2 ⇤ W-V^3-2V^2 ⇤ V_2$
Then
$X_3 = V ⇤ A$
$Y_3 = U ⇤ (V^2 ⇤ V2 - A) - V^3 ⇤ U2$
$Z_3= V^3 ⇤ W$

Is the result correct for projective coordinates (X/Z,Y/Z), because it should be same with affine (18:20:1)?

The projection coordinates you got are wrong. We can tell that because those coordinates do not correspond to a point on the curve.

We have $15 \cdot 9^{-1} \equiv 17$ and $2 \cdot 9^{-1} \equiv 13$; when we plug $x = 17$ and $y = 13$ into the original curve equation, we do not get equality, and so we know something went wrong.


Is there a signature scheme in which private keys can't be linked to their signatures? Normally in a signature system, the private key can be used to derive the public key, and therefore verify any given signature signed by that private key. Can we create a system without this property?

Namely, I'm looking for a signature scheme in which given a signed message and a private key, you can't tell whether the private key was used to sign the message; only the public key (or rather verifier key) can.

A corollary is that public/verifier key is not derivable from the private key. In addition, the signing process must be stochastic, as otherwise you could sign the message and see if it produces the same signature.

The use case I have in mind is that Alice would have 100 private keys, with one key be the distinguished "true" key, and then send these 100 public/verifier keys to Bob (and then Alice would delete the 100 private public keys from her computer). She would always sign messages with "true" key. Then, if Alice is captured, the adversary can not know which private key is the "true" key even after applying Rubber-hose cryptanalysis (since they can't tell whether Alice is lying or not). If one of the bad keys is used, Bob will know that either Alice's computer was compromised, or she signed it under duress.

The use case I have in mind is that Alice would have 100 private keys, with one key be the distinguished "true" key, and then send these 100 public/verifier keys to Bob (and then Alice would delete the 100 private keys from her computer). She would always sign messages with "true" key.

If she deleted all private keys, how can she then always sign with the true key? She has to keep all private keys, because in a rubberhose attack, the adversary would demand access to check what kind of private keys Alice has stored. Obviously she could only sign messages with a key she didn't delete again.
But for your scenario, you actually don't need an unusual signature scheme, here are two ways to achieve what you want:

Alice uses common signature schemes (they don't have to be the same, as long as the signatures have equal length), with all verification keys being public. And when she sends a message to Bob, she always uses the same signing key. And now she always encrypts the signature with Bob's public key. As long as Bob isn't compromised, no one knows which key was used.
as fgrieu pointed out, the randomized signatures can be used to get covert channels. Basically you agree with Bob on at the setup on a function over a bit array. Examples would be lowest (few) bit, parity of bits, 1st bit xor 5th bit, etc.
In RSA-PSS you can put that information directly in the padding. In DSA (or ElGamal signatures) you would have to put it in the signature itself or an intermediate result of the verification, because the verifier can't extract $k$ from the signature. Instead, you would have to try multiple values of $k$.

But coming back to a previous part of your question:

Namely, I'm looking for a signature scheme in which given a signed message and a private key, you can't tell whether the private key was used to sign the message; only the public key (or rather verifier key) can.
A corollary is that public/verifier key is not derivable from the private key. In addition, the signing process must be stochastic, as otherwise you could sign the message and see if it produces the same signature.

ElGamal and DSA signatures don't fit this: From $x,r,s$ you can calculate $k$, and then check if $r=g^k$ holds. If you consider the RSA setting, there is a really interesting property, which Ilmari Karonen pointed out in his comment: Assume that there are two keys, with each one consisting of the modulus $n$ and one exponent, s.t. we get the usual RSA relation. If you have random values for the exponents, e.g. both have to be in a certain range, then both exponents are actually drawn from the same distribution, and knowing one does not reveal the other - under the RSA assumption.
However, there is one problem: Verification keys are public. As soon as the attacker gets hold of a signing key, they can calculate the product of the exponents. And with this the modulus can be factorized efficiently, so basically everything is out in the open.
At this point I am not sure what the adversary actually knows exactly. In general, (basic) signature schemes are built from oneway-trapdoor functions and there has to be a efficiently computable equation for the verification. In order to achieve this, the public key is always derived from the private key with the trapdoor in mind, so that you can't calculate "backwards" to the private key. But if you want that this computation is infeasable, then this might imply that the key generation can't be done efficiently.
However, group signatures or ring signatures might be of interest to you, because they have following properties:

There are different signing keys (derived from a master key) and just one verification key
In ring signatures it is not possible to determine which signing key created a signature
In group signatures, the master key is required to determine which key signed a message.

In your case you could give Alice multiple keys, but there is a problem: If you require Bob to be able to tell which key signed a message, then you need group signatures and Bob has to have the master key. Because otherwise he won't be able to tell the difference either.


Meaning of Dilithium-1024x768 or Dilithium2 Can someone explain me the meaning of 1024 and 768 in Dilithium-1024x768 in the algorithm? And the meaning of 2 in Dilithium2 in the algorithm?

1024 and 768 refer to the dimension of the base "generator" matrix $A$, these numbers are multiples of 256, which is the size of the module ring.
If the terminology is a bit confusing so far, then let me explain a little:

$A$ is a component of the public key, it's computed from a random seed chosen during key generation. It's also used in signing and verification.

Dilithium (along with Kyber, Saber, and some others) uses a "modular" lattice. That is, instead of a polynomial ring, or a matrix of integers, they use a matrix of high-dimension polynomial ring (degree-256 in the case of Dilithium and Kyber, etc.). This greatly improves performance and the scalability of the security level.

Some may question: "didn't document say $(k,l) = (4,4)$ (or $(4,3)$ in earlier versions)?". That's true, and those numbers are referring to when you consider module ring as matrix element. If you expand the ring modules into 256-by-256 matrices, the full matrix will be 1024-by-768. And for those familiar with lattice-reduction attacks, 4 is obviously too small a dimension that can be easily attacked.
As for "2", I'm not certain. Maybe it just refers to the version of Dilithium submitted to NIST in the 2nd round.


Can two cipher letters per plaintext letter easily defeat character frequency analysis? For a class 5 years ago I wrote a paper about "defeating character frequency analysis by using  two cipher letters per plaintext letter" (jamesjava.blogspot.com/2009/08/defeating-character-frequency-analysis.html).

Quote:

  Using two letters in the cipher text for each letter in the plaintext can be a good way to create a flat character distribution.

  The algorithm is to partition the 676 2-letter combinations based on the standard character frequency. i.e. if the standard frequency for a letter is 5% then it will get 5% of the 2-letter combinations (randomly selected). This doubles the size of the data, could include spaces & punctuation, and makes a much larger key.

  Note that some letters may get dropped because they occur less than 1/676 (0.15%) of the time. Both 1-gram and 2-gram frequency analysis produce a nearly uniform histogram (variation appears to only be caused by rounding). Two-gram results: P&P=5,117%; SH=5,013%.

  Therefore this technique was extremely effective with no obvious weaknesses.

I didn't get much feedback from the professor so I wonder if anyone can comment on this and tell me if my conclusion is correct.

It is probably impossible to remove language characteristics completely with a substitution cipher. Your algorithm flattens out single character frequencies, but that's it kinda.

Language bigrams (your cipher-quadruples) might not be uniform distributed. The reason for this is simple: Bigram probability is not just the product of the probabilities of both letters - they are not independent variables.

Let's make an example (frequencies from http://www.cryptograms.org/letter-frequencies.php):

Letter t with frequency 0.09056 => 61 cipher-bigrams for t
Letter h with frequency 0.06094 => 41 cipher bigrams for h
Bigram th with frequency 0.03882
Now there are $61*41=2501$ cipher quadruples for the original bigram th, and all of them have the same probability. However, $2501$ of $26^4 = 456976$ possible qudruples is just a fraction of 0.005473. So now the number of ciphertext quadruples for *th does not match required number to enforce a uniform distribution.

An other way to attack might work with those bigrams which are very unlikely or even impossible in English language.


Hash length extension attack - SHA256 to 512 - impossible, correct? Just want to be sure about something before I sign off on a method we're about to put into place.

We have a secret, to which a user-defined key is appended. The user can see the SHA256 hash of the secret.

The secret and the user-key is then hashed with SHA512 to obtain results.

Given the ending hash is SHA512, and the user only knows the SHA256, a hash length extension attack would be impossible, correct? As there is no way to convert a 256 to 512, or to backtrack the 256?

From every angle I can see it, it shouldn't be possible. But want to confirm with those more well versed than I. Thanks.

No, there is no known way.

It would actually be rather surprising if there were even a theoretical way; the SHA-256 and the SHA-512 compression functions are rather different (for one, one works with 32 bit words and the other works with 64 bit words); one wouldn't expect them to share any sort of relation.


Order Preserving Encryption for Numeric Data Values How can I ensure order of encrypted data i.e., Enc(m1) < Enc(m2) where m1 < m2, and all messages are integer values.

I have gone through Order Preserving Encryption discussed in Enabling Search over Encrypted Multimedia Databases.

According to the literature, for sorted data values (i.e., words), lower limit (l_w) and upper limit (U_w) are defined according to the frequency count of a word and estimated value (encoded value) is selected by Linear Spline Interpolation within the defined limits.

I am finding it hard to define lower and upper limits for the following data values. I want to encode the frequency with the range of [0 – 10,000] and DocCount with in [0 - 500]. However, I have only one data point (i.e., w_i) within each range (i.e., l_w_i to U_w_i), how can I find interpolant of the values.

DocCount    Word Frequency
10          1
8           2
6           3
5           4
3           5
2           6
1           7
0           8
0           9
0           10

Or

Is there any other way through which I can ensure order of the encrypted data. On StackOverFlow I was referred to homomorphic encryption – I am familiar with Pascal Paillier crypto system, any idea how can utilize it to preserve order among encrypted values.

To answer your second question, Paillier and other CPA-secure homomorphic encryption schemes cannot provide order-preserving encryption. The security of these schemes rely on using a random factor during encryption to ensure their ciphertexts are distributed randomly in the ciphertext space. OPE must use a weaker notion of security than CPA.

In terms of your first question, I don't know enough about the data structure behind OPE to follow what you are asking. I know OPE is an available option in CryptDB so maybe they have automated the process of defining the limits you are asking about?


Slow hash algorithm that does not require salt? I usually choose bcrypt when hashing as I can set the work factor to slow down the calculations of the hash. However, I have to keep a copy of the hash in order to verify it (since it includes the salt) when the same input comes around again.

Are their any A) common and B) slow hashing algorithms that do not require a salt? In other words, I don't need to preserve the output state in order to calculate the exact same hash again?

I am not looking for a more secure/unbreakable hash - just one that takes a long, long time to work out.

At this point it seems that multiple rounds of SHA-256 is my current best option.

You can use any common slow hash construction that takes a salt with a constant salt. This includes scrypt, bcrypt and PBKDF2.

You obviously lose the benefit of the salt. Since the purpose of a salt is preventing multi-target attacks, now an attacker can attack all hashes at the same time. I'd use at least a salt that's unique for your application, so an attacker can't attack your application at the same time as others.

Personally I'd go with scrypt, since it strengthens the most for a given derivation time limit, but you can use bcrypt or PBKDF2 if you prefer older/more popular constructions.


In English, are there any words which encrypt to other words under the Caesar Cipher? Are there any words in the English language which, when encrypted using the Caesar Cipher with any key, result in another English word? How may one go about determining which Caesar shifts are weakest in this context?

Actually, we have a four-way (that is, four words that will can be converted into any of the others with the right shift).  These words are:

ax, by, he, if

Other two letter words are:

am <-> my
at <-> pi
do <-> it
hi <-> no

We also have

the <-> max

I didn't do a systematic search for words over two letters; there certainly do appear that they are moderately plentiful

I've done a more systematic search over longer words; ignoring extremely obscure words, the best I found were

abjurer <-> nowhere
inkier <-> purply
fusion <-> layout
manful <-> thumbs
primero <-> sulphur
steeds <-> tuffet

(OK, 'tuffet' missed by 'obscure' criteria; I still liked it).

So, yes, there certainly are words can be be encoded into other words


What's the appeal of using ChaCha20 instead of AES? I read about ChaCha20 being used in TLS by Google, SSH, and towards standardization in general.

What's the appeal of using something other than AES, what with AES receiving dedicated CPU instructions on various architectures to make it so efficent?

I believe there are three main reasons why ChaCha20 is sometimes preferred to AES.

On a general-purpose 32-bit (or greater) CPU without dedicated instructions, ChaCha20 is generally faster than AES. The reason for this is the fact that ChaCha20 is based on ARX (Addition-Rotation-XOR), which are CPU friendly instructions. At the same time, AES uses binary fields for the S-box and Mixcolumns computations, which are generally implemented as a look-up table to be more efficient.

AES's use of a look-up table with an index derived from the secret makes general implementations vulnerable to cache-timing attacks. ChaCha20 is not vulnerable to such attacks. (AES implemented through AES-NI is also not vulnerable).

Daniel J. Bernstein is having significant greater-than-average success in advertising his algorithms. (I'm not implying there are no merits. I'm just stating the fact that his algorithms have success in terms of deployment).

Of course, other reasons justify the choice of AES instead of ChaCha20.
To name a few:

Dedicated instructions on high-end CPUs
Amount of received cryptanalysis
Availability of studies on side-channel (other than cache timing) protections


What is the probability of breaking the AES algorithm? I am doing a project which requires the encryption to be done using AES. Is it really possible (technically) to crack AES?

If yes, please tell me:

What is the probability of breaking AES?
How does the round number influence this probability? Do more rounds really help in decreasing this probability?
What is the contribution of each round towards enhancing the security?

Of course it is technically possible to crack AES. The method for doing this is to guess the correct key. Assuming you know something about the plaintext, you can easily verify that the key you guessed resulted in the correct decryption.

The probability of breaking AES using this method? AES has 128, 192 and 256 bit key variants. Thus if there are $n$ bits in the key, the probability that your guess is correct is $\frac{1}{2^n}$.

What is the role of increasing the rounds and does this make it harder to break? In general, more rounds are required to diffuse bits. That is why you see more rounds with the larger key sizes. In the specific case of guessing the key, it only slows down decryption. It does not change the probability of a break. There are other articles on this site on increasing rounds. I'll try to find them and add links.

What is the contribution of each round towards enhancing the security? This is hard if not impossible to say. If you modified AES to have only 1 round, it would be trivial to break. Up it to 10 rounds for AES-128 and we can't break it. Up that to 1 million rounds and the cipher isn't really much more secure but takes so long to encrypt or decrypt that no one will use it (a kind of dimishing returns). See fgrieu's comment for additional information.


Computation indistinguishability questions The definition I have is:

Two probability ensembles $X = \{X_n\}_{n \in \mathbf{N}}$ and $X = \{Y_n\}_{n \in \mathbf{N}}$ are computationally indistinguishable if for every probabilistic polynomial-time algorithm $D$, every positive polynomial $p(\cdot)$,
and all sufficiently large $n$ we have
$$
|P(D(X_n, 1^n) = 1) -  P(D(Y_n, 1^n) = 1) | < \frac{1}{p(n)}.
$$

I'm having trouble digesting some ideas and the notation here.

Does $X = \{X_n\}_{n \in \mathbf{N}}$ mean $X = X_1, X_2, \ldots$
where each $X_i$ comes from the same distribution? So if our $X$ distribution is $0-1$ coin flips, then $X$ is an infinite sequences of $0$s and $1$s ?

A note says "typically, each $X_n$ ranges over strings of length $poly(n)$". What does this mean? The distribution will take $n$ as some sort of input? In my coin-flipping example each $X_i$  gives us back just one bit...

I also want to ask why the $1^n$ is necessary as input to the distinguisher $D$, but I should probably understand the answers to my above questions first.

No, $X = \{X_n\}_{n \in \mathbf{N}}$ means $X = X_1, X_2, \ldots$ where each $X_i$ is a distribution.

So one could let each $X_i$ be the uniform distribution on strings of length $i$.

That means there is a polynomial $q$ such that for all $n$ and $x$, if $X_n$

assigns non-zero probability to $x$ then the length of $x$ is at most $q(i\hspace{.02 in})$.

The distributions do "take $n$ as some sort of input".

See these two questions for $1^n$.


Why is RSA preferred over Diffie-Hellman if they're both used to establish shared key? I've read that the RSA algorithm is preferred over Diffie-Hellman key exchange as it makes key management easier. In the context of online banking, before the RSA algorithm they would have to maintain a different shared key with every single one of their customers, instead of just having one public key and a private key.

But then I've also read that RSA is primarily used for exchanging a shared key for use in symmetric ciphers like AES. So surely no matter if the bank were to use DH or RSA they would still establish a shared key and key management would be just as much a problem as it was before?

RSA is rarely appropriate instead of DH for key exchange. It's mostly only appropriate if backwards-compatibility is required, or if keys need to be sent from one party to the other instead of generated for each session (eg for encrypting e-mail).

RSA is much, much harder to use securely. RSA requires padding of the messages, which is quite easy to screw up in ways that catastrophically break the security of the system. RSA is far more expensive to use in an ephemeral mode, and thus typically cannot provide forward secrecy. RSA keys are substantially larger than ECDH (Elliptic Curve Diffie-Hellman) keys. RSA key generation is much more complex (and harder to get right) than (some) ECDH key generation: RSA needs to generate large prime numbers & ensure that they are safe, while X25519 or X448 ECDH systems can use any random number of the appropriate length.

Where possible use ECDHE (Elliptic Curve Diffie-Hellman, Ephemeral). If you can't do that, use DHE. If you can't do that, use ECDH. If you can't do that, use DH. If you can't do that, THEN use RSA.

RSA can also be used as part of a signature scheme, but that's not relevant to this question since it's not comparable to DH which only does key exchange. TLS 1.3 uses RSA only for signing the DHE or ECDHE key exchange, and also supports ECDSA for signing.

NaCL, Libsodium, Libhydrogen, TLS 1.3, monocypher, and probably a few other libraries and cryptographic standards have dropped the use of RSA for key exchange.


What do the last chunks of the output string of Scrypt contain? When you use scrypt to hash a string, it will generate something like:

SCRYPT:4096:8:1:8zCQhTI8y2pdrFeIj2WYBJIbaLiePLOuXdbevG7XDV4qgUuiGPCXPFjh1aEmXQ/5u+SlCvz0KkcoOJtUWBkytfkCs2OZep60W+Nagv0gixqkcMn/PxoIqnOGIzyDWntEdsQKjYBHDYK5Va5VDHqoQxJeIm+yq3lJ4/y5dnL55RA=:zABi6opzkXwG627OUrk4KNUCiajY1xdM+PVmSC+VJS8=

The first part: SCRYPT:4096:8:1: is the "header" (identification and parameters used).

The second part:

zCQhTI8y2pdrFeIj2WYBJIbaLiePLOuXdbevG7XDV4qgUuiGPCXPFjh1aEmXQ/5u+SlCvz0KkcoOJtUWBkytfkCs2OZep60W+Nagv0gixqkcMn/PxoIqnOGIzyDWntEdsQKjYBHDYK5Va5VDHqoQxJeIm+yq3lJ4/y5dnL55RA=`

I believe is the actual hash (b64 encoded).

What is the last part? zABi6opzkXwG627OUrk4KNUCiajY1xdM+PVmSC+VJS8=, the salt?

UPDATE

I found this question: https://security.stackexchange.com/questions/88678/why-does-node-js-scrypt-function-use-hmac-this-way/91050#91050

bytes 0-5: The word "scrypt"
bytes 6-15: Scrypt parameters N, r, and p
bytes 16-47: 32 bits of random salt
bytes 48-63: A 16 bit checksum
bytes 64-95: A 32 bit HMAC of bytes 0 to 63 using a key produced by the scrypt key derivation function.

To my understanding, it describes the first and second part of the resulting string described previously. Unless I'm mistaken, the last part is not discussed there.

Bottom line

As commented by Maarten Bodewes, I have found that not all libraries will output the same string as I posted above. That one is specific for the Perl library I'm using (I was unaware of that). For example, take a look to these implementations, and you will see the hash doesn't look like that:

https://github.com/pbhogan/scrypt#how-to-use-scrypt
https://github.com/barrysteyn/node-scrypt#if-random-salts-are-used-why-do-all-resulting-kdfs-start-with-c2nyexb0

I should have started here:

sub scrypt_hash {
  my ($key, $salt, $N, $r, $p) = _scrypt_extra(@_);
  return undef unless defined $key && defined $salt && defined $N && defined $r && defined $p;
  return "SCRYPT:$N:$r:$p:" . MIME::Base64::encode($salt, "") . ":" . MIME::Base64::encode($key, "");
}

It explains that the last chunk is actually the base64 encoded key (hashed password). The second part (which I thought was the hashed password), is actually the base64 encoded salt.


Perfect secrecy and known ciphertext length From what I understand perfect secrecy means that the probability distribution of the messages are independent of the cipertext, right? How can the one time-pad be perfectly secret when the ciphertext is as long as the message in terms of bits?

Because for a given ciphertext I could for example know that my message is not longer than my ciphertext and therefore I could say that a given message occurs with higher probability?

You are correct that the security provided by a one-time pad is that a chosen-plaintext attacker can't distinguish between two messages of the same length, at least not with better advantage than their advantage at distinguishing the pad itself from uniform random.

Length, of course, can be a side channel for more interesting information, especially if variable-rate compression is involved!  For example, the distribution of page sizes when downloading Wikipedia is likely to be very different from the distribution of file sizes when downloading the WikiLeaks archive.

If you have a maximum message length, you could extend your messages up to that maximum length with (say) zeros.  But this can be costlier.  Alternatively, you could break messages up into chunks.  In any case, message length is something that a protocol designer must consider when striving for confidentiality!


How can I improve a password generation scheme based on a shared secret and URL? I currently use the following method to generate a different password on every website I have to login:

password = SHA1 ( mainPassword . domainName . number )

where . stands for concatenation.

Here are my questions:

Is this secure enough?
I mean, if somebody knows my algorithm and one or many passwords, could he find easily one of my other passwords? Up until now, most people I contacted believe it is true, but I didn't get any real strong certitude.
(Related to question 1) When one of my passwords is compromised, I just increment the number. Is this enough?
Now, as many people suggested, SHA-1 can be a bit too weak and many proposed to use bcrypt or even better scrypt. But, as I understand these two algorithms, it is more about encrypting than hashing. Is it secure to use the following passwords?

SHA1( SHA1( … SHA1( str ) … ))

Here is my reasoning:

It is difficult to retrieve str, knowing sha1(str).
I hope that to retrieve str knowing sha1(sha1(str)) one must do twice of the work.
Therefore retrieving str from sha1n(str) should be n times as difficult than to retrieve sha1(str).

I am almost sure there won't be any proof of this. But could I consider this method safe enough?

The problem is just to have a very good algorithm similar to bcrypt or scrypt for hashes without the nightmare of finding a correct implementation in all languages I used to implement this (JavaScript, Objective-C, shell script using openssl).

password = sha1 ( mainPassword . domainName . number )
  Is this secure enough?

Answer is no. Let me explain. The only part that is really unknown in the above is mainPassword. The rest can easily be guessed by a hacker. If your original password is weak (not many characters, no digits, no specials characters), the number of combinations to test is small enough for brute force attack (i.e., testing them all). sha1 is not going to help. You are also vulnerable to collision attacks (google it for more information).

You need to learn about salting and stretching. Use a sufficiently large random number too when you salt-and-strech. Make sure you stretch with enough rounds. Salt and stretch only works if the mainPassword is good enough in the first place.

  could he find easily one of my other password?

If you use a random when salting and stretching, it makes it much harder to guess another password from a known password.

  When one of my password is compromised, I just increment the number. Is it enough?

Absolutely not. It is very easy for the hacker to increase the number too. You really need to use salt-and-strechting with another random number.

  sha1( sha1( ... sha1( str ) ... ))

Not helping when used like that (again, learn about salting and stretching). If you are uncomfortable with SHA1, use SHA256 (or SHA512) as the hash function.

EDIT

  How to keep secret the salt in an open source project? The only other
  way is to make the user choose the salt which seems to be exactly the
  to ask for a longer password. Am I wrong?

Hiding the salt is not absolutely necessary. You could also include a timestamp in the salt-and-stretching. It would require you to perform extra rounds on the server side with the timestamp. If the timestamp is too old, refuse the log on.

EDIT2

To be complete. You can implement something like that:

User picks a password.
A = any public random;
FOR 1 TO 1000 (or more) hash = SHA( A || hash ); with user pwd
Store hash on server.
Logon -> Server picks a new large random R and sends it to client with authentication
Let t = current time;
User verifies authentication for received R.
User computes FOR 1 TO 1000 (or more) hash = SHA( A || hash ); with entered pwd
Then, FOR 1 TO 1000 (or more) hash = SHA( R || SHA( hash || t) );
Send hash, R, t to server
Server check t is ok (for replay)
Server computes FOR 1 TO 1000 (or more) SHA( R || SHA( stored_hash || t) );
Server checks computed against received, and eventually validates logon.

It will kill many attack venues, but it is impossible to eliminate them all.

EDIT II

Sorry, there is an issue with step 8 (and 11), this step needs to be performed 1000 times (i.e., or whatever the number of salt-and-stretch iteration you need) too, or it does not make sense to iterate 1000 in step 7 in the first place.


How AES treat string input to encrypt data and what will happen if the cipher key is less than that expected? The official docs of AES have several example of how hexadecimal or byte input can be encrypted. I have some problem about the input text and cipher key. My question is:

How can encrypt string input in AES or how AES treat string input? If I use a string input [example: "Admin"] than how AES encrypt it? If I use the following hexadecimal input: 32 43 f6 a8 88 5a 30 8d 31 31 98 a2 e0 [which has 24 bits less than the expected input for AES-128], than how can it encrypt?
How the cipher key is scheduled if it is less than 128 bit (for AES 128), or less than 192 bit (for AES 192) or less than 256 (for AES 256)? If I use the cipher key: 2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 [Which has 3 less hexadecimal input than the expected for AES-128], than how can it schedule for Add Round Key?

How the cipher key is scheduled if it is less than 128 bit (for AES 128), or less than 192 bit (for AES 192) or less than 256 (for AES 256)?

That is undefined; the AES specification does not address that possibility.  The AES 128 algorithm assumes that you give it 128 bits of key (and tells you exactly what to do with that key); it says nothing about what you should do if you're initially starting with less keying data.

The AES block cipher takes a 128, 192 or 256 bit key, and uses that to define a reversible mapping between 128 bit plaintext blocks and 128 bit ciphertext blocks.  However, we often want to do other things than mapping 128 bit strings to 128 bit strings; so we use AES in some sort of "mode of operation" which can perform more versatile functions (such as CBC mode, which with padding, can handle arbitrary sized plaintexts).  As modes such as CBC can handle odd sized plaintexts, and thus might be considered an answer to your first question.  I suppose a mode of operation could also define how to handle an odd sized key (I haven't heard of such a thing, but it wouldn't be inconceivable).


Is there a way of encryption that allows to check what encrypted values are close to their mean? I am looking for a way to allow parties to publicize encrypted values that can only be decrypted by one or a select few other parties, but that allow everyone to check how close they are to the mean of all such publicized values.

This of course would mean that there is some entropy that is lost; the encryption would not be perfect because certain information can be gleaned from the given values.

However, are there schemes in which this is possible? At first I thought it might be possible using Homomorphic Encryption, but as far as I now know, these seems to allow to calculate the mean as encrypted value, but not the process of comparing the other values against it.

Is there a way to do this?

If I understand what you're looking for correctly, that would completely destroy the security.

First off, if an attacker can compute the difference between her value and the mean, it is trivial to find the actual mean. Simply encrypt the number $0$ and then compare it to the mean.

If she can compute the mean of any subset, it's pretty trivial to recover plaintexts: just compute the "mean" of a single ciphertext. Even if you somehow make it work only for subsets of a particular size or something, she can still decrypt an arbitrary ciphertext $c$ like so:

$$ d(c) = (N+1)(\mu(S\cup m)-\mu(S\cup e(0)))$$

Where $e(0)$ is the encrypted $0$, $S$ is some arbitrary subset of the ciphertexts, $N$ is the size of $S$, and $\mu$ is the mean of a subset.


An Elliptic curve cryptography implementation which can be terminated I'd like to have an implementation of elliptic curve cryptography along the lines of secp256k1 which is secure until some information is published after which it is broken.

One idea would be to use elliptic curves over a ring $Z_n$ where $n=pq$ or perhaps $n=pqr$ where $p$, $q$ and $r$ are primes of similar size and the order of the curve over each factor is also prime. The factors would be small enough that discrete logarithms on curves over individual factors would be very practical but factoring $n$ would still be hard.

With the above construction the "order" of the ring would be a large composite which would be hard to factor so there wouldn't be a problem publishing that and the chances of happening across points for which the addition operation is undefined (hence leading to a factorization of n) is small.

These parameters could be used to implement a scheme which would be secure until the factorization of $n$ is published whereupon it is broken. Are there any problems with this scheme?

ByteCoin

If discrete logarithm on the curve over $\mathbb{Z}_n$ is easy then $n$ can be as easily factored, precisely by using the Elliptic Curve Factorization Method, in which we indeed work with a curve over the ring $\mathbb{Z}_n$ and fervently hope for the computation to fail, i.e. to hit a non-invertible value. With figures: in practice, ECM works well when the smallest factor is no longer than 200 bits, but an "easy" discrete logarithm on an elliptic curve requires a much smaller field (an effort at breaking a single discrete logarithm on a 128-bit curve has begun, but it will take several years).


Breaking Insecure Elliptic Curve Cryptography If you knew the entire equation of an elliptic curve $$y^2 = x^3 + ax + b~( mod ~~m)$$ given $a, b$ and $m$ which are all more than 70 digits in length, as well as a point $P$ and the point $t P$, with different orders, would it be possible to calculate $t$? What would be the fastest way to do this?

(I'm aware that $tP$ and $P$ not sharing the same order makes this less secure but I'm wondering how exactly to exploit it).

You mention your point has order
$$93556643250795678718734474880013829509\\196181230338248789325711173791286325820$$
 which factorizes as

$$2^2\cdot 3\cdot 5\cdot 7\cdot137\cdot593\cdot 24337\cdot 25589\cdot3637793\cdot5733569\cdot106831998530025000830453\cdot1975901744727669147699767.$$

Without much computing power, we can apply the Pohlig-Hellman algorithm to obtain
$$t\bmod4, t\bmod3,t\bmod5,\ldots,t\bmod5733569.$$

Using the Chinese Remainder Theorem, we can combine all these results to get

$$t\bmod\left(4\cdot3\cdot5\cdots5733569\right),$$
i.e.
$$t\bmod443208349730265573969192476820.$$

As @Ruggero remarks, the other primes are only about 80 bits. So with $\approx 40$ bits of computing power we could also break that discrete logarithm. It takes a little more effort than the others though, so if $t < 400\cdots 0$, then you may as well only do the easy ones.


Chacha20 internal counter/position and nonce I have to encrypt the communications between two devices. I was planning on using a timestamp(in seconds) and the serial number as the nonce. I know its impossible for me to send more than 100 messages a second. So potentially the nonce can repeat a couple of times in a second, but the internal chacha counter should work to make each nonce unique correct?

So potentially the nonce can repeat a couple of times in a second, but the internal chacha counter should work to make each nonce unique correct?

No.

YOUR OBLIGATION in the ChaCha security contract is to choose a unique nonce for every message you send; IN EXCHANGE, ChaCha provides IND-CPA security, meaning roughly confidentiality against a passive eavesdropper.

ChaCha does nothing to fulfill its contractual obligations for you if you violate your contractual obligations to ChaCha.  The ‘counter’ is an implementation detail of how ChaCha encrypts a single message; ChaCha itself keeps no state between messages—that is your job.  If you repeat a nonce, the security contract is null and void, and ChaCha provides no security whatsoever.

If you're exchanging messages sequentially in a conversation, I recommend that you simply count the number of messages you have sent so far and use that as the nonce.  This way you can cheaply reject replays too by refusing to accept old message numbers.
If you have no persistent state, but you do have access to an entropy source, you could use XChaCha instead of ChaCha (it is easy to write an XChaCha implementation in terms of a ChaCha implementation); then you can pick the 192-bit nonce independently and uniformly at random for each message, and send it along with the message.  But I recommend using message sequence numbers instead if you can.

By the way: You are actually using ChaCha as part of the authenticated cipher ChaCha/Poly1305, right?  I hope you're not building an application out of an unauthenticated cipher!


DES key expansion: why are these two descriptions different? I would like someone to explain me how to generate DES subkeys, because in the documentation that I saw, sometimes they say:

  "We rotate the initial key according to the number of iterations given by this sequence:
  1, 2, 4, 6, 8, 10, 12, 14, 15, 17, 19, 21, 23, 25, 27, 28."

and sometimes they say:

  "The two halves are each rotated to the left by an amount depending on the iteration stage, in the following order: 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1."

Do you have any idea why these descriptions are different?

I'm not going to look up the DES key schedule such, but the connection between your two sequences

$$( a_i ) = ( 1, 2, 4, 6, 8, 10, 12, 14, 15, 17, 19, 21, 23, 25, 27, 28 )$$

and

$$( b_i ) = ( 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 )$$

is obvious: $b_i = a_i - a_{i - 1}$ (with $a_0$ taken to be 0).

That is, the second sequence gives the difference between successive elements of the first sequence.

Edit: OK, I did look it up, see link above.  Basically, the first sequence gives the number of bits by which the halves of the original key need to be rotated to obtain the $i$-th subkey, whereas the second sequence gives the number of bits by which the halves of the previous subkey need to be rotated to obtain the next one.  That's all there is to it.


Question on using endomorphism on secp256k1 and negative results I have read section 3.5 (algorithm 3.7) in "Guide to Elliptic Curve Cryptography", and have been trying to implement endomorphism on secpt256k1 to speed up calculating $kP$ by changing it into 2 point multiplication operations over half-size bit widths of k with a final point add. I tried to implement this in Python first to make sure I had the equations correct.

I can follow algorithm 3.7 to calculate $k_1$ and $k_2$, but for some values of k input I will get a negative $k_2$.

Does this mean when I evaluate $kP = k_1P + k_2φ(P)$, where
 $φ(P) : (x, y) →(βx, y)$ , I have to either convert $k_2$ to positive by doing $k_2' = n - k_2$ where $n$ is the curve order (this would not make sense as now $k_2$ would be the same bit size of $k$), or do I calculate $k_2φ(P)$ and then find the inverse of this point (just negate the Y coordinate) before adding it to $k_1P$?

This is my code I wrote (I am also not sure if all these operations should be mod n or not).

I do a final check to see if the values match what they should in the textbook ($k = k_1 +k_2λ$ mod n).

But I also have the problem of regardless of $k_2$ being negative (and so I would do the final inversion), the result I calculate from $kP$ does not match the result when I don't use endomorphism (I am using the double-add algorithm for the two point multiplications, not point or NAF, if this makes a difference). I was wondering if anyone knows why?

def decompose_mult(k):
        curve_n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
        lam = 37718080363155996902926221483475020450927657555482586988616620542887997980018
        beta = 55594575648329892869085402983802832744385952214688224221778511981742606582254
        a1 = 64502973549206556628585045361533709077
        a2 = 367917413016453100223835821029139468248
        b2 = 64502973549206556628585045361533709077
        b1_neg = 303414439467246543595250775667605759171

        c1 = (b2*k) // curve_n
        c2 = (b1_neg*k) // curve_n

        c1_a1 = (c1*a1) % curve_n
        c2_a2 = (c2*a2) % curve_n

        c1_b1 = (c1*b1_neg) % curve_n
        c2_b2 = (c2*b2) % curve_n

        k1 = (k - (c1_a1) - (c2_a2))
        k2 = c1_b1 - c2_b2

        print ("k1 ", k1, " bits ", k1.bit_length())
        print ("k2 ", k2, " bits ", k2.bit_length())

        k_test = (k1 + k2*lam) % curve_n
        if (k_test == k):
                print("Values matched")
        else:
                print("Values MISMATCHED")
                print ("k_test ", k_test)
                print ("k ", k)
```

Do you mean Algorithm 3.77 on p. 129?

The algorithm has an explicit case for whether $k_{j,i} > 0$ or not, in the loop in step 8.2.  Obviously a conditional like this is bad news for fast constant-time arithmetic if taken naively.  But as you noted, you can simply do a conditional subtraction in the coordinate field to negate the point, and then do the point addition unconditionally.


Decryption of Alternating Step Generator I have programmed an alternating step generator in the following way:

I have three LFSR. LFSR_1 is being clocked in every step.
Every LFSR has an initialization vector.
And we have a text to encrypt.

If the output of LFSR_1 is 1 :

LFSR_2 is being clocked and calculates its new output. LSFR_3 is not being clocked.
We build the sum of the output of LFSR_2 and LFSR_3 ("xor")-> sum23
Then the sum23 is XORed with the 1. bit of the plaintext we have to encrypt and this is the first bit of cipher.

If the output of LFSR_1 is 0:

LFSR_2 is not being clocked but stays the same.
LFSR_3 is being clocked and calculates its output.
We build the sum of the output of LFSR_2 and LFSR_3 ("xor")-> sum23
Then the sum23 is XORed with the next bit of the plaintext we have to encrypt and this is the next bit for the cipher...

My question is: I have to decrypt the cipher to the plaintext again.  But I don't know how to do that?

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

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