Cryptographic pseudo-random generation of address subsets Suppose I have devices which broadcast, on an insecure channel, 32-bit addresses.
I want to make these devices untraceable - one way to do so is to allocate for each device a distinct subset of address, for example $X=256$ addresses for each device with no repetitions, and make each device change its address from time to time (to a different number in its subset).
A secure receiver, who knows how the addresses-subsets are separated, could trace the origin device of the address.

However, this would require to store $X$ addresses on each device.

Another way is finding some injective function $f:Z_{2^{32}} \to Z_{2^{32}}$, where the first device will calculate on-the-fly the addresses $f(0), ..., f(X-1)$, the second device will calculate $f(X), ..., f(2X-1)$, etc...
However, if the code of this function falls to the wrong hands, the whole mechanism becomes worthless (I'm talking about physically breaking and reading the code secrets of one of the devices, not only reading its addresses from outside).

A third way is to have a different salt in each device and a CSPRNG executed $X$ times per device - leaving out salts that generate addresses that are "already taken" by previous devices.
In this case, after some time (around $2^{32}/X$ addresses, $2^{32}/{X^2}$ devices), it will become hard to find salts that do not generate "already taken" addresses.

Is there a mechanism that is both memory efficient and secure, i.e. breaking one device won't give too much information about the addresses of other devices (except that they are different from those of the broken device), without loosing too much of the address space (keep generating "devices" easily)?

Thanks

--- EDIT ---

Fourth way:
Similar to the third way, I can create create pairs of $(s_1, l_1), (s_2, l_2), ...$ where $s_i$ are randomly chosen salts and $0 < l_i \leq L$ is the number of times I can execute the CSPRNG on $s_i$ before getting a collision with an address generated by a previous $s_j$ (for $j < i$).

Then all I have to do is to give some $(s_i, l_i)$ pairs to each device so it could generate the amount of addresses I want.
For example, if every $l$ is a powers of 2, I could make devices that have pairs like:
$(s_{i_1}, 128), (s_{i_2}, 64), (s_{i_3}, 32), (s_{i_3}, 16), (s_{i_4}, 8), ...$,
and when I run out of $(s, 128)$ pairs, have devices that have:
$(s_{i_1}, 64), (s_{i_2}, 64), (s_{i_3}, 64), (s_{i_4}, 32), (s_{i_5}, 16), (s_{i_6}, 8), ...$

I am not sure about the average amount of memory I need on each device, but I know that the generated addresses can use much more than $1/256$ of the address space (suggested in the "third way"). Obviously, when it comes to pairs like $(s, 1)$ it would be more efficient to simply store the generated number...

I think there is a fundamental problem with what I'm trying to do. Informally, I am trying to allocate random numbers to each device and "compress" them. The only way to do that is to generate the numbers pseudo-randomly based on a secret, but then other devices must "know" that secret to prevent collisions - i.e. if a device is compromised then the secrets of other devices are lost too.
An asymmetric mechanism is needed - knowing that an address is taken by a different device without knowing the other device's secret. I don't believe it's possible with 32-bit numbers.

It is possible to build a hybrid between your first two solutions, to trade off between their advantages and disadvantages.

Let $E_K : \{0,1\}^{32} \to \{0,1\}^{32}$ be a block cipher with a 32-bit block.  You will select a single global key $K$, that will be stored on every device.  Also, for each device, select a few starting points $s_1,\dots,s_m$, say $m=8$ of them.  These are specific to each device.  The idea is that the device has a pool of $nm$ addresses, namely, the values $E_K(s_1), E_K(s_1+1), \ldots, E_K(s_1+n-1)$, $E_K(s_2),E_K(s_2+1),\dots,E_K(s_2+n-1)$, $\ldots,E_K(s_m+n-1)$.  Each time the device changes its address, it selects a new address from its pool -- either randomly, or cycling through the addresses in the pool, whichever you prefer.  Here you should select $n,m$ so that $nm=X$, so that each device has $X$ different addresses in its pool.

Now you select different start points $s_1,\dots,s_m$ for each device, and select the starting points so the devices' address pools don't overlap.  One approach is to choose each $s_i$ to be a random multiple of $n$, uniformly and independently at random, sampling without replacement (i.e., you discard a starting point if it has been previously selected).  In this way, you can arrange to have up to about $2^{32}/(nm)=2^{32}/X$ devices.

This scheme requires each device to store $m+1$ values, the starting points $s_1,\dots,s_m$ and the global key $K$.  The security you get is pretty decent.  If no device is compromised, this scheme is as good as your first solution (and as good as you can get, assuming 32-bit addresses): it'll take $nm$ or $\approx \sqrt{nm}$ address-changes before a device ever repeats its address (depending upon how the device selects from its pool, either cycling or random selection).  If a device is compromised, not all is lost: you still have some security remaining; in particular, you get security equivalent to a pool of $m$ addresses.

This now lets you tune the parameters to trade off between storage cost vs level of security.  My suggestion would be to pick $m$ as large as you can reasonably afford, given the amount of storage available for this security mechanism.

As fgrieu points out, in this scheme the block cipher must have a 32-bit block size, which is not as common as 64-bit or 128-bit block, but still well studied as part of Format Preserving Encryption, including by Granboulan and Pornin (in proceedings of Fast Software Encryption 2007); Bellare, Ristenpart, Rogaway and Stegers (in proceedings of Selected Areas in Cryptography 2009); Morris, Rogaway, and Stegers (in proceedings of Crypto 2009).  (Paragraph and links copied from fgrieu's comment; my thanks to fgrieu.)


Is RSA vulnerable to possible PRNG + Miller Rabin test weaknesses? Factoring a 2048 bit number is a difficult topic with a well known complexity.

But it seems that p, q, the prime numbers used in RSA (order of magnitude: 10^308) are generated thanks to the probabilistic primality Miller Rabin test. Indeed even a table of primes between 10^307 and  10^308 would be out of reach.

Is RSA vulnerable to the potential specific arithmetic properties (if any) of the primes generated during the pseudo random number generator + Miller Rabin process?

RSA is vulnerable to poor choice of the primes of the modulus, and there are quite a few examples of that: RNG that generates the same output on different calls (see CVE-2008-0166, smartfacts and an example in usenix 2016's best paper); or dubious mathematical shortcut to make the generation faster (see the Roca attack).

It is much less common that a bad implementation of the primality test cause disaster, because a single iteration of a correct implementation of the Miller-Rabin test is actually quite solid when the number generated is random (see FIPS 186-4 appendix F); and accidentally choosing a non-prime would most often be caught on the first use of the RSA key: an RSA encryption/decryption is a Fermat primality test for its factors, and this has excellent chances of catching a composite.


Does the AES-KW (Key Wrap Algorithm) perform authenticated encryption? The RFC for AES-KW doesn't actually mention authentication. It only mentions integrity, where the unwrapping/decryption process should produce an identical IV of A6A6A6A6A6A6A6A6. Is this integrity check effectively performing authentication, or is it possible for a third party to generate a key that will produce the same IV when unwrapped with an arbitrary key-encryption-key?

Yes, it does perform authentication.

AES-KW is essentially a keyed pseudo-random permutation on large blocks, and being a keyed PRP means 2 things:

Observing ciphertext and plaintext pairs gives no knowledge of the key.
Without knowledge of the key, one cannot obtain any knowledge of the plaintext from the ciphertext or vice versa.

Therefore the knowledge of key (thus identity authenticity under the assumption of key secrecy) is a necessary condition for producing ciphertexts that yield recipient expected values (in this case, the IV) when decrypted.

Also, the wrapping algorithm W is unauthenticated and not approved for use in production as noted in NIST-SP-800-38F, and you may be interested in what exactly is key wrapping.


How do I solve this RSA instance for m? How we can solve this equation and get the value of M?

$$8 = M^{13} \mod 33$$

not a computer program, but a mathematical operation.

Factor the modulus, $n$ which was given as 33, to yield $p = 3$ and $q = 11$.

The totient, $\phi$ is $(p - 1)(q - 1) = 20$.

The public exponent, $e$ is given as $13$.

Now compute the private exponent $d$ as the multiplicative inverse of $e \mod \phi$, so
$e^{-1}\mod \phi \equiv 17$.

The cipher text, $c$ is given as 8.

Finally compute the message, $M$ as $c^d \mod n \equiv 2$.

No algorithm has been published for factoring large numbers quickly, so the first step is what makes breaking RSA "computationally infeasible." Fast algorithms are known for all of the other operations.


How does CBC work with read-write volumes? I have read an article about an attack on LUKS in CBC mode and had a look at the WP article about CBC and now I am confused. If I have understood that correctly then changing the plaintext of a block affects all following blocks because every block needs the ciphertext of the previous block to be decrypted. Changing the plaintext ($i$) changes the ciphertext so (in my understanding) you have to rewrite the next block ($i+1$) so that the changed ciphertext of $i$ still leads to the correct plaintext of $i+1$. Rewriting $i+1$ causes the same problem for $i+2$.

This doesn't make sense so obviously I misunderstand something important.

You should read the wikipedia article about disk encryption.

In short: for disk encryption, data is organized in sectors (for instance of size 512 bytes), and data may be encrypted with a chaining mode of operation such as CBC only inside these sectors, using a different initialization vector for each sector.


Parallelized Pollard's Rho algorithm for ECDLP + Jacobian coordinates My implementation of the parallelized Pollard's Rho algorithm is using Jacobian coordinates to avoid the costly inversion operation when performing point addition.

I am wondering if there are any methods to check for distinguished points while in Jacobian form, since switching back to affine coordinates requires an inversion?

The bad news is that projective coordinates do not work with Pollard's Rho like you want it to. Rho needs an unambiguous point representation to find meaningful collisions, and in projective coordinates each point can have up to $p-1$ valid distinct representations.

The good news is that, sticking to affine coordinates, you can avoid most of the cost of the inversions by performing a bunch of them in parallel, and trading $N$ inversions by $1$ inversion plus $3N-3$ multiplications. This is the so-called Montgomery trick (Section 2.5.1), and is the most common approach in ECDLP Rho implementations.


Practical Attack on RSA Currently I am designing an RSA based application, and I am thinking of how long should the key be in order to be secure against attacks. I know that RSA 4096 bit key can be recovered using Sound Pattern attack yet it is not practical. Brute Force is impossible unless if a quantum computer is available with the claimed computation power.  How long shall the RSA key be in order to be secure against practical attacks?

Update: There exist many techniques which are much faster than brute force attack. Actually we can assume that no one can break RSA cryptosystem with brute force attack. number field sieve was used by Aoki and others in Factorization of a 768-bit RSA modulus to factor 768 bit RSA key. In addition, they predict that RSA 1024 will be factorised by 2019.

Also, if a bad random number generator is used two parties might have the same keys! as described in Mining Your Ps and Qs: Detection of
Widespread Weak Keys in Network Devices

What is your recommendation?
Is there any new advancement in factorization? so the key size should always be longer than the factorable key length.
Can I use Microsoft RSA Implementation?

Thank you.

Q: How long shall the RSA key be in order to be secure against practical attacks?

A: Impractically large. This does not imply that RSA is unsafe against practical attacks; only that some of these attacks must be prevented by ways other than increasing the key size.

That's because key size is not a parameter with a major impact on the efficiency of many attacks against RSA, with the exception of factorization of the public modulus. For example, in (Simple) Power Analysis of RSA (without CRT), the secret exponent $d$ is directly recovered from observation of the power trace of one execution of the private-key function, thus any increase in public modulus length making attack impractical also makes usage impractical.

For less severe signal leakage (like in the sound pattern attack linked to in the question), the attack may require a number of executions of the private-key function growing with the key size (all things being equal), perhaps linearly or per some other slow-growing function; but again increasing the key size will make the system impractical before it gets safe.

Q: Is there any new advancement in factorization?

A: Publicly, no experimental progress. The state of the academic art remains close to that when factorizing RSA-768 in late 2009. However there has been claims of breakthrough by the NSA which could be explained by factoring 1024-bit RSA moduli; quoting that Wired article quoting an unnamed former senior intelligence official

  “They made a big breakthrough” (..) “They were thinking that this computing breakthrough was going to give them the ability to crack current public encryption.”

One of the few notable theoretical progress that I'm aware of is: Daniel J. Bernstein and Tanja Lange, Batch NFS, in proceedings of SAC 2014, free on ePrint in revised version.

Independently of NSA breakthrough claims, because both technical and theoretical progress has not stopped, it would be prudent to assume that 1024-bit RSA is vulnerable to factorization these days, if even a small fraction of the funding of the NSA is poured into trying that; see this answer.

Q: What is your recommendation?

A: With respect to public modulus size: French authorities recently vetted 2048-bit RSA good enough for civilian use up to year 2030 at least (rather than year 2020 formerly), and ask for 3072-bit RSA afterwards. When there is incentive (like: efficiency, compatibility, availability, or cost) not to use something wider, or/and good reason to fear side-channel or fault attacks attacks (e.g. in a Smart Card), I find 2048-bit a reasonable choice for many systems.

A: With respect to choice of implementation: know precisely what you trust and why, or delegate that to competent parties that you have reasons to trust. That's what Common Criteria security certification aims at. Microsoft RSA Implementation is not something well defined enough that advice can be given about it.


HMAC - What does "in transit" mean I often read that MAC's provide a proof of authenticity of a payload 'in transit'.

I'm wondering though is there any special definition of "in transit" that would prevent it from being reliable over a long period of time - for example proving the data was not simply corrupted by a storage medium.

if the meaning is 'over the wire where an attacker only has a short amount of time to successfully modify the payload and MAC', then the implication would be that it is unsafe to store the payload and MAC long term to provide authenticity at a later date.

The meaning I'm guessing is 'end to end' authenticity, say between Alice and Bob independent of time.

This may be a silly question that simply boils down to are MACs secure, then that would be dependent on the specific HMAC, GMAC or what ever is used.

In secure transport protocols, the authentication tag (i.e. MAC value) is usually calculated with a session key. This session key is not linked to the data that is send, it is just used to protect the records within the transport protocol. Hence after processing the records, the tag is stripped off to retrieve the actual data that was send. Furthermore, after the session ends the session key gets destroyed - it is often not available at application level.

So although the authentication tag does protect the data while it is "in transit" it doesn't offer any protection afterwards. This is not because the MAC algorithm is not strong enough, it's just that the authentication tag and session key are not available anymore to validate the integrity/authenticity (as explained above). HMAC's are actually one of the most reliable schemes out there.

As example take the various TLS libraries. I don't know any where the TLS records or the session key is passed on to the application layer. TLS always protects the data with an authentication tag regardless.

To protect the data outside the transport protocol it is required to add protection in an application level protocol. For instance it is possible to send enveloped messages using the Cryptographic Message Syntax. For this long term keys are required. It is certainly possible to use a MAC to do add integrity to application level messages for long term storage.

Signatures are more common though. This is because a MAC requires a shared secret; symmetric cryptography is cumbersome when it comes to key management between different parties.

As it is now seems common to add a tl;dr: It's not so much the properties of the MAC rather than how it is used within a protocol that makes it just protect messages in transit.


Does any $x < p$ satisfy the curve equation of X25519? I've been reading about the famous X25519, a montgomery curve from wikipedia  and in that article they say that we do not have to check for point validity. Is it because that any $x < p$ satisfy the curve equation ? Is this possible for  X25519 because it is a Montgomery curve or because it was specifically designed to do so (for the sake of efficiency,  and more possibilities for public keys) by its discoverer Dan Bernstein ? Why every $x < p $ does not satisfy the curve equation for other curves like SECP256k1, where the equations are of the Weierstrass form, $y^2 = x^3 + ax + b
    \mod p  $ ? I would really like to know the mathematical reasons behind it. Thankyou everyone in advance!

If you have an elliptic curve given by the equation $y^2 = f(x) \bmod p$, then for each $x$, either $f(x)$ is a square modulo $p$, and there exists a square root $y$ such that $(x,y)$ and $(x,-y)$ satisfy the curve equation. If $f(x)$ is not a square modulo $p$, then this value $x$ does not correspond to a point on the curve, but to a point on the quadratic twist of the curve.

Therefore knowing only $x$, we know it corresponds to a point on the curve or its quadratic twist. The thing is that many standardized curves have a weak quadratic twist (see this page on SafeCurves so it is mandatory to check the point is on the curve, and if we use only the $x$-coordinate, we still need to check it is not on the quadratic twist to avoid invalid curve attacks.

Dan Bernstein designed X25519 as a Diffie-Hellman function using Curve25519 in its Montgomery form. On this curve, the Montgomery ladder scalar multiplication is efficient and uses only the $x$-coordinate of the points. Then, manipulated points lie on the curve or its quadratic twist which is as secure as the original curve. Then any $x$ is valid, but does not necessarily correspond to a point on the curve.


CMAC Generation : If input payload length is not aligned in 16 bytes, what are the possible side effects? While searching for answers ,I understand that RFC AES-CMAC 4493 is suggested by NIST to overcome if payload is not aligned in 16 bytes.

I would like to know what drawbacks/insecure caused by AES-CMAC if length is not aligned in 16 bytes. Would the generated TAG value is easily tampered?

how and when the One-Key CBC MAC1 (OMAC1) is used? here what is the ONE-KEY stands for?( Normal CMAC Gen/Ver - Same single key is used for Generation and verification).

I hope you mean drawback caused by AES CBC-MAC which is resolved in AES-CMAC.

AES_CBC MAC if used properly with ISO padding technique should not result into a tag collision.

So AES-CBC MAC should look something like this.

In AES-CBC MAC if the last block is not  16 byte aligned (considering AES as PRF) then padding must be done to the last block.
Padding should be done based on ISO (bit padding, using binary one followed by zeros, e.g. $\texttt{100..00}$)
For ISO 1 indicates the start of the padding.
If the block is already 16 byte aligned then a dummy block (with ISO padding)
should be concatenated . After this only the tag should be calculated.

Let's see the collision situation:
last block say m is of 13 bytes. Hence as per ISO padding the block would become  $m\|\texttt{100}$ and then tag will be calculated.
What if there is a block called $m'$ which ends with $\mathtt{100}$ as the real data and if the dummy 16 byte block is not added then tag will be of same as with $m\|\mathtt{100}$.
This means that a collision can be created.

As per security two different data should not result in the same MAC with the same Key. Hence it can become insecure.

To overcome this, there is a solution in AES-CMAC where there is no need to add a dummy block if the it is already block aligned to the PRF (in this case it is AES then 16 bytes aligned).

In AES CMAC there are three keys ($K$,$K_1$ and $K_2$).
$K_1$ and $K_2$ are derived from $K$.
For the subkeys ($K_1$ and $K_2$ ) generation, please see section 2.3 (Subkey Generation Algorithm).

If the last block is not aligned (16 bytes in case AES PRF) then pad the last block as ISO padding . Encrypt it with AES and XOR the output with $K_1$ .
The tag is calculated on the XOR-ed output with the same key $K$.

Please see the image for padded case in AES-CMAC

If the last block is aligned (16 bytes in case AES as PRF) then XOR the output of the block with the $K_2$. The tag is calculated on the XOR-ed output with the same key $K$.

Please see the image for the non padded case.

Note: referenced from Professor Dan Boneh.


C# equivalent of openssl ecparam -name prime256v1 -genkey -noout -out I am having some issues generating a proper private key,I need it to be an  Elliptic Curve private key suitable for use with NIST P-256 which i than need to  convert to Base64-encoded private key in PKCS #8, for some reason when I generate the key and than base64 encode the bytes I end up with a string of 108 characters. but I need it to be in the range of 184 characters. The following is what I am doing with bouncy castle, I am aware that this is more of a crypto section but also just knowing the steps of what it is I need to properly do would be appreciated from a non programming level

       // Curve Cryptography (ECC) key pair.
        DerObjectIdentifier ecParam = new
        DerObjectIdentifier("1.2.840.10045.3.1.7");
        ECKeyPairGenerator keyGen = new ECKeyPairGenerator();
        keyGen.Init(new ECKeyGenerationParameters(ecParam, new
        SecureRandom()));
        AsymmetricCipherKeyPair keyPairServer = keyGen.GenerateKeyPair();

        //Grab private key from key pair
        // for storing.
        PrivateKeyInfo pkInfo =
        PrivateKeyInfoFactory.CreatePrivateKeyInfo(keyPairServer.Private);
        String privateKey = Convert.ToBase64String(pkInfo.GetDerEncoded());

Your question is contradictory and incomplete, as well as being primarily about coding for a particular implementation, which is offtopic and apparently heading (slowly) for closure.

First, the output from openssl ecparam -genkey is NOT PKCS8 format (not either of them); it is the algorithm-specific format from SEC1 (available at http://www.secg.org)(*) including the public point (tagged context[1]) as well as the curve (context[0]). For P256/secp256r1/prime256v1 (in named form) this is 121 bytes in DER if the public point is uncompressed (as is default) and 89 bytes if compressed; in base64 these are 164 and 120 characters and in PEM they are 227 and 182 chars using LF for linebreak or 232 and 186 using CRLF.

Second, the output from that openssl commandline operation, like most others including the ones that are in PKCS8 format, is by default PEM. PEM is NOT just base64 of DER, as you coded; it is base64 of DER PLUS linebreaks PLUS header and trailer, which are important and among other things change the length.

Although I don't have dotnet set up to test, according to the source that BouncyCastle call does produce PKCS8 (unencrypted) 'wrapping' SEC1 (class ECPrivateKeyStructure is in Org.Bouncycastle.Asn1.Sec) with the
curve (which is redundant here) but NOT the public point (see currently line 142, and similarly 126 for ECGOST). That will be 80 bytes DER, 108 chars base64, or 164 or 168 chars PEM. BouncyCastle also has classes to write and read PEM although unencrypted PEM is simple enough you can do it by hand.

If you can specify more exactly what you want, or at least how (and by what software) the result will be used, and thus how it differs from what you have, this will probably be ontopic for StackOverflow or maybe security.SX (which does accept some how-to-code-crypto Qs).

(*) Ironically, secg is currently serving HTTPS with an invalid cert, and so is best accessed HTTP!


What is the link, if any, between Zero Knowledge Proof (ZKP) and Homomorphic encryption? What is the link/relation, if any, between Zero Knowledge Proof (ZKP) and Homomorphic encryption?

There are many.

Homomorphic encryption implies ZK proofs for NP. This is simply because homomorphic encryption implies one-way functions, which imply ZKP for NP.
Homomorphic encryption allows to compile any public-coin zero-knowledge proof into a designated-verifier non-interactive zero-knowledge proof; this was shown in the paper Non-interactive Zero-Knowledge from
Homomorphic Encryption.
Zero-knowledge proofs are not known to imply anything regarding the existence of homomorphic encryption. In fact, only very strong forms of zero-knowledge proofs were very recently shown to imply public-key encryption.
Fully homomorphic encryption can be used to minimize the size of a non-interactive zero-knowledge proof, and reduce it to witness size + polynomial in the security parameter, see this paper.

This is just a sample of the many interplays between the two notions; if you had more specific relations in mind, please clarify.


The protocol of provisioning shared key to multiple devices? I have a bunch of IoT devices which can do ECDH/ECDSA and AES. They all are connected to some server and know its public key. In turn, server knows each public key of the corresponding device. Devices do not know about each other, only their master-server and its public key.

What I want is to get rid of ECDH for most of the time and to let all the devices to securely know about some common key that can be used to broadcast messages using AES and which (optionally) could be switched to a new one after some time.

So, the naive idea is for devices to securely "ask" server for a new AES key and its expiration date every time they get online. Or re-ask if they get decryption error.

Does it sound sane? Or should I consider some other group key establishment protocol?

By securely "ask" I mean some proper way of communicating like noiseprotocol/TLS

This looks likely a classic server-multiple client scenarios, I had the similar situation:
Depend on real application, some of my thought:

For most case, IoT devices does not communicate to server at the same time? so server should be able to setup secure key for each of IoT devices through ECDH.
To have a common key for all devices looks too dangerous, that means as soon as one IoT device is compromised, hacker will be able to hijack all IoT devices..
It is only safe for each IoT device to use a common AES key--when you have physical access to them--for exp, in factory, in Lab, before shipment .. after it is been deployed to field, you must consider the different key for each device. Someone also burn a HW AES key into IoT device ROM, but still that have to be different for each of the IoT device, so one compromise does not jeopardize all devices.
Given ECDH could be too heavy for a IoT devices (usually take few back-forth communication), my suggestion would be to consider once time ECDH when IoT device is been activated, and using Ephemeral ECDH (ECDHE) which does not request regenerated ECC keys.


security against CPA attack? Let $\mathcal{E} = (E,D)$ be a CPA secure cipher.

Let's define $\mathcal{E'} = (E', D')$, where $E'(k,m) = E(k, E(k,m))$.

How can I prove that $\mathcal{E'}$ will be CPA secure if $\mathcal{E}$ is?

My guess: Let $a$ be the CPA advantage of an attacker over $\mathcal{E}$, that is, $\mathrm{CPAadv}[\mathcal{A, E}] = a$.

As $\mathcal{E}$ is CPA secure, then $a$ is negligible, thus $E(k,m)$ provides a negligible advantage to some arbitrary efficient attacker.

Let $E(k,m) = e$. If I repeat the prodecure $E(k,e)$, $E$ should give the attacker another negligible advantage $b$.

Then, the total advantage given by $E(k,E(k,m))$ would be $a+b$, and since they are both negligible, $a+b$ would be negligible and $\mathcal{E'}$ would be secure.

You can prove this by contradiction.
Suppose $\mathcal{E'}$ is not CPA-Secure, meaning there exists an attacker $\mathcal{A}$ who can break this scheme with non negligible probability. Using this attacker, we try to break CPA-Security of $\mathcal{E}$ with non negligible probability as follows:

The adversary $\mathcal{B}$ (for breaking $\mathcal{E}$) outputs two plaintexts $m_0$ and $m_1$.
A bit $b$ is then chosen uniformly at random $b \leftarrow \{0,1\}$ and $\mathcal{B}$ receives the encryption of $m_b$ i.e., $c=E(k,m_b)$.
Based on the definition of CPA indistinguishability experiment (see section 3.5 in Katz-Lindell book), the adversary has still access to the encryption oracle and can query this oracle at the point $c$ receiving $c'=Enc(k,c)$. (Here, we assume that the plaintext and ciphertext space is the same.)
$\mathcal{B}$ emulates the CPA indistinguishability experiment for $\mathcal{A}$ by sending this challenge ciphertext $c'$ to $\mathcal{A}$.
$\mathcal{A}$ outputs a bit $b'$.
Eventually, $\mathcal{B}$ returns the same outbuts bit $b'$ as $\mathcal{A}$.

Now, it is obvious that assuming non-negligible success probability for $\mathcal{A}$, the success probability of $\mathcal{B}$ in breaking $\mathcal{E}$ is non-negligible too.


Does there exist an indistinguishability formal proof obfuscator? A formal proof obfuscator is a mapping $\mathcal{O}$ such that whenever $P$ is a formal proof of a theorem $T$, then $\mathcal{O}(P)$ is a distribution of formal proofs of the same theorem $T$. An indistinguishability formal proof obfuscator is a formal proof obfuscator $\mathcal{O}$ such that whenever $P_{1},P_{2}$ are proofs of of a theorem $T$ the distributions $\mathcal{O}(P_{1}),\mathcal{O}(P_{2})$ are indistinguishable. Does there exist an indistinguishability formal proof obfuscator? Are there any references for an indistinguishability formal proof obfuscator or any formal proof obfuscator in general?

Since you do not give $T$ as an input, the existence of such an $\mathcal{O}$ seems

like it should significant constraints on the is_a_proof_of relation:

For example, if there are proofs P0,P2,P1 and Theorems T0,T1,T2 such that

[for all elements i and j of {0,1,2},  Pi is_a_proof_of Tj  if and only if  i ≠ j ]

then there would have to be a P such that P is a proof of all three of those theorems.

  For the rest of this answer, assume there is a function theor_of_ such that

  for all proofs P and theorems T, if P is a proof of T then  theor_of_(P) = T .

Under that assumption, sure.    For such a function theor_of_, one can

have $\mathcal{O}$ be given by    $\mathcal{O}(P)$  =  lexicographically least proof of theor_of_(P)  .

That $\mathcal{O}$ is in Ptheor_of_[1],NP.

You probably want $\mathcal{O}$ to be efficient, or at least significantly faster than brute force for suitable input lengths, even if NP is hard.  For that requirement, it becomes very significant that

you do not give the security parameter as input
and
you're not relating the lengths of the proofs

.
The distributions thus do not depend on the security parameter, so if they're indistinguishable then they're identical.  Efficiency in particular forces output-length to be not so much longer than input length, so for the resulting distributions to be identical, $\mathcal{O}$ must find a proof which is not so much longer than the shortest proof, regardless of how long its input proof is.

The latter is the much stricter requirement - For example, consider statements of the form "There exists an x such that $\big[\big[$x satisfies $\phi \big]$ or [length(x) = L]$\big]$", and proof systems for which the proofs of such statements are exactly ordered pairs of the statement and such an $x$.

By setting L so that it will be slightly greater than

$\big[\mathcal{O}$'s runtime on proofs of the resulting formula for which $x$ is a satisfying assignment$\big]$ (remember that L is only log(L) bits long) and giving $\mathcal{O}$ a proof with an L-bit $x$, $\mathcal{O}$ must solve $\phi$.

Even for proof systems that are not so insistent on constructiveness, one could try

replacing  length(x) = L  with something else such that $\big[$one also gets a proof but it's

probably hard to find a proof that's not sufficiently longer than assignments to $\phi \big]$.

Even if you [give the security parameter as an input] and [only require indistinguishability against uniform adversaries that must choose equal-length proofs], such an $\mathcal{O}$ for a

similarly-constructive proof system would suffice for inverting candidate one-way functions with probability greater than 1/3  -  Just run it on proofs that give r for statements

"There exists an x such that f(x) is in {$\hspace{.02 in}$y,z}.", where a random one of

of y,z is the target image, the other of them is f(r), and r is chosen

uniformly from strings with length equal to the security parameter.

Thus, if one-way functions exist then for a feasible such $\mathcal{O}$ to exist,

the proof system must not be feasibly constructive.

Now, I'll finally give the positive results:

As warmup, if there is an efficient non-interactive witness-indistinguishable proof system

NIWIP for SAT with deterministic verifier, then for axiomatic systems S such that

a theor_of_ function, as described near the top of this answer, is efficiently computable
and
the proof system includes arithmetic and

[can prove enough about its own provability predicate]
and
there is a poly(k,M)-time algorithm for finding a proof in  S + Con(S)  that

NIWIP with security parameter k is sound for statements of length at most M

then there is an efficient $\mathcal{O}$ that takes as input

the security parameter, in unary
and
a length bound L, in unary
and
a proof in S of a $\Pi_1$ formula

and outputs a proof in  S + Con(S)  of the same $\Pi_1$ formula,

such that the desired indistinguishability will hold when

the security parameters are equal
and
the length bounds are equal
and
the proofs both satisfy the length bound

.
Furthermore, if NIWIP's indistinguishability is perfect,

then $\mathcal{O}$ does not need the security parameter.

(In either case, use NIWIP on the existence of a proof of length at most L, prove the relevant

soundness property of NIWIP to deduce the existence of a proof in S of the $\Pi_1$ formula, and

then use Con(S) and [provable-in-S facts about being provable-in-S] to deduce the $\Pi_1$ formula.)

It's finally time for the full result.  For axiomatic systems S0 such that

a theor_of_ function, as described near the top of this answer, is efficiently computable
and
the proof system includes arithmetic and

[can prove enough about its own provability predicate]

,    with the axiomatic systems  S1,S2,S3,S4,...,S$_{\infty}$  given by

Sn+1 is Sn plus [the schema with one axiom per wff p, where those

axioms are padded (for example, by ANDing with 0=0) to each be longer

than n bits, and otherwise just assert "if p is provable in Sn then p"]
and
S$_{\infty}$  =  S0 + S1 + S2 + S3 + S4 + ...

, if there is $\big[$an efficient non-interactive witness-indistinguishable proof system NIWIP for SAT with deterministic verifier$\big]$ and $\big[$a poly(k,M)-time algorithm for finding a proof in S$_{\infty}$

that NIWIP with security parameter k is sound for statements of length at most M$\big]$,

then then there is an efficient $\mathcal{O}$ that takes as input

the security parameter, in unary
and
a length bound L, in unary
and
a proof in S$_{\infty}$

and outputs a proof, also in S$_{\infty}$, of the same formula,

such that the desired indistinguishability will hold when

the security parameters are equal
and
the length bounds are equal
and
the proofs both satisfy the length bounds

.
As before, if NIWIP's indistinguishability is perfect,

then $\mathcal{O}$ does not need the security parameter.

(In either case, work as follows:    Proofs in S$_{\infty}$ of length at most L cannot use axioms that aren't in SL, so use NIWIP on the existence of a proof in S$_{\infty}$.  From there, prove the relevant soundness property of NIWIP to deduce the existence of a proof in SL of the relevant formula, and then use the relevant axiom from SL+1 to deduce the relevant formula itself.)

I'm not aware of any candidates for that which Shor's algorithm won't break.


Advice in password auto-generation I'm creating a program with key access for a determined term. I've made a code that will generate a key (password) with 16 characters length. The following information is encoded:

initial date 6 characters, ex. 010120;
term up to 3 characters length, ex. 1 or 10 or 365 days;
term length identificatior, ex. 1 or 2 or 3, depending on term number length;
6 randomly generated symbols: lower/uppercase letters and numbers.
These characters are scattered in the password string using some logic (to be decoded by password verification code).

Encoding is simply based on ASCII codes of symbols.

Example of coding letters: a b c d e f = ASCII codes 126 + 127 + 128 + 129 + 130 + 131 = 771 = 7 + 7 + 1 = 15. 15 is the control sum. Thus generating a key my code loops through random codes ASCII until the control sum will be equal 15 - this is the generated letter part of the password. This control sum is after used to verify is the password is correct. Digits for the date are encoded simply by adding a constant value to the ASCII number code (48 to 57) to get a letter.

Here are examples of keys (used another control sum):

3Y6CEecb0MYc1e1c, oPFjeefcAD8m2dmd, bF5bGfdb4dud2ejd, ClEigfdbydcd2ezd

My question is about the "strength" of this password: how easily it could be hacked, or date and term part discovered?

Only randomly generated components matter for passwords/passphrases.

  6 randomly generated symbols: lower/uppercase letters and numbers.

You have 26+26+10 possible characters, so 62.

The entropy of a password is $L\log_{2}N$, where $N$ is the number of possible symbols and $L$ is the number of symbols in the password. So you have $6\log_{2}62=35$ bits of entropy. You want a minimum of 80 to be considered reasonably strong.

This is ridiculously weak. For all practical purposes it's a 6-character alphanumeric password.


Output of using the same key in all 3 boxes of 3DES I am trying to figure this one out: What would be the encrypted output for an input x if the same key K is used in all three boxes of 3DES?

The encryption scheme for 3DES with three different keys, and $k_3 = k_1$, is
$y=ek_3(ek_2(ek_1(x)))$. So, if the key is the same 3 times, then the encrypted output of x would be $y = k(k(k(x))) = ?$

Can someone let me know if what I have done here is correct?

Traditionally, 3DES is configured in a mode called EDE, which means "Encrypt, Decrypt, Encrypt". This means that your encryption operation looks like this: $c = E(D(E(m, k_1), k_2), k_3)$. As it turns out, if all three subkeys are independent, the security of the system is not impacted by the second operation being a decryption.

The reason for this construction is a historic one. When 3DES was being introduced, people wanted a way to fall back to a "legacy" mode which amounted to just plain DES. This is handled through keying modes, of which there are three:

Keying mode 1: All three subkeys are independent (which implies probabilistic inequality, though some implementations may enforce $k_1 \neq k_2 \neq k_3$ explicitly)
Keying mode 2: $k_1$ and $k_2$ are independent, but $k_1 = k_3$.
Keying mode 3: All three subkeys are equal, i.e.e $k_1 = k_2 = k_3$.

In keying mode 1, you get full 3DES with a 168-bit key (3 × 56-bit). In keying mode 2, you get a 112-bit version of 3DES (2 × 56-bit), though this keying mode is less commonly used in practice. In keying mode 3, the first two steps cancel out, leaving you with just DES:

$$\require{cancel}\cancel{a = E(m, k)}$$
$$\cancel{b = D(a, k)}$$
$$c = E(b, k)$$


What alphanumeric string length can be used to guarantee no hash collisions from CRC-64? If I'm hashing alphanumeric strings (chars in the set 0-9, a-z, and A-Z) with a CRC-64 hashing function, how long can my strings be while guaranteeing no hash collisions?

Stated differently: If I have a set of all CRC-64 checksums computed from alphanumeric strings  $0$ to $N$ bytes, how large can $N$ be before I see a collision in the set?

If you have 62 chars you can transform 62 letters ($10+26+26$) in 6 bit number (approx). CRC is guaranteed to be unique mapping (Injective function) as long as input is shorter than output  – you can have at most 10 letters, but not 11 since $62^{10} < 2^{64} < 62^{11}$.

It same goes whit most other hash functions. Lets say that you have hash function that takes only 64 bits and makes 64 bit output and is bijective (like a symmetric cypher). That mean you will not have collision as long as your input is shorter than 64 bits.

If you have mappings from all 64 bit inputs you are 100% sure that each new input will produce collision (because there is no value that is unused)


Hiding the metadata of a one time pad message by encrypting the next key here is an idea that I feel has some big flaw I can't put my finger on.

The scenario is: Alice will go overseas for 5 days and will hopefully retrieve some information and send it back to Bob. She does not want to let anyone listening to know what day she got the information. She is taking with her a one time pad the size of the information, and a hardware random number generator.

The solution I thought of was:

Alice and Bob at home
Alice creates new key(key1) > Bob (key1)

Alice travels to Elbonia
Alice creates new key (key2) XOR key1 > Bob (key2)
Alice creates new key (key3) XOR key2 > Bob (key3)
Alice creates msg + padding (msg) XOR key3 > Bob (msg)
Alice creates new (rand) > Bob (rand)
Alice creates new (rand) > Bob (rand)
Alice travels home

Is this system any better or worse than just sending the encrypted message the day she receives the information, and pure random data on the other days?

Basically that's a one time pad variant where each day a cryptogram is sent, consisting of one between

on days before the actual message is sent, a new random pad replacing the previous random pad (of same size as the original), encrypted by XOR with the current random pad;
on a certain day, the message to be sent (padded to the pad size) encrypted by XOR with the current random pad;
random (of the pad size) on subsequent days.

That allows to send a single message. As is, the receiver has to know in advance or figure out on which day the message was sent, but the later is easy for practical messages.

That works; assuming all random bits generated are perfectly independent and unbiased, it insures the same unconditional security as the one pad, and meets the stated security objective of concealing on which day the information is sent. The quality of the generator is paramount: notice for example that a mere distinguishing attack allows to find on which day the actual message is sent.

Form a practical standpoint, the proposed system has a serious operational drawback compared to sending random on every day the message is not sent: if the cryptogram from any day before the actual message is sent gets lost (or is garbled), the message can not be deciphered (or is garbled).

I do not see any advantage, under the hypothesis that all random bits generated are perfectly independent and unbiased.


How to use GCM mode and associated-data properly I'm currently migrating a project to use the bouncy castle GCM mode.  I understand that using an authenticated mode removes the need for a HMAC, however I want to be sure that I'm using this mode correctly.  When applying a HMAC to ciphertext, I know it's imperative to include in the HMAC'd data any params that could affect the outcome of the decryption (IV, block-size, algorithm name, etc).  The bouncy castle GCM implementation accepts AEAD parameters, one of which is 'Associated Text'.

With authenticated modes, is it correct to:

use encryption params as Associated Text
encrypt cleartext (without params appended)
append params to ciphertext (in cleartext) to facilitate future decryption

I assume this workflow applies to EAX mode as well?

GCM mode already incorporates any params that could affect the outcome of the decryption. The associated authenticated data is there to allow you to rely on context for your decryption.

For example, say you are encrypting some records associated with a user. You may want to include the user's database ID as the authenticated data. If a user found a way to copy another user's data and key into his own record, it would still fail to decrypt since his database ID is not the same.

In general, you would like it to be something that's inherently managed separately from the nonce and ciphertext.


The Generator point and Mod P in ECDSA I've been reading about The discrete logarithm problem as of recent and i decided to try it out on a small portion of numbers myself and i actually came to a  mental gridlock after watching this Video.
In the video, he uses the mod p which is prime to find a specific generator point (which is also prime) that could iterate all possible points(which i know that G is constant throughout the curve. but why use the order of the curve to find a suitable generator point.). And he also mentions that some numbers can't provide all possible digits that can iterate through all possible values.
But what baffles me the most is that the real values like the generator point and the order of the curves  for example secp256k1, secp192ri is/are not prime. And did i mention that all the answers on the discrete logarithm problem online ALL had prime generator points and the order of the curve were also prime. Can i get a breakdown as of what is going on?
Any opinions would be appreciated.

The video (at least, where the question links) illustrates the Baby-step/Giant-step Discrete Logarithm method in the multiplicative group modulo $p$, for prime $p$. That is the set $\{1,2,\ldots,p-2,p-1\}$, under the internal operation multiplication modulo $p$.
This group has essentially nothing to do with an Elliptic Curve group. The principle of Baby-step/Giant-step is the same regardless of group, however the operation analog to multiplication modulo $p$ is extremely different in an Elliptic Curve group.

It is important for security that the order of the group generated by $g$ (that is, the number of distinct values $g^x\bmod p$ can take) is prime, or at least has a large prime factor. When working in the multiplicative group modulo $p$, the order of the full group is $p-1$, and the order of $g$ is some divisor of that. One option is to choose $p$ such that $(p-1)/2$ is prime ($p$ is a so-called safe prime). Now we can take any $g$ except $g=1$ and $g=p-1$, and it's order will be $p-1$ or $(p-1)/2$, which both have a large prime factor $(p-1)/2$.
There is no imperious reason to choose a generator $g$ that is prime. It happens that $2$ and $3$ are popular, and prime; and some people have found satisfactory to choose $g$ prime.
There's even less reason to worry about prime $g$ in ECC groups. In secp256k1, both the $x$ and $y$ coordinates of the generator point are large even integers, thus not prime. What matters is the order of the group generated by $g$. That is noted $n$, and the curve parameters are usually chosen such that $n$ is prime.


Is the key safe if attacker know the encrypted and decrypted message? Given an attacker know both the encrypted message (+ an iv) and the equivalent decrypted message, is it possible for him to craft a new encrypted message that could result in a desired decrypted message? I'm using aes-256-gcm algorithm specifically.

For any proper encryption algorithm, it is safe. The type of vulnerability you are describing is a key recovery attack or a forgery attack involving known plaintext-ciphertext pairs. Only very insecure ciphers are vulnerable to that attack, and strong, modern ones like AES are not.


Are all public-key encryption protocols based on one-way functions? Are there any public-key cryptography protocols which don't rely on one-way (or trapdoor) functions?

RSA and Diffie-Hellman cryptographic protocols both rely on one-way functions (prime factorization and discrete logarithm). Lattice-based cryptography is based on the Shortest Vector Problem which is NP-hard, but is it a one-way function?

Yes, all public-key cryptography based on one-way functions. Every one-way function builds on some hard problem. There is many one-way functions in lattice-based crypto, that based on SVP. For example, NTRU one-way function, LWE one-way function, etc.


Why use Diffie-Hellman key exchange over RSA (or any public-key encryption)? In Diffie-Hellman key agreement between Alice and Bob, Alice computes and sends $g^a$ to Bob, and Bob computes and sends $g^b$ to Alice. Alice then computes $(g^b)^a$, and Bob computes $(g^a)^b$; $g^{ab}$ is their shared key. But this is vulnerable to man-in-the-middle attack.

To overcome the man-in-the-middle, suppose Alice and Bob use RSA signature scheme with their public keys signed by certificate authority. That is, Alice signs $g^a$ and Bob signs $g^b$. But if they're going to use RSA anyway, why even use Diffie-Hellman in the first place? Alice could just generate a random number (to be their shared key), sign it, encrypt it with Bob's public key, and send it to Bob.

Thank you!

Alice could just generate a random number (to be their shared key), sign it, encrypt it with Bob's public key, and send it to Bob.

I, as an eavesdropper, can capture this exchange. In fact, I can capture many of these as I want with other people communicating with Bob. Then, fast forward to some point in the future, if I can compromise Bob's private key, I can now decrypt all those past communications using Bob's compromised private key. Additionally, I can compromise all new secure communications with Bob (since I have his private key, I can do it on the fly, no need to wait).

Compare this with the DH over RSA case, where as you say, Alice and Bob sign the DH elements they transfer to one another. I capture this information as it is transiting the wire and save it. Again, fast forward to some point in the future where I have compromised Bob's private key. What can I do now? Well, I can still MITM subsequent connections as I can masquerade as Bob having his private key. But what about all those prior sessions? There is nothing I can do with those as they have already occurred. There is nothing to decrypt with Bob's private key.

As Ricky pointed out in the comments, this is a property of secure communications knowns as forward secrecy. If long-term private keys have not been compromised at the time of the handshake, going forward even if those private keys do get compromised, our prior sessions are still secure.


Binary neural network encryption quality I am creating a Binary Neural Network that encrypts payloads and I would like to compare it to AES in quality, for example: With BNN you would need XX years to decrypt where with AES would take YY years. How can I do that??
Currently, I have two tests:

A graphic representation that shows how random the payload is, like the image below:

The STS randomness test, which gives me the following numbers:

Are there any other test(s) that I can perform to increase the confidence that the encrypted payload is comparable/best/worst than AES??

What you are trying to do is fundamentally incompatible with cryptographic methods as would be described by this site.  You are looking at an analog input, and analog output, and a lossy compression.  Neural networks by definition have a stochastic behavior because the axon->dendrite interface is inherently unreliable.
There is a body of work in the encryption of analog signals with chaotic oscillators.  I would personally not call it encryption because there is loss, but the brain or machine learning can figure out the output.
The basis of this is Chua's Circuit, and if you look dig around in libraries you can find how these different compression methods were handled in the 90s during the analog to digital channel transistion.


How to find an element of high-order in an RSA group? Is this even possible? The RSA group is not cyclic, so usually you wouldn't find a generator for accessing all group elements.
What happens if you use the RSA group in a scenario where you want that the discrete log problem is difficult. If you cannot find a generator, you want at least find an element with a high order, or?

As for the question "how difficult would it be to solve a random instance of a discrete log problem modulo an RSA modulus", well, it turns out that we can give a fairly solid answer; which is essentially "about as difficult as factoring the modulus".

Here's is a demonstration that the discrete log problem is not drastically easier than factoring the modulus": if you have a procedure that solves a random instance of a DLOG problem in a composite modulus with nontrivial probability, then you have a procedure that factors that composite modulus with nontrivial probability".

This is a well-known observation; one way to arrive at that is "if you can compute DLOGs, you can compute (a multiple of) the order of a random element, and if you can do that, you can factor".

To compute this order using an Oracle that can compute random logs, you take your random element $r$, select a random exponent $k>1$ ($k$ needs to be relatively prime to $(p-1)(q-1)$, making it a large random prime works), and then query your DLOG oracle for discrete log $(r^k)^m = r$; once you know $m$, you also know that $r^{km-1} = 1$; that is, the order of $r$ is a divisor of $km-1$.

Once you have that multiple of an order $x = km-1$, you can then factor $n=pq$ by considering the odd value $y = x/2^j$, and then for random values of $s$ ($r$ works well for an initial guess), consider the sequence $(s^y, s^{2y}, s^{4y}, ..., s^{x})$.  If we see a 1 in the sequence proceeded by a value $z$ other than 1 or $n-1$, then we can factor; the factors are $gcd(n, z-1)$ and $gcd(n, z+1)$.  And, if $r$ was chosen randomly, then with high probability this procedure will find a factorization after a modest number of random $s$ values.

As for the demonstration that the discrete log problem is unlikely to be drastically harder than factoring the modulus, well, that's just the observation that the DLOG problem can be solved by factoring the modulus, and then solving the DLOG problem in the smaller groups modulo $p$ and $q$.  As far as we know, solving the DLOG problem in those smaller groups is considerably easier than factoring, hence the factorization is the main effort.

What does this all mean?  Well, it implies that it's actually safe to pick a random generator; if there is a nontrivial probability that the generator is weak, then there's a nontrivial probability that RSA is weak as well.

Now, does this mean that the extra effort that antosecret suggested is not worth while?  Well, that's actually a matter of opinion; is it better to do a simpler method (with a provably tiny chance of failing); or is it better to do a more complex method (that avoids that specific failure mode)?  Personally, I don't care for unnecessary complexity; you would need to make up your own mind.


Signature Aggregation / Multi-Signature I want to save the space signatures take up in a block of Bitcoin transactions. To simplify it, here is the general transaction structure in a block:

message
public key
signature of the message

There are many transactions in one block and I want to save the space the signature takes by using signature aggregation.
The signatures in one block are under many different public keys and on distinct messages.

I found these interesting articles about it, but I am not sure that they solve my exact problem. Please tell me if the solution to my problem can be found in one of those articles or point me in a new direction or explain to me why this is not possible.

Signature Aggregation
Multi-Signatures in the Plain Public-Key Model
and a General Forking Lemma
Signature aggregation for improved scalability

A multisignature scheme would be a signature scheme where several parties all sign the same message. So this is not what we are looking for.

What we are looking for is called an aggregate signature scheme. In such a scheme, we have $\ell$ distinct users, each with their own public key $\mathsf{pk}_i$. Each of those users has a distinct message $m_i$ that they would like to sign.
The goal of the aggregate signature scheme is to create a single short signature that convinces any verifier that each user $i$ did indeed sign their respective message $m_i$.

To do so, there in general exist five algorithms:

$\mathsf{KGen}(1^n)$: outputs a keypair $(\mathsf{sk_i},\mathsf{pk_i})$.
$\mathsf{Sign}(\mathsf{sk_i},m_i)$: outputs a signature $\sigma_i$.
$\mathsf{Vfy}(\mathsf{pk_i},m_i,\sigma_i)$: outputs $1$ if the signature is valid and $0$ otherwise.
$\mathsf{Agg}((\mathsf{pk_1},\dots,\mathsf{pk_\ell}),(m_1,\dots,m_\ell),(\sigma_1,\dots,\sigma_\ell))$: outputs an aggregate signature $\sigma$.
$\mathsf{AggVfy}((\mathsf{pk_1},\dots,\mathsf{pk_\ell}),(m_1,\dots,m_\ell),\sigma)$: outputs $1$ if the aggregate signature is valid for all messages and $0$ otherwise.

Standard Correctness applies, i.e. for all messages $m_i$ and all key pairs $(\mathsf{sk}_i,\mathsf{pk}_i) \gets \mathsf{KGen}(1^n)$ it holds that
$$\mathsf{Vfy}(\mathsf{pk_i},m_i,\mathsf{Sign}(\mathsf{sk_i},m_i)) = 1$$
and
$$\mathsf{AggVfy}\left((\mathsf{pk_1},\dots,\mathsf{pk_\ell}),(m_1,\dots,m_\ell),\mathsf{Agg}\left(\begin{array}{c}(\mathsf{pk_1},\dots,\mathsf{pk_\ell}),(m_1,\dots,m_\ell),\\(\mathsf{Sign}(\mathsf{sk_1},m_1),\dots,\mathsf{Sign}(\mathsf{sk_\ell},m_\ell)\end{array}\right)\right) = 1$$

In addition to standard unforgeability we also require unforgeability of aggregated signatures. I.e. we require that for all polynomial time adversaries $\mathcal{A}$ there exists a negligible function $\epsilon(n)$ such that
$$\Pr_{(\mathsf{sk}_1,\mathsf{pk}_1) \gets \mathsf{KGen}(1^n)}\left[\mathsf{AggVfy}\left(\begin{array}{c}(\mathsf{pk_1},\dots,\mathsf{pk_\ell}),\\(m_1,\dots,m_\ell),\sigma\end{array}\right)
 :\left(\begin{array}{c}\mathsf{pk}_2,\dots,\mathsf{pk}_\ell,\\m_1,\dotsm_\ell,\sigma\end{array}\right)\gets\mathcal{A}^{\mathsf{Sign}(\mathsf{sk}_1,\cdot)}(\mathsf{pk}_1)\right] \leq \epsilon(n)$$

The first instantiation of such a signature scheme is due to Boneh, Gentry, Lynn, and Shacham in their paper Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. (See specifically Section 3.1.) In their scheme an arbitrary number of signatures can be aggregated in an aggregate signature that consists only of a single group element.

There are many other instantiations of this primitive from different assumptions and with special properties such as the ability to do sequential aggregation.

While some of those schemes have probably been implemented at least benchmarking purposes, I'm not aware of any crypto library implementing aggregate signatures.


When using HMAC, does key encoding matter? Given:

H is a good hash function with block size L.
K is a key of length >= L (recommended by RFC 2104).
Khex and Kbase64 are ASCII encodings of K.

In the HMAC algorithm, is there a good reason to prefer K over the other encodings?

Obviously the HMAC algorithm would consider these distinct keys of different lengths, and keys over length L are hashed, but the way HMAC works I don't see why using K would increase the security of the MAC.

The theoretical problem with using text encoded keys, is that it doesn't necessarily conform with how the keys are assumed to be formatted in security proofs such as this one. If you are using HMAC with an underlying hash function that is still believed to meet the requirements of a cryptographically secure hash function, such as the SHA-2 family of hashes, this shouldn't be a problem. The collision resistance assumption of those hashes should be enough to make your alternative scheme no less secure than conventional HMAC.

However, technically, using keys with special formatting might be a problem e.g. if you are using HMAC-h with a broken underlying hash function h, such as SHA-1 or MD5. Both of these two algorithms are based on simple operations such as bit-wise logical operators, addition modulo $2^{32}$ and shifts and rotates. Considering that both hexadecimal encoding and base64 encoding results in octet strings with the high bit of each octet consistently zero, it wouldn't be completely unrealistic that HMAC-h with $K_{hex}$ or $K_{base64}$ might get broken before (or after) HMAC-h with $K$ selected uniformly from $\{0,1\}^k$.


For RSA, does $p^e=p$ and $q^e=q$ hold? Is it true that $p^e\equiv p \pmod n$ and $q^e\equiv q \pmod n$ for RSA?

Here $n=p\cdot q$, $p$ and $q$ are different prime numbers as required by the RSA system.

I have to find four examples of $w$: $w^e\equiv w \pmod n$ that always hold. My candidates are $p,q,-p,-q$.

It works on examples but I can't prove it.

Is it true that in RSA $p^e\equiv p \pmod n$ and $q^e\equiv q \pmod n$?

No, it is not always true (and, for realistic RSA modulii, it is rarely true).  To take an example, if we have $p = 11$, $q = 17$ and $e = 3$, we have $p^e \equiv 22 \not\equiv p$ and $q^e \equiv 51 \not\equiv q$

  (I have to find four examples of $w$: $w^e\equiv w \pmod n$. My candidates are $p,q,-p,-q$.)

Actually, there are always at least nine examples, however those four aren't it.  I'll give you three for free: 0, 1, and $n-1$, all you need is a fourth one...


Are all homomorphic encryption schemes not CCA secure? Homomorphic encryption is hyped by computer sciences because it offers great potentials. For example you can perform cloud based calculation while nobody gets to know you data.

I am wondering if there is any homomorphic encryption scheme that is CCA secure. Can't you always just choose a random message, encrypt it and link the ciphertext to the challenge? A decryption oracle will decrypt it without hesitation. As the attacker know one plaintext message, he can easily calculate the second one. By doing so he always wins the CCA experiment.

By definition, homomorphic encryption cannot be CCA secure. Therefore when using homomorphic encryption, care must be taken to prevent chosen-ciphertext attacks in the constructed system. Sometimes this requires proving in zero knowledge that certain actions were followed correctly, for example.

If you want to learn a bit more about what can be said about the CCA security of homomorphic encryption, see this paper (On CCA-Secure Somewhat Homomorphic Encryption).


HMAC Key Sizes for MD5, SHA1, SHA224|256|384|512 I'm trying to find an authoritative source for the HMAC Key sizes for each of the hashing algorithms below. Specifically for TLS implementations of HMAC.

I found this table in RFC5246:

MAC       Algorithm    mac_length  mac_key_length
--------  -----------  ----------  --------------
NULL      N/A              0             0
MD5       HMAC-MD5        16            16
SHA       HMAC-SHA1       20            20
SHA256    HMAC-SHA256     32            32

Which lets me populate this information:

MD5 HMAC uses a 128 bit Key and produces 128 bit digest
SHA1 HMAC uses a 160 bit key and produces 160 bit digest
SHA224 HMAC uses a ____ bit key and produces a 256 bit digest, truncated to 224 bits
SHA256 HMAC uses a 256 bit key and produces a 256 bit digest
SHA384 HMAC uses a ____ bit key and produces a 512 bit digest, truncated to 384 bits
SHA512 HMAC uses a ____ bit key and produces a 512 bit digest

But I am unable to find definitive key sizes for SHA224, SHA384, and SHA512.

The HMAC RFC (2104) lists this:

  We denote by B the byte-length of such
  blocks (B=64 for all the above mentioned examples of hash functions),
  and by L the byte-length of hash outputs (L=16 for MD5, L=20 for
  SHA-1).  The authentication key K can be of any length up to B ... the
  minimal recommended length for K is L bytes (as the hash output
  length). See section 3 for more information on keys.

Which implies the Key Size must be at least the hashing algorithm's digest size, and confirms what I've "filled in" above.

I presume, given the above that in all cases the HMAC key size should be at least the length of the digest, which would make the SHA384 HMAC key size a minimum of 384 bits, but I can not seem to find definitive confirmation of the fact.

I'm trying to find an authoritative source for the HMAC Key sizes for each of the hashing algorithms below

Good question.  It turns out that TLS always uses the same length of key as the hash function length (so HMAC-SHA384 would use a 48 byte key).

However, I also can't find any RFC which actually states this.  Neither RFC5246 (which acknowledges HMAC-SHA384 and HMAC-SHA512 as potential MAC algorithms, but doesn't define any ciphersuites that use them) nor RFC5289 (the earliest RFC I can find which actually does define a ciphersuite with HMAC-SHA384 as a MAC algorithm) actually address it.

I suspect that's just something that fell through the cracks; RFC5246 only defined it for those MACs which were actually defined ciphersuites at that time; the author of RFC5289 apparently overlooked the issue.


Rigorous practical pseudorandom generators It is known that existence of pseudorandom generators (PRGs) is equivalent to the existence of one-way functions. In turn, the latter is an open problem.
I am curious if someone developed kind of "practical" PRGs, which are weaker than PRGs in terms of computational indistinguishably to uniform random number generators.
I know of some statistical tests for randomness, but is there any rigorous theory on the subject?
This is a repost from MO, and I intend to remove the original question.

It is worth mentioning that there is a connection in complexity theory often called "Hardness v Pseudorandomness" that makes this question somewhat difficult.
It may not be surprising that given a strong enough PRG, one can derandomize certain randomized algorithms, i.e. trying to prove $P = BPP$ can be done by giving a provably strong enough pseudorandom generator.
What is perhaps surprising is that this is intimately connected to the existence of hard problems in $NP$.
Specifically, if there is a problem in $NP$ that requires exponentially sized circuits, I believe it implies that $P = BPP$ via the construction of an explicit pseudorandom generator.
Moreover, some form of the reverse holds --- being able to derandomize $P$ (via the construction of a provably good PRG of good enough parameters) leads to circuit lower bounds, which is a notoriously hard subject.
Keywords for this are things like "Nisan-Wigderson PRG", or you can look at these notes for some pointers.
I think (but am fuzzy on the details) that one can generalize the above to other circuit classes as well, i.e. the existence of explicit provably secure PRGs against some circuit class is intimately related to circuit lower bounds against some related circuit class.
As in general most circuit lower bounds we can prove are against fairly restricted models of computation, I would expect that the literature on "rigorous PRGs" is restricted to PRGs that are secure against relatively weak forms of computation.
I don't know a great place that summarizes this all --- I do not myself work in the area, but heard about it from someone who does. Perhaps their thesis would be a good reference, but I'll admit that I have not personally read it.


How are the primes used to generate RSA keys? I am confused about how keys in RSA asymmetric encryption are generated and what the implications for open communications are.  Textbooks say the one-way function is merely two primes (with some critical constraints) -- so how do the two primes generated get turned into keys?

Does this mean that having a public key is simply having one of the primes in a translated or equivalent form?  For example, if I were to encrypt a message with someone else's public key and the one-way function could be broken by a third party, then could they decrypt the message with a key generated by the other prime?  Does the other prime have to go through some special process to become a key?

To go further, if the encrypted message was posted in a public forum or sniffed off of a wireless network, etc. (and again, the one-way function was broken by a mysterious third party), does that mean the message could be decrypted by the third party?  Would it matter which prime was used?  What i am wondering is what is the process whereby the primes behind the one-way function are converted into keys and is that process the same regardless of encryption used?

Textbooks say the one-way function is merely two primes...

Yes, that's the key part.

It turns out that if you have a number that's a product of two large primes, deducing which primes factor that number is quite difficult.

So, what we understand from this is that if you have $n = pq$, and you know $p$ and $q$, you can generate $n$, but if you have only $n$, it is hard to generate $p$ and $q$.

These are not keys by and of themselves - they're parts of a process used to find a key. Specifically, a number $e$ is chosen and then you need to find $de = 1 \mod (p-1)(q-1)$. I've covered the mathematics in detail here, but the essential part to understand is that it is difficult to compute $p-1$ or $q-1$ without $p$ and $q$, which you don't have if you have only $n$. Thus, if you know $e$, you have no way to get to $d$ (it's important to understand it isn't theoretically impossible. It's just very, very hard practically).

$e$ and $d$ form the key - $e$ is chosen and $d$ is usually computed, although not always by the mechanism I described.

  ...if ... the one-way function could be broken by a third party, then could they decrypt the message with a key generated by the other prime?

Yes. The message wouldn't be generated by another prime in the case of RSA, but if they could somehow undo the one-way function, then the cryptosystem is broken and all your messages would be readable.

  Would it matter which prime was used?

It does not matter. They just need to be big! At one time, the choice of prime did matter, for resistance against  Pollard's p-1. However, it is now thought that for more advanced methods this is not the case.

For Textbook RSA you can actually interchange the keys $d$ and $e$, which makes RSA a trapdoor permutation, however, in this case $d$ the product of two primes is still the private component, even though it is used in the "role" of encryption.  If things are done properly using "production quality" crypto like PKCS# 2.2 then the keys are not interchangeable as the functions for encryption and signatures are different.

  What i am wondering is what is the process whereby the primes behind the one-way function are converted into keys and is that process the same regardless of encryption used?

The $de = 1 \mod (p-1)(q-1)$ process is not the only way to relate $d$ to $e$. You can also use $\lambda(n)$, the Carmichael function, which is what happens in PKCS#1.

Other public key systems have different conversion functions, not all of which rely on the use of prime number factorisation. Common examples are the discrete logarithm problem and point multiplication over elliptic curves.


Can Trivium be used as a PRF? The Trivium encryption algorithm has two inputs, key and IV, both of which are 80 bits long. Let's call it Trivium(key, IV) → keystream. My question is whether doing Trivium(key, input) and taking the first 80 bit of keystream would result in a secure PRF.

I have found another way to create a PRF from a stream cipher, but that seems to be for stream ciphers that do not have an IV input, so such a complex construction might not be needed for one that does. Based on reading the Trivium algorithm description paper and the Trivium design paper I feel like my construction should be secure but I have no idea how to go around proving it.

This question was spurred by wondering whether I could implement authenticated encryption using only Trivium as a primitive. If I could turn it into a PRF, as far as I understand I could construct something similar to CBC-MAC from it. (Of course this doesn't make much sense to because rekeying the cipher, which you'd need to do for every 8 bytes, is quite slow.)

To attempt such a proof you need a definition of what security properties an IV-based stream cipher is supposed to provide.  For example, like this (very informally):

A nonce-based cipher is secure if and only if its encryptions are indistinguishable from random bitstrings of the same length to a nonce-respecting adversary that's allowed to carry out a chosen-plaintext attack.

The "nonce-respecting" bit is important, because one of the key assumptions in a PRF is that it's supposed to be secure against adversarially-chosen inputs, and the inclusion of "nonce-respecting" in such a definition is to give the adversary as much control over nonces as we can get away with.  (Note not all ciphers meet this standard—e.g., CBC-mode encryption doesn't, because it requires random nonces. Evaluating whether Trivium meets this standard is a whole 'nother topic.)

So if encrypting message $p$ with key $k$ and nonce $n$ is notated as $Enc^n_k(p)$,
then your proposed PRF construction would be:

$$
PRF_k(m) = Enc^m_k(0^{80})
$$

...where $0^{80}$ is the 80-bit all-zero string.  And what you want to prove is that, given a secret, random choice of $k$, if an attacker who can choose messages $m$ could distinguish your PRF apart from a random function, then they could break the underlying nonce-based cipher.

In this case, that follows by observing that if there was such a chosen-message attack they could mount against the PRF, it would imply the existence a corresponding attack on the cipher by querying for the encryption of the same plaintext $0^{80}$ repeatedly but with different, adversarially-controlled nonces.


$\mathrm{Hash}(A\|B)$ where $B$ is known, $A$ is unknown. Would knowing $\mathrm{Hash}(A\|C)$ as well as $C$, speed up a brute force search for $A$ Let's say $\mathrm{Hash}(A\|B)$ is a hash of two concatenated strings, $A$ and $B$.
Suppose I am trying to figure out $A$ from $\mathrm{Hash}(A\|B)$, I know $B$ but not $A$, I want to brute force to find $A$. Let's ignore practical reality for a moment.
If I also know $\mathrm{Hash}(A\|C)$, $\mathrm{Hash}(A\|D)$ etc, as well as $C$ and $D$ etc. can I use this info to reduce the time required in the brute force search?

The answer depends on your definition of a hash function.
In general hash functions don't guarantee, that they hide their input.
A general hash function gives you three properties:

preimage resistance (given $y = H(x)$ it is hard to find $x^*$ such that $H(x^*) = H(x)$)
second preimage resistance (given $y = H(x)$ it is hard to find $x^*$ such that $H(x^*) = H(x)$ and $x^* \neq x$)
collision resistance (it is hard to find $x_1$ and $x_2$ such that $x_1 \neq x_2$ and $H(x_1) = H(x_2)$)

None of these properties guarantee that the hash function doesn't reveal part of the input - i.e. there are hash functions that reveal $A$.
However, in practice you typically model hash functions as random oracles - for any input, the function yields a randomly chosen output.
In this case it is easy to show that it is hard to find $A$.
You might also want to take a look at length extension attacks, which are a way many hash functions deviate from a random oracle. However, these won't help you in finding $A$, they will however help you in finding (roughly) $H(A \| B \| C)$, given $H(A \| B)$ (without knowing $A$ or $B$).


What is the algorithm behind PasswordDeriveBytes? Microsoft has created an implementation of PBKDF1 in the PasswordDeriveBytes class. It can however generate more bytes than PBKDF1, which is limited to the number of bytes generated by the underlying hash function. How is this proprietary extension of Microsoft defined?

The password P in the Microsoft implementation is first encoded using UTF-8. The iteration count c defaults to the value 100, and the hash algorithm Hash to SHA-1.

The output is identical to PBKDF1 up to the maximum output size of PBKDF1, which is the output size of the hash. After that the first-to-last hash is prefixed with a counter (as a string containing a decimal number encoded using ASCII) and hashed again to produce the output. If GetBytes is called multiple times it will just return the next output bytes from the stream.

Note that this description does not describe the broken implementation that Microsoft shipped with earlier Windows operating systems. Those contained a bug which could result in repetition in the output of the GetBytes method if it was called two or more times.

The following is a more formal description of the algorithm. It extends the definition of PBKDF1 in RFC 2898, section 5.1.

PBKDF1_MS (P, S, c, dkLen)

   Options:        Hash       underlying hash function

   Input:          P          password, an octet string
                   S          salt, an eight-octet string
                   c          iteration count, a positive integer
                   dkLen      intended length in octets of derived key,
                              a positive integer, bounded to 100 times
                              the output size of Hash

   Output:         DK         derived key, a dkLen-octet string

   Steps:

      1. If dkLen > 100 * Hash output
         "derived key too long" and stop.

      2. Apply the underlying hash function Hash for c iterations to the
         concatenation of the password P and the salt S,
         apply the Microsoft extension by hashing the concatenation of
         an encoded counter and the output of the hash produced for
         iteration c - 1, then extract the first dkLen octets to produce
         a derived key DK:

                   T_1 = Hash (P || S) ,
                   T_2 = Hash (T_1) ,
                   ...
                   T_c = Hash (T_{c-1}) ,
                   R_1 = T_c ,
                   R_2 = Hash (Ctr(1) || T_{c-1}) ,
                   ...
                   R_n = Hash (Ctr(n-1) || T_{c-1}) ,
                   R = R_1 || R_2 || ... || R_n
                   DK = R<0..dkLen-1>

      3. Output the derived key DK.

    The Ctr function converts the given number to a decimal
    representation in ASCII.

Original Mono implementation in C# here. Java port here.

You are strongly encouraged to use the RFC2898DeriveBytes instead, which implements PBKDF2.

If output is required of PBKDF2 that extends beyond the output size of the underlying hash then it is recommended to use a Key Based Key Derivation Function such as HKDF. If you don't have an implementation of that, then simply hash the output and a statically sized identifier to create a derived key SHA-256(master | identifier) and take as many bytes from the left as needed.


Correct use of Fisher-Yates for subsequent selections We all know Fisher-Yates takes an array and shuffles it as per the output of a PRNG.

My question is in relation to what would be the "correct" implementation to select multiple sets (e.g. n sets of k lottery numbers).  Is the answer :

Re-initialise array to default state, shuffle and pick ; or
Assuming the array is long enough, continue picking along array; or
Re-shuffle already shuffled array and pick; or
It does't make any difference as long as Fisher-Yates and PRNG are correctly implemented.

At the moment, I'm leaning towards number four. But then I know that "crypto is hard" and that I am merely a learning beginner when it comes to cryptography!

Let me start by trying to rephrase your question in more precise terms.  (Please let me know if this rephrasing doesn't match what you intended to ask.)

Let $\textsf{random}$ be a (pseudo)random number generator that, given a positive integer $n$, returns a random integer uniformly sampled from the set $\{0, 1, 2, \dots, n-1\}$.  I assume that the output of this generator is computationally indistinguishable from that of a true source of independent uniformly distributed random numbers.  (Constructing such a generator is the only cryptographically challenging part here.  Everything else is just combinatorics.)

Let me introduce the following helper procedure, which essentially performs one step of the Fisher–Yates shuffle:

  $\text{procedure }\textsf{rand_swap}(A, n, i): \\
\quad j \leftarrow i + \textsf{random}(n-i); \\
\quad (A_i, A_j) \leftarrow (A_j, A_i).
$

That is, given an array $A = (A_0, A_1, A_2, \dots, A_{n-1})$ of (at least) $n$ elements, and a base index $0 \le i < n$ into this array, $\textsf{rand_swap}(A,n,i)$ picks a random second index $i \le j < n$ and swaps the array elements $A_i$ and $A_j$ (which might be the same, if $j = i$).

Using this helper function, the Fisher–Yates shuffle for an $n$-element array $A$ can be implemented as:

  $\text{procedure }\textsf{shuffle}(A, n): \\
\quad \text{for each } i \text{ from } 0 \text{ to } n-1: \\
\quad\quad \textsf{rand_swap}(A, n, i).
$

Also, the same algorithm can be used to implement a partial shuffle:

  $\text{procedure }\textsf{partial_shuffle}(A, n, k): \\
\quad \text{for each } i \text{ from } 0 \text{ to } k-1: \\
\quad\quad \textsf{rand_swap}(A, n, i).
$

After such a partial shuffle, the sub-array $A^{(k)} = (A_0, A_1, A_2, \dots, A_{k-1})$ contains a randomly shuffled uniform sample of $k$ values drawn without replacement from the original array $A$.

Now, we finally get to your question.  Specifically, as I understand it, you wish to repeatedly draw a random sample of $k \le n$ elements from an $n$-element array $A$, and ask which of the following methods will do:

Method 1:

For each sample, initialize $B$ as a copy of the array $A$, call $\textsf{partial_shuffle}(B,n,k)$ and let the sample be the first $k$ elements of $B$.

Method 2:

Let $s$ be the total number of elements sampled so far.  For each new $k$-element sample, while $s + k \le n$, run the following continued partial shuffle:

  $\text{for each } i \text{ from } s \text{ to } s+k-1: \\
\quad \textsf{rand_swap}(A, n, i).
$

and let $(A_s, A_{s+1}, \dots, A_{s+k-1})$ be the sample.  After sampling, increment $s$ by $k$.

Method 3:

Same as method 1, except that we repeatedly (partially) shuffle the same array instead of reinitializing it every time.  That is, for each sample, call $\textsf{partial_shuffle}(A,n,k)$ and let the sample be the first $k$ elements of $A$, retaining the shuffled array $A$ for the next iteration.

The answer is that, as long as our pseudorandom number generator is indeed indistinguishable from a truly random source of uniform independent random integers, methods 1 and 3 are equivalent.  They both generate a sequence of independent random $k$-element samples from the original array, where the elements within each sample are drawn without replacement, but where different samples are fully independent.

This equivalence follows from the observation that, regardless of the initial order of the array $A$, after each call to $\textsf{rand_swap}(A,n,i)$ within $\textsf{partial_shuffle}$, $A_i$ will be uniformly sampled from among the elements of $A$ not already chosen during earlier iterations.

(If the pseudorandom number generator is not perfect, method 3 may be somewhat better at disguising some of its flaws, especially if a full shuffle is used instead of a partial one.  This is because retaining the state of the array $A$ between iterations effectively maintains a large partially hidden state that carries forward some of the randomness from previous shuffles.  This is the main reason why e.g. physically shuffling a previously used deck of playing cards often yields adequately random-looking results after only a few iterations, whereas a new or deliberately sorted deck of cards needs to be much more thoroughly shuffled before it loses all traces of its original order.)

Method 2, however, does something very different: in effect, it draws individual random elements from the original array without replacement, returning these in blocks of $k$ elements.  In particular, if a given element appears in one $k$-element sample, it cannot appear in any other sample drawn from the same array using this method.

Of course, if the array size $n$ is very large compared to the total number of elements sampled from it (squared, due to the birthday paradox), then the probability of ever seeing the same element twice even with methods 1 or 3 is negligible, and so all the methods are effectively indistinguishable.  But in that case, you might as well not bother with shuffling at all, but simply pick random elements from the original array with replacement, since that will also yield only a negligible chance of ever seeing the same element twice.


Has any alternative to RSA and Discrete Logarithm been standardized for deployment? Suppose RSA and Discrete Logarithm over any group (including elliptic curves) gets broken what other schemes we have for DEPLOYMENT IMMEDIATELY do we have to rescue the internet from collapse?

So there is no other alternative and pretty much the internet is dead?

I see a lot of alternatives such as SVP based, code based alternatives floating around. Have any of these been standardized?

Since you say

  to rescue the internet

I presume you are specifically referring to TLS. With a quick look at the supported Key Agreement Schemes in TLS 1.3, the ongoing draft of TLS, it is clear that all the Key Agreement Schemes are based upon the generalized Discrete Logarithm problem or Integer Factorization. Both of these are broken by Shor's algorithm on Quantum Computers, in the event that the physical constraints limiting the construction of such high bit quantum computers are solved.

However, there are numerous asymmetric cryptosystems that exist with no known efficient quantum algorithm. As you noted, there are multiple based upon the Shortest Vector Problem. In addition there are other systems, such as the Anshel-Anshel Goldfeld Key Exchange, which is based on the difficulty of the conjugation problem on braid groups. There is no known efficient algorithm to solve this.

There are standardizations for several post quantum systems, though they are not slated for inclusion in TLS. The lattice based ones have standardizations, but new variants are continually being proposed with different properties. There are standardizations for the code based schemes.


How to use a stream cipher to sign a message? Are there known constructions which allow to sign a message M
(let's say it will be sent as clear text) using a stream cipher C
and a symmetric secret key K?
So, we have M, C, K and we want to send M|S
where S = SIGN(C,K,M) and | is the concatenation operator.

Many caveats: I'm not qualified to write this answer, but hopefully other folks can correct my mistakes. Outside of NaCl's crypto_box and crypto_secretbox constructions, there are a lot of ways to misuse a polynomial MAC. That might be why Thomas Ptacek specifically recommends against them. The standard way to sign a message using a symmetric key is HMAC, and this question seems like kind of an "assuming I'm forced to used a stream cipher instead of a hash for some reason" thought experiment.

That said.

Poly1305 is the authenticator in NaCl, and it's built with a stream cipher. First it feeds your message into a big polynomial, to give a checksum. The coefficients of the polynomial are derived from the bytes of your message, and the value of x in the polynomial comes from half of your secret key. Then it encrypts that checksum, using the other half of your secret key along with a nonce. The cipher for encrypting the checksum can be anything; it was AES in the original paper and it's XSalsa20 in the NaCl implementation. You need the cipher because the checksum by itself can leak the x that generated it.

One important difference between a polynomial MAC and a hash, is that it's easy to find collisions in the polynomial. If you know x you can find its multiplicative inverse, and then you can mix that into a message to control the exact checksum you end up with. A polynomial MAC doesn't uniquely determine its input like a good cryptographic hash does.

Another important difference is that the polynomial MAC relies on a unique nonce (for the cipher) to keep its key secret, which means nonce reuse is extra specially terrible.


Any point in waiting for the SHA-3 standard? The Wikipedia article on SHA-3 says that Keccak has been chosen but the standard hasn't been issued. Does this matter?

That is, can we just assume it's going to be as specified by the submitters (specifically for SHA-3-256 it's the Keccak-f-1600 permutation, in a sponge construction with r=1088 and c=512 and the pad10*1 rule)? Or might NIST wind up tweaking something, meaning we might have to re-hash a bunch of things if we made this assumption -- which, depending on application, could be inconvenient.

(EDIT: of course, waiting is also inconvenient, thus there is a risk-benefit question here -- again, depending on application.)

From John Kelsey on the NIST mailing list for SHA-3 (http://cio.nist.gov/esd/emaildir/lists/hash-forum/msg02656.html if you are on it — it's password-protected):

a.  We plan to allow the collision and preimage resistance to be the same for SHA3, since that fits with the notion of a single security level, and since that will substantially improve hashing performance.  That is, for a security level of 256 bits, we can accept a capacity of 512 bits, representing both collision and preimage attacks of $2 ^ {256}$ work.
b.  We plan to allow the variable-length feature of Keccak by default, since it seems like such a useful feature.
c.  We are considering whether it makes sense to have many different capacities or only one or two.

So short answer, they do seem set to lower the required capacity from the initial proposal so it isn't as dog slow in software, but haven't figured out what the exact settings will be.


Is streaming API to ChaCha20-Poly1305 possible or recommended against? None of the implementations of ChaCha20-Poly1305 AEAD scheme I've seen so far provide a streaming API. Instead, ChaCha20-Poly1305 is presented as an inseparable combination, closely adhering to the pseudocode from the section 2.8 of "ChaCha20 and Poly1305 for IETF Protocols", which requires the plaintext message to be fully loaded into memory. I would prefer to avoid that in case the input becomes very large (but still finite and with a known size). (I know I could split the message up, but I want to avoid that, too)

I'm starting to wonder if it's at all possible to provide a streaming API to that scheme? If not, why?

This is not specific to this construction, but generally, you want to split the stream in smaller chunks, that are individually encrypted and authenticated.

If the encrypted stream doesn't have a valid authentication tag, this is not something you want to discover at the very end, after having decrypted terabytes of data.

Some precautions have to be taken when splitting a stream into chunks. Namely, you need to make sure that chunks haven't been reordered, removed, duplicated and you need a way to verify that the last chunk you read was meant to be the end of the stream.

The encrypting a sequence or a set of dependent messages page in the libsodium documentation provides some guidance for this, as well as a streaming API using Chacha20-Poly1305.


X3DH protocol - What are One-time prekeys for? I'm reading about Signal Protocol and this protocol uses the X3DH Protocol to establish a shared secret key between the two parties but I couldn't understand why we use one-time prekeys in the flow. This keys are optional and if there is any in the server, in the first message between Bob and Alice, an extra Diffie-Hellman is calculate between this prekey and ephemeral key. What is the advantage of using One-time Prekeys?

The short answer is ‘for forward secrecy’, but that glib term obscures the meaning of the property we hope for.

Suppose Alice sends a message to Bob.  If Alice and Bob both erase the message, what is the time at which all key material that can ever decrypt a transcript of network packets on the wire is erased?

Without prekeys, the following are all the sets of keys that can decrypt the wire transcript:

Alice's long-term identity key $\mathit{IK}_\mathrm A$ and Alice's ephemeral key $\mathit{EK}_\mathrm A$.
Bob's long-term identity key $\mathit{IK}_\mathrm B$ and Bob's long-term signed prekey $\mathit{SPK}_\mathrm B$.

While Alice will erase her ephemeral key immediately, Bob is intended to never erase his long-term identity key—at least, as long he wants to maintain his identity—and to rotate his long-term signed prekey only occasionally so that delayed messages can get through.  Thus, a set of keys that can decrypt the wire transcript can be found on Bob's device long after the message has arrived.

With prekeys, the following are all the sets of keys that can decrypt the wire transcript:

Alice's long-term identity key $\mathit{IK}_\mathrm A$ and Alice's ephemeral key $\mathit{EK}_\mathrm A$.
Bob's long-term identity key $\mathit{IK}_\mathrm B$, Bob's long-term signed prekey $\mathit{SPK}_\mathrm B$, and Bob's one-time prekey $\mathit{OPK}_\mathrm B$.

Alice will again erase her ephemeral key immediately.  Bob won't immediately erase anything, because he might be offline—this is an asynchronous protocol.  But as soon as he receives the message, he will erase his one-time prekey.  Thus, as soon as Bob has processed the message, all sets of keys that can decrypt the wire transcript will be erased.

Of course, Alice or Bob might keep a copy of the message on their respective devices for all eternity.  But one-time prekeys guarantee that they have the option to erase messages without leaving targets on their devices for retroactive decryption of wire transcripts.


Including a "purpose" designation in a digital signature A signature of some data can mean many different things, such as: This is a message I sent, this is a certificate I validated,... So I was surprised that common signing schemes don't include a "purpose" parameter as part of the signature. In particular I didn't find such a parameter in the schemes from PKCS#1.
Other methods such as PBKDF2 include a way to include a purpose designation that prevents interactions between different applications. In the case of PBKDF2 the purpose is simply concatenated with the salt.

Why is there no such purpose designation of a signature?
This would make it possible to use a single private key for multiple purposes, as long as the same signature scheme (such as RSASSA-PSS) is used in all of them. It would also help if a key is reused for different purposes accidentally.

Are there any existing workarounds?
This was one of the first things I ran into when looking at digital signatures, so I'd expect other people to have had the same problem. I'd prefer reusing an existing scheme here, instead of inventing my own.

What kind of workaround would be possible?
My first instinct is to sign the result of HMAC(message, purpose) and make sure this is the only kind of data ever signed. Would this be secure?

BTW: I'm talking about a signature-only key used with a single signature scheme here, since I know that it's bad to use a single key with different schemes or for encryption+signature.

A signature algorithm operates over a sequence of bits -- any sequence of bits. The meaning you may want to attach to these bits is totally none of the business of the signature algorithm. It is supposed to be handled at some other level.

Basically you want to attach some meta-data to the signed object, and have that meta-data signed as well. The usual solution is to compute the signature over a structure which encodes the meta-data and contains the target message as well. See, for instance, the CMS standard. When a "document" is signed, it is wrapped in a SignedData structure which contains "attributes", e.g. a "Content Type". The signature is computed over an encoding of (some of) the attributes, one of them containing a hash of the document itself.