Prime factors of non-random keys I have been working on a challenge i found on the internet. It is as follows:

  You've stumbled onto a significant vulnerability in a commonly used cryptographic library. It turns out that the random number generator it uses frequently produces the same primes when it is generating keys.

  Exploit this knowledge to factor the (hexadecimal) keys below, and enter your answer as the last six digits of the largest factor you find (in decimal).

  Key 1: 1c7bb1ae67670f7e6769b515c174414278e16c27e95b43a789099a1c7d55c717b2f0a0442a7d49503ee09552588ed9bb6eda4af738a02fb31576d78ff72b2499b347e49fef1028182f158182a0ba504902996ea161311fe62b86e6ccb02a9307d932f7fa94cde410619927677f94c571ea39c7f4105fae00415dd7d

  Key 2:
   2710e45014ed7d2550aac9887cc18b6858b978c2409e86f80bad4b59ebcbd90ed18790fc56f53ffabc0e4a021da2e906072404a8b3c5555f64f279a21ebb60655e4d61f4a18be9ad389d8ff05b994bb4c194d8803537ac6cd9f708e0dd12d1857554e41c9cbef98f61c5751b796e5b37d338f5d9b3ec3202b37a32f

These seem to be common RSA 1024-bit keys.

My approach to the problem was to implement Pollard's rho algorithm to find factors, then once a factor is found, try dividing the decimal form of the keys by that factor until it is not divisible anymore. Iterate.

Now, i used Pollard's rho and tried to divide until the key is not divided anymore because of the information the problem gave: the keys are not completely random.

But here comes the question: assuming the algorithm generates two primes and multiplies them to get a co-prime, which is the key, the low randomness doesn't help much, does it? I mean, even if both keys share a common factor, finding it the first time would take the regular-impractical-exponential time.

That seems to be the case, as my Python algorithm is running for about 5 hours now and has not found any factor to the second key, which i decided to start with.

As it is a challenge, i assume there is a practical way of finding the answer.
So what im i doing wrong? Is just the algorithm choice wrong, as Pollard's rho is intended mainly for integer with small factors? Is my assumption that i can only use the lack of randomness after i find the first of the four factor, to then try to break the other key with the same factor, wrong?

I would like if someone could just point me in right direction, instead of just giving the answer. Thank you.

In such terms, I suppose you should to find GCD of two numbers Key1 and Key2. It seems that with big probability it will give to you one of the prime number which was generated by compromised generator.
Pollard`s method is very hard, and I doubt, that you can successfully apply it in the case.


eavesdropping on sha 256 consist of two entries one is public is secure If i need to use symmetric encryption(AES), sending the same message for many times with the same password and initial value is absolutely not secure(i don't use Public key exchange ((in first approach)'PKI,CA, etc') i will use Certificateless.

So if i used sha-256 to hash the password with public value(the current date and hour), then used the hashed value as the password

can the attacker retrive the original value of the password from the hash(he also kmow the current date and time)

The reason for asking this question:
Anew a pproch called (Certificateless cryptography),
Certificateless_cryptography

Certificate-Less_Authenticated

The step of trusting KGC server or trusted center(TC), is using pre definied password (known for only user and the server)encrypt the id, so the server decrypt the password and identify the ID and generate a partial private key back(encrypt it with the password)

if the user for any reason repeate the process so it's the same message (user id) same password(PKDF used)

It is proposed to use $\operatorname{SHA-256}(\mathsf{horodate}\|\mathsf{password})$ as a key of AES or/and Initial Value (the lack of unique IV is stated as the motivating context).

That's a very poor idea. If the password is worth its name and is low-entropy (as most passwords are, and increasingly so since the bar for low-entropy is raising per some variant of Moore's law), then indeed the attacker can retrieve the original value of the password from the hash and time-stamp.

A general problem is ignoring the

First rule of modern crypto: don't roll your own

Ignoring that rule is a tried and tested recipe for disaster (and making a question rejected as off-topic on CSE, but I won't raise that further).

More specifically, it is ignored the

First rule of passwords: they must undergo entropy streching

Not knowing why entropy stretching is needed when turning password into key, that irreversible entropy stretching (going under the name of Password-Based Key Derivation Function) is needed for password storage, and that the first hit for PBKDF is outdated, is a sure indication that one should either learn, or leave the problem at hand to someone more knowledgeable, including for applying the first rule of crypto (commercial products that get the first rule of passwords wrong are legion, and recognizing the good from the ugly requires understanding of the issues and the products).

Even more specifically, if it is performed as planned, it will be easy to mount a password search. Yes, that thing in the movies, except one can find characters one after the other only in the most strikingly incompetent implementations of the first rule of passwords (like those vulnerable to timing attack).

Here, the regular breed of brute force password search will be needed: plausible passwords are tried (roughly from most probable to least, possibly in parallel), and for each

the disastrous substitute of a PBKDF $\operatorname{SHA-256}(\mathsf{horodate}\|\mathsf{password})$ is applied ($\mathsf{horodate}$ is assumed known, and since regular decryption needs it, that's reasonable);
decryption of some ciphertext(s) is attempted with that; if a direct error occurs (like incorrect padding), that password is rejected;
the resulting plaintext is submitted to more plausibility test(s); the most commons are:

starting with a magic number appropriate to the context;
being sharply rejected as uniformly random octets by a chi-squared test.

That will tell when the attack has reached the right password, which will then allow decryption of all ciphertext encrypted under that password (and perhaps access to unrelated online accounts of the person using that password).

There are other lesser issues in the proposed solution:

Usually, the IVs are in clear at start of ciphertext; that alleviates the need for steps 2 and 3 in brute force password search.
If AES-256 is used, SHA-256 is not wide enough to derive key and IV; using a fixed IV with a message-unique key dents the theoretical security.
There is no mentioned effort to insure message integrity, which often is more important than confidentiality; see first rule of modern crypto.

Note: this answer applies to the original question, without its new flavor of Certificate-Less Authenticated Encryption.


PGP digital signature vs SHA256 HMAC Comparison First let me admit that I am not a mathematician or a cryptographer.
I am responsible for assisting in making a recommendation on a project that is consolidating payment processes within a company's internal network.

We have payment files which are being created by various applications; Several legacy applications are using PGP to digitally sign the payment files (sign only - no encryption. The hash algorithm is SHA1 and the digital signature algo is RSA 1024).  Several newer applications are protecting the payment files using SHA256 HMAC (using a 256 bit random private key).

Regardless of whether we decide on public key cryptography (PGP) or secret key cryptography (HMAC), we will replace the keys periodically and feel reasonably assured that we can protect the private key and passphrase or the secret key for HMAC.

The question has been raised questioning the relative strength of SHA256 HMAC vs. PGP digital signature.  We know that the PGP digital signature is appended to each payment file, and network admins and others can easily copy signed payment files (but they cannot get to the PGP keys folder nor the passphrase).  Similarly, the SHA256 HMAC hashtag value and the original plaintext payment file can be accessed by admins, but not the secret key.

Given that in both sets of applications a potential adversary can get the original plaintext and the digital signature or HMAC Hashtag, which of these two scenarios would be least vulnerable to brute force or other attacks that attempt to derive the private or secret key?  Based on current computing power, how long should we have reasonable assurance that either technology would be relatively secure?

PGP [1024-bit] digital signature vs SHA256 HMAC Comparison...

First, you can compare asymmetric and symmetric algorithms. A 1024-bit asymmetric key provides about 80-bits of security. A SHA256 HMAC provides about 128-bits of security. With all other things being equal, the HMAC is stronger.

Second, I believe PGP (or is it GnuPG) uses Lim-Lee primes and they don't provide the prime factorization. So you can't test that they are any good in practice.

Third, the random key used in the HMAC may not be random. And the random numbers used to generate the asymmetric keys might have problems too. Randomness is a lot like bugs. To borrow from Dykstra, you can test for the absence of randomness, but the presence of it.

Fourth, both systems sound like they might be subject to forgeries. So you might want to ensure surreptitious forwarding, replays and other tricks don't occur.

Fifth, ... (favorite threat here).

Also, storing the private key or the symmetric key is the Unattended Key Storage problem described by Gutmann in his book Engineering Security. Its a problem without a solution.

  other attacks that attempt to derive the private or secret key?

OK, this is easier. The adversary will not attempt to break the crypto. They will go around it. They will go around it by breaking into the system, getting root, and then reading the key from the filesystem.

There are only two crypto attacks I am aware. First was the factoring of the TI Signing Key, and second was the Flame malware. The TI factoring occurred on a 512-bit asymmetric key; while the Flame malware took advantage of MD5 collisions on Microsoft CA certificate.

Breaking into the system is a much more cost effective attack. It will probably start by phishing one of the ladies in HR or Accounts Receivable. That's how it started with with a few high profile attacks, like RSA Data Securities and one of the other big ones, like Sony (IIRC).

  Based on current computing power, how long should we have reasonable assurance that either technology would be relatively secure?

I think 80-bits of security is within reach of a few well funded adversaries. But out of reach of most others.

128-bit security will likely never be within reach of anyone.


Would a non-deterministic (read: randomized) compression algorithm be crypto-safe? Would a compression algorithm that randomly shifts stuff around every iteration be TLS/crypto-safe?

This randomization would prevent the same byte sequence from appearing twice in a row, thus making it harder to figure out the key and stuff. Altho I don't have any crypto knowledge...

Note that it would only apply to the compression step. The decompression step would always produce the same output when given the same input.

... a compression algorithm that randomly shifts stuff around ...

This is a contradiction in terms, surely? The extent to which any block of data can be compressed is directly related to the entropy of this data. The more predictable the data is, the lower its entropy and the more compressible it becomes.

If you apply random transformations to your data, you are increasing its entropy and making it less compressible. This defeats the purpose of your compression algorithm. Ultimately, you will end up with data that is indistinguishable from random noise, making it completely incompressible.


What is the meaning of h(r) in this protocol? Could somebody tell me what the meaning is of $h(r)$ in the protocol below?

$A\leftarrow{B}\quad:{h(r)}{,B}{,P{_A(r,B)}}
\\A\rightarrow{B}\quad:r$

As Ricky Demer already mentioned, $h$ is a hash function.

In the realms of cryptography, it mostly points to a secure hash function. But in the end, it doesn’t matter if it’s a secure hash or not… $h$ is standard notation for “hash”.


Several questions about Paillier cryptosystem I have several questions concerning the original Paillier cryptosystem as described in Paillier, Pascal (1999).
"Public-Key Cryptosystems Based on Composite Degree Residuosity Classes".
EUROCRYPT. Springer. pp. 223-238. http://www.springerlink.com/content/kwjvf0k8fqyy2h3d/?MUD=MP

Notation:
$p$ - unencrypted message, plaintext
$c$ - encrypted message, ciphertext
$r$ - random factor
$k_{pub}$ - public key
$k_{priv}$ - private key

I have a Paillier-encrypted ciphertext ($p$) that is no straight encryption but the result of an arbitrary number of various true or mixed homomorphic operations or re-randomizations.

Assuming I know $p$ and the corresponding private key $k_{priv}$.
Am I able to compute the random factor $r$ from this so that a reencryption of $p$ with $r$ would be identical to $c$, i.e. $E(p, k_{pub}, r) = c$ ?
if positive answer to 1, how do I compute $r$?
if positive answer to 1, is it possible that there exists another $r'$ so that a different plaintext $p'$ encrypted with $r'$ would also result in $c$, i.e.
$Enc(p, k_{pub}, r) = c = E(p', k_{pub}, r')$, $p \neq p'$, $r \neq r'$ ?
if positive answer to 3, could this $r'$ be efficiently computed, i.e. could the owner of $k_{priv}$ be trusted if he would provide $r$ to a given $c$ as (Zero knowledge) proof of correct decryption?

Let us briefly recall the Paillier encryption.
Let $k_{pub} = (N = PQ, g)$ be a public key, where $N$ is the RSA modulus.
The secret key is $\lambda = \mathrm{lcm}(P-1,Q-1)$ (or $P,Q$).
The encryption of $p \in \mathbb{Z}_N$ with randomness $r \in \mathbb{Z}_N^*$ is $C = g^p r^N \bmod{N^2}$.

You can verify $\mathbb{Z}_{N^2}^* \simeq \mathbb{Z}_N \times \mathbb{Z}_N^*$.
As Paillier wrote, there is a subgroup $G = \{z \mid z = y^N \bmod{N^2}\}$ of order $\phi = (P-1)(Q-1)$.
There is a bijective mapping $\tau$ from $\mathbb{Z}_N^*$ to $G$ which maps $y$ to $z = y^N \bmod{N^2}$. The inversion $\tau^{-1}(z)$ is computed by $y = z^{N^{-1} \bmod{\lambda}} \bmod{N}$. Roughly speaking, this is the RSA decryption with $e = N$.

Answers:

Yes.
You can find such $r$. Since you know the plaintext $p$, you can compute $d = g^{-p}C = r^N \bmod{N^2}$. By applying $\tau^{-1}$, you can find $r$. (See Section 5.)
No. There is only one $r \in \mathbb{Z}_N^*$. (See Lemma 3.)\
Makes sense since there may be even a huge number of ciphertexts representing the same plaintext but they all have to decrypt to just one plaintext. Hence r is unique as long as en- and decryption are executed using the same pair of keys.
No.


Faster alternatives to RSA trapdoor permutation We're working on web3.0 decentralized internet, a big part of which is a decentralized file storage system where clients upload files to storage providers and pay them for the services. Storage providers return signed messages, with the content hashes included, as guarantees, such that if they lose the file and fail to respond to a verification challenge on the blockchain, by not being able to provide the proof they're still storing the file, they will lose their collateral.
Clients upload files to several storage providers at once for redundancy. We needed to make sure that providers can't collude with each other/one provider can't misrepresent itself as being several and take payments for N copies of the file, getting away with storing only one copy. At the same time, the original file contents should always be available to storage providers, since they're supposed to publicly serve it on the network by responding to requests for the content based on its hash. This means encrypting several copies with AES
The solution I initially came up with is to use pure RSA (not hybrid) algorithm in signature mode, i.e. when you encrypt with the private key, and decrypt with the public key (or, more precisely, sign a message with a private key, and recover the message from the signature using the complement of that, but the math is the same as encryption/decryption, just with swapped keys). That way:

A client can generate one key pair per provider
When storing file F with the provider N, it can generate an "encrypted" replica of F (a signature containing the message) specific to that provider, by performing F_N = RSASign(F, k_priv_N), and sending the public key k_pub_N to the provider
Provider signs the guarantee on the Hash(F_N), promising to store the encrypted copy
Provider can at any point extract the content by performing F = RSARecover(F_N, k_pub_N) which is analogous to feeding the public key to a decryption algorithm, calculate the real hash Hash(F), and serve this file on the DHT network
However, all providers, even if they wanted to collude, must continue to store individual encrypted copies/signatures F_N because each signed off on their specific Hash(F_N). There is no way to lose the F_N, deliberately or accidentally, and then recreate it on demand just by having F and k_pub_N, because that would require knowledge of the private key (which also explains why RSA must be in pure mode, and not in hybrid node, because performing AES encryption on provider side is trivial given the symmetric key, and they could get away with having to store just the RSA signature on top of the symmetric key, which is much smaller in size).

This works well, but we've ran into a few problems with this approach:

RSA in pure mode is extremely slow
Using proper padding for each block reduces the space we can use for embedding the file chunks, and therefore the resulting files are many percent bigger than the originals

Q: Are there any other similar cryptographic functions we can use for this case, which are superior to the RSA scheme in speed and size?
(For example, we've been looking at elliptic curves but there doesn't seem to be a way to extract the message, or even hash of the message, which would have also been helpful, from an EC signature.)

encrypt with the private key, and decrypt with the public key

That statement, and the very name privateEncrypt, is incompatible with standard terminology: "public" means known to all and opposes to "private"; and "encrypt" implies transforming some information $X$ into $Y$ in a way such that if $Y$ becomes public, $X$ does not.
Per standard terminology we sign with total message recovery, and recover the message. The term "total message recovery" designates a signature scheme where all the data is conveyed in the signature itself. This is how RSA signature was introduced, and the term is used in the ISO/IEC 9796 series of standards.

RSA in pure mode is extremely slow

Whatever the name and the variants, RSASign is indeed rather slow, and usually size-expanding. This can be mitigated, but some slowness will remain.
On the other hand, RSARecover is relatively fast, and Integer Factorization (based) Crypto (the IFC family, which best known member is RSA) is by far the fastest asymmetric crypto around for the task. In the application, if information retrieval quantitatively dominates, that might be an advantage.

Are there any other similar cryptographic functions we can use for this case, which are superior to the RSA scheme in speed and size?

Outside of systems closely related to RSA in that they belong to IFC, none that I have met since I started watching public key crypto¹.
Let's see how we can mitigate the issues:

RSASign can be made faster by

Using a right-sized public modulus (and correspondingly splitting the information into blocks²). Currently the accepted minimum for signature is $n=2048$-bit public modulus, and all things being equal the signature cost per byte grows only slightly slower than $n^2$.
Using the Chinese Remainder Theorem method. Every speed-optimized implementation of RSA signature does that, because it reduces computational cost by a factor typically over three. Some implementations also use it to spread most of the workload on several CPU cores, further reducing encryption time. Implementations of RSA encryption can not use that method, because it requires the private key.
Using a public modulus product of $k>2$ primes. That's known as multiprime RSA. All things being equal, execution time is roughly halved when we go to 3 primes, divided by more than three with 4 primes. If high security assurance is not paramount, it would be reasonable to consider $(n,k)=(2048,4)$.
Using highly optimized implementation. Shay Gueron and Vlad Krasnov's Speed Records for Multi-prime RSA Using AVX2 Architectures (in CIT 2016) report $(1.9,\,1.0,\,0.6)$ million Skylake CPU cycles/signature for $n=2048$, $k=(2,\,3,\,4)$, translating to $(0.4,\,0.7,\,1.3)$MByte/s/core @3GHz (neglecting time and size overhead due to padding). And then dedicated hardware is a possibility.

Size overhead depends on padding:

If we want to use something standardized and cut no corner, we can use ISO/IEC 9796-2 scheme 2 and a random nonce as wide as the hash size. The size overhead is $3h/2+16$ bits out of $n$, that is 206 bytes stored in a 256-byte cryptogram with SHA-256 and $n=2048$ (+24.3% overhead). Even if the data actually stored was entirely constant, it's unlikely two stored blocks would get identical until there are $2^{64}$, that is >3ZiB effective data.
If we accept something custom, a deterministic transformation (which allows to store a single copy of identical data blocks), and dropping cryptographic signing, the size overhead can be one bit per block (just apply a reversible transformation to the data followed by textbook RSA signature, that is textbook RSA encryption), or even zero (apply textbook RSA only to values lower than the public modulus after the reversible transformation, and generate the public/private key pair so that the high-order 64 bits of the public modulus are all-one).

RSARecover can be made faster by

Using a low public exponent, such as $e=3$. This allows the exponentiation to use one modular squaring and one modular multiplication, rather than sixteen and one for the most common $e=65537$. Except for possible regulatory requirements, $e=3$ is fine. There's a saving by a factor of roughly 8, and now RSARecover typically is hundreds of times faster than RSASign (when $k=2$). We are talking some gigabit/s on a standard PC.
Using $e=2$, which allows a further saving by some factor like two. The name changes from RSA to Rabin signature, there are a few minor complications, but that remains fully academic and covered in ISO/IEC 9796-2.

¹ That was in 1980 during one of these strikes France is renewed for. My math (Spé) teacher dropped the official program and showed her class RSA, based on Martin Gardner's article.
² As pointed in comment, if we only do that splitting, we loose overall message integrity assurance (an adversary can swap signed blocks). I don't see that such assurance is indispensable in the context. But if we require it, we can prepend a fixed-width block number to a block's payload, at the expense of increased size overhead. A note suggests "Using CBC rather than ECB" but that does not seem to work unless the data signed is somewhat redundant.


Security importance of Key Schedule in Block Cipher For example block cipher AES-128, Key size is 128bit and it is used to make a 10 round key which is total 320bit.

Question 1. If i use another Key schedule algorithm in AES, then security decreased or remain same? In other words, if the key schedule algorithm of AES has some relationship with AES encryption itself, then it will be decreased, or it will be same if the new key schedule algorithm is safe enough.

Question 2. Why we expand key? brute force will take O(2^128) time regardless of the key schedule is strong or not. what is the advantage of making key expend?
I was curious about this when I was learned about 3DES.
Which developed because the former DES has weak key length 56bit so vulnerable to brute force attack, i was wondering why doesn't they just remove key schedule process and use the whole round key as a key.

If i use another Key schedule algorithm in AES, then security decreased or remain same?

This really requires a concrete proposal for an alternative key schedule in order to conclude whether or not it would constitute an improvement or a weakness.

The AES key schedule is not exactly ideal, but the rest of the design seems to be strong enough such that this does not really matter in practice. So the practical security would probably not be modified. The key schedule is almost surely the weakest part of the AES algorithm; The fact that it is secure as-is implies it probably would not make a gigantic difference to modify the key schedule.

I bet if we tried, we could come up with some kind of pathological example that would lead to a weakness, but I can't think of one offhand.

  Question 2. Why we expand key? brute force will take O(2^128) time regardless of the key schedule is strong or not. what is the advantage of making key expend?

This is a very good question that I have wondered about myself. I do not think I have ever seen explicit justification in a cipher proposal for why round keys are derived and applied exactly as they are - as in: "By deriving our keys this way and applying them at this specific interval, these attack(s) are prevented"

One thing that it accomplishes is that it makes each application of the round act differently. Symmetry of various kinds can be used in an attack against the algorithm.

I have seen a few papers that were specifically about the importance and design of key a schedule. Basically, they advocate ensuring full diffusion of the key and ensuring that, given one portion of a round key, it should be difficult to derive any other portions of the key.

So, hypothetically, if you used a fully diffusing, unpredictable, one way function as your key schedule, then recovery of one round key would not assist in recovery of other round keys.

Interestingly, I have found justification for NOT using a key schedule: The cipher LED utilizes no key schedule, and is resistant even to related key attacks because of it. It relies on the round constants to simulate independent round keys.

  I was curious about this when I was learned about 3DES. Which developed because the former DES has weak key length 56bit so vulnerable to brute force attack, i was wondering why doesn't they just remove key schedule process and use the whole round key as a key.

Since the DES key is only 56 bits, just using it directly would not be an improvement. Also, the DES key schedule pretty much does just use the key directly: It does pull from different bits over the course of different rounds, but it's really just re-ordering the bits of the key, and not really deriving a new/different one. Also note that 3DES utilizes more master key material then regular DES.


Why Might XOR's Lead to Hash Functions Lacking 2nd Pre-image Resistance? My hash function is as follows:

Cut the string in half (assume even length of 2m)
XOR's the two halves together
Take the result of the XOR and pass it to a function (a one-to-one and "onto" function) that simply does:

$f: \{0, 1\}^m \rightarrow \{0, 1\}^m$

I'm being asked to prove why this hashing strategy is not second pre-image resistant (though it is pre-image resistant) but I'm getting hung up.

I know a 2nd pre-image means finding $x' \neq x$ s.t. $h(x') = h(x).$

I also know that different strings can result in the same XOR:

$1010 \oplus 1111 = 0101$ and so does $0000 \oplus 0101.$

I think I'm just lacking complete understanding of the concept.  Thank you in advance for your help.

Well, if you construct what you described you basically create a function $f: \{0,1\}^{2m} \rightarrow \{0,1\}^m$.

As you correctly pointed out these two strings give the same when xor'ed. So the messages $10101111$ and $00000101$ will result in the same xor and hence will get mapped to the same hash, resulting in a second preimage as you found two $x,x'$ with $x\neq x' \wedge h(x)=h(x')$.

Now let's see what happens if $x$ is fixed:

Assuming you're given a value $x \in \{0,1\}^{2m}$ for which you want to to construct $x'\in\{0,1\}^{2m}$ with $x \neq x' \wedge h(x) = h(x')$.
Now observe that $x_1 \oplus x_2 = x_1' \oplus x_2'$ (with $x_1, x_2$ being the first and second half of $x$) will give the same hash $h(x_1 \oplus x_2)=h(x_1'\oplus x_2')$.
Now for a given $x=x_1||x_2$ one can easily construct $x'=x_1'||x_2'$ by using the equation $x_1 \oplus x_2 \oplus x_1' = x_2'$ so one can arbitrarily choose half of the second preimage and can then compute the other half. As $x_1' \in \{0,1\}^m$ this yields $2^m$ second pre-images for any given $x$.


Question about algorithm https://www.shoup.net/ntb/ntb-v2.pdf, page 523, algortithm IPT

I don't get the for loop, since "k" isn't used anywhere inside the loop. What am i missing?

Just above the algorithm, the document says:

  If $f$ is irreducible, then $\gcd(X^{q^k}−X, f) = 1$ for all positive
  integers $k$ up to $\ell /2$

What the loop does is just testing all the $\gcd(X^{q^k}-X,f)$ up to $\ell/2$.

To avoid computing $X^{q^k}$ at each $k$, you just compute $X^{q^k}=(X^{q^{k-1}})^q=h^q$.

At the $k$-th round you will have $h=X^{q^k}$.


Can DH_anon really be exploited by an attacker? General consensus is that DH_anon (and ECDH_anon) ciphersuites should be disabled since they offer no way to verify if the server is the one you intend to communicate with. However, I have never run into a client that supports DH or ECDH_anon. Could an attacker really leverage this to pull off a successful attack (with no errors/warnings?)

Ensuring that you're talking to the correct server is the client's duty. They need to verify the certificate and reject anonymous DH.

A client that accepts anon DH or doesn't verify the server's certificate is always vulnerable to MitM, even if the server disables anon DH.

Thus disabling anonymous DH on the server has little effect on security, beyond encouraging clients to choose proper ciphersuites. In the context of web applications, all popular browsers do not support anon DH to "secure" https.


Is it possible to generate a message using the mac and the key? Say that you have the Key and the MAC value that was generated from the Key using CBC.  Is it possible to generate a message with just the mac and the key?  If so, how would you do it?

This depends on the MAC algorithm.

Two examples:

With HMAC based on a secure hash function, no, there is no known way to construct a message fitting the MAC other than brute-forcing it. (If you want to find a specific message, like when you have a MAC of a message containing a password and some fixed text, brute-forcing the password might be quite feasible.)

With CMAC (a MAC-algorithm based on a block cipher), given the key and MAC value, it is usually quite easy to construct a fitting message, you even can chose all but one block of your message freely.

In general, MACs based on hash-functions are usually safe, MACs based on block ciphers not.

Have a look at the CMAC algorithm, assuming we have a full-length message (multiple of block size). In the image the length is 3 blocks.

             +-----+     +-----+     +-----+
             | M_1 |     | M_2 |     | M_3 |
             +-----+     +-----+     +-----+
                |           |           |    +--+
                |     +--->(+)    +--->(+)<--|K1|
                |     |     |     |     |    +--+
             +-----+  |  +-----+  |  +-----+
             |AES_K|  |  |AES_K|  |  |AES_K|
             +-----+  |  +-----+  |  +-----+
                |     |     |     |     |
                +-----+     +-----+     |
                                        |
                                     +-----+
                                     |  T  |
                                     +-----+

(Image modified from RFC 4493, page 5.)

Assume we know the key $K$ and the tag $T$, we did choose $M_1$ and $M_3$ arbitrarily and we now want to produce a message by finding a fitting $M_2$.

This is the formula:

$$T = E_K(E_K(E_K(M_1) \oplus M_2) \oplus M_3 \oplus K_1)$$

($K_1$ is derived from $K$.)

We can apply the decryption function on both sides:

$$D_K(T) = E_K(E_K(M_1) \oplus M_2) \oplus M_3 \oplus K_1$$

Next move the XORs over:

$$D_K(T)  \oplus M_3 \oplus K_1 = E_K(E_K(M_1) \oplus M_2)$$

Apply decryption again:

$$D_K( D_K(T) \oplus M_3 \oplus K_1) = E_K(M_1) \oplus M_2$$

One more step:

$$D_K( D_K(T) \oplus M_3 \oplus K_1) \oplus E_K(M_1) = M_2$$

Of course this also works with more than three blocks and if the last block is not a full block (then we pad and XOR with another key $K_2$ at the end), as long as one block is free to choose according to the result.

The general idea is that we can move through our diagram from both sides (replacing encryption by decryption if going in the other direction) until we arrive at the one unknown block.

The moral is that a MAC with a known key doesn't give us a secure hash function, where such a result would count as a preimage-attack.


Does ChaCha20-Poly1305 need random nonce? RFC 7539 says:

  A 96-bit nonce -- different for each invocation with the same key

It doesn't explicitly say whether it has to be random or not. If we use an ever incrementing counter. Would that be secured? Generating cryptographically secured random number is a slow process.

No, it doesn't need a random nonce.  Yes, if you use an incrementing counter, that works.

As the RFC says, the only requirement is uniqueness; as long as you make sure that each nonce you use is different, you have met the requirements - an incrementing counter does that quite nicely (and, in fact, is commonly used in practice)


Is such a crypto-system available? $E(k_1, pt) = c_1, E(k_2, c_1) = c_2, D(k_{new}, c_2) = pt$, where $k_{new} = f(k_1, k_2).$ Sharing $k_{new}$ and $k_2$ should reveal no information about $k_1$.

Clarifications:

Being able to decrypt the ciphertext $c_2$ knowing only $k_{new}$ is the first desired property of the system
One cannot derive $k_1$ knowing both $k_{new}$ and $k_2$.
One cannot easily derive $k_1$ knowing other pairs $k_2'$ and $k_{new}'$. See @poncho's comments.

$D(k_{new}, c_2) = pt$ or $E(k_{new}, c_2) = pt$ doesn't matter as long as you recover the plaintext.

Real world example to clarify things even more:

Alice has a very large database which it chooses to store at Eve's site. Because Alice doesn't want Eve to read the data, nor doesn't she know in advance which data will be shared with whom, she encrypts all the records with a single key ($k_1$).
Now Bob requests access to some specific information. Bob and Alice know each other so Alice gives him access to that subset. However Alice wants to do that efficiently. Also Alice doesn't want Bob to be able to read anything else except the shared subset. Therefore she cannot: a) Decrypt the shared subset at Eve's site and then re-encrypt with a different key (this would expose all the database contents to Eve), b) Retrieve the data from Eve, decrypt, re-encrypt and store back data at Eve's site - this implies a round-trip delay which is prohibitively expensive.

Thus Alice needs a cryptosystem which would allow re-encrypting the data directly at Eve's site, however Eve shouldn't be able to read any plain text (nor the one shared with Bob, nor the rest of the database records). Sharing the decryption key ($k_{new}$) is done through a direct channel between Alice and Bob (e.g. using Diffie-Hellman).

The "cryptosystem" stated in the question is just a way I saw that happening. Note that $k_1$ shouldn't become known to Bob (e.g. if Bob colludes with Eve or other people with whom Alice shares (possibly different sets of) data).

This can be done with RSA where k1 and k2 are encryption keys and f is  multiplication modulo the totient of the public modulus.
The last property, that knowledge of other pairs $k_2'$ and $k_{new}'$ does not reveal $k_1$ is satisfied by using a different modulus for each pair generated.


Do Curtmola et al.'s IND-CKA1/2 security definitions protect against search pattern leakage? In the
article Searchable Symmetric Encryption:
Improved Definitions and Efficient Constructions, Curtmola et al. propose adaptive and non-adaptive (indistinguishability and simulator-based) security definitions for searchable encryption schemes, conventionally called IND-CKA1 and IND-CKA2.

My question is: Do the IND-CKA1/2 security definitions guarantee that the search pattern is not leaked (i.e., that an attacker can not distinguish whether two issued trapdoors are generated with the same keywords)?

In their article, they mention that

  [...] the  security  notion  achieved  for SSE is that nothing is leaked beyond the access pattern and the search pattern [...]

Further, in their article, Bösch et al. state that

  Curtmola et al. review existing security definitions for searchable encryption and propose new indistinguishability and simulation-based definitions that address the shortcomings of the existing
  definitions. At the same time they loosen the character of SSE by allowing the
  leakage  of  a  user's  search  pattern.

So it seems pretty obvious that the definition should not guarantee search pattern hiding. Nevertheless, taking a look at the IND-CKA2 definition:

$\mathbf{\mathrm{Ind}}^{*}_{\mathrm{SSE},\mathcal{A}}(k)
\\
\;K\leftarrow \mathrm{Gen}(1^k)\\
\;b\overset{\$}{\leftarrow}\{0,1\}\\
\;(\mathrm{st}_{\mathcal{A}},\mathbf{D}_{0},\mathbf{D}_{1})\leftarrow\mathcal{A}_{0}(1^k)\\
\;(I_{b},\mathbf{c}_{b})\leftarrow\mathrm{Enc}_{K}(\mathbf{D}_{b})\\
\;(\mathrm{st}_{\mathcal{A}},w_{0,1},w_{1,1})\leftarrow\mathcal{A}_{1}(\mathrm{st}_\mathcal{A},I_{b})\\
\;t_{b,1}\leftarrow\mathrm{Trpdr}_{K}(w_{b,1})\\
\;\mbox{for }2\le i\le q,\\
\quad(\mathrm{st}_{\mathcal{A}},w_{0,i},w_{1,i})\leftarrow\mathcal{A}_{i}(\mathrm{st}_{\mathcal{A}},I_{b},c_{b},t_{b,1},\ldots,t_{b,i-1})\\
\quad t_{b,i}\leftarrow\mathrm{Trpdr}_{K}(w_{b,i})\\
\;\mbox{let }\mathbf{t}_{b}=(t_{b,1},\ldots,t_{b,q})\\
\;b'\leftarrow \mathcal{A}_{q+1}(\mathrm{st}_{\mathcal{A}},I_{b},\mathbf{c}_{b},\mathbf{t}_{b})\\
\;\mbox{if }b'=b\mbox{, output }1\\
\;\mbox{otherwise output }0$

one sees that any algorithm able to distinguish whether two trapdoors encode the same words or not directly breaks IND-CKA2, which would mean that IND-CKA2 protects against search pattern leakage.

For instance, and very informally, in the first trapdoor query $\mathcal{A}$ can set $w_{0,1}=w_{1,1}=w_{1}$ for some fixed $w_{1}$ and receive $t_{b,1}=\mathrm{Trpdr}_{K}(w_{1})$. In the second query, it can issue $w_{0,2}=w_{1}$ and $w_{1,2}\neq w_{1}$. Then $t_{b,2}$ either encodes $w_{1}$ or some other word, and $\mathcal{A}$ can guess $b$ by guessing whether $t_{b,1}$ and $t_{b,2}$ encode the same word ($b=0$) or not ($b=1$). Continuing in this fashion, since $\mathcal{A}$ breaks the "search pattern challenge", $\mathcal{A}$ has a non-negligible advantage in distinguishing $b$.

The condition $\tau(\mathbf{D}_{0}, w_{0,1},\ldots,w_{0,q})=\tau(\mathbf{D}_{1}, w_{1,1},\ldots,w_{1,q})$ rules out the possibility that $\mathcal{A}$ issues the keywords as I pointed in the question, since the output of $\tau$ includes the search pattern matrix defined in page 9. This has the effect of weakening the definition to allow search pattern leakage.

As a note, the stronger definition in Shen et al.'s 1 does not include a restriction of this type, and so it captures the search pattern protection property.

1 Shen, Emily, Elaine Shi, and Brent Waters. “Predicate Privacy in Encryption Systems.” In Theory of Cryptography, edited by Omer Reingold, 5444:457–73. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2009.


Find private exponent in RSA The other answers for this confuse me, I know the principle of d in terms of the equation it has to satisfy. However I'm not sure how I would go about finding the private exponent without trial and error. I want to implement this in a program, but I'm not quite sure the algorithm I would use to find d. Can someone explain the equation or algorithm for finding d?

If you know the prime factors (p,q) of the modulus, then it would be easy to find the private exponent.
You'll proceed as follow:

Compute the Carmichael function $\lambda(n)=\operatorname{lcm}(p-1,q-1)=\frac{(p-1)\times(q-1)}{\operatorname{gcd}(p-1,q-1)}$
Choose a number e such that $\operatorname{gcd}(e,\lambda(n))=1$,
Apply the Extended Euclid Algorithm to compute the inverse of $d=\frac{1}{e}\bmod\lambda(n)$,    Cf Donald Knuth:Semi-Numerical Algorithms II (or any other reference book),

Then the public Key is $(n, e)$, while the private Key is $(n,d)$. This correspond to the straightforward parameters of RSA Keys.
You can also generate with a similar way, the parameters associated to the CRT algorithm with allow a substantial gain when executing Modular exponentiation with the private Key.
If required I could depicted it.


How can I use the whole potential of DES? I have recently programmed the DES algorithm. Right now it works just with integers (or better to say chars) in the range <0;255>. How can I use its whole potential - using just ASCII would be a waste (there are many characters I would never use).

Programming your own DES is usually a bad idea (unless as an exercise to understand the algorithm better), but OK. By definition the algorithm works with blocks of data that consist of 8 bytes (i.e. integers in the range 0..255), and the key is 7 of those bytes (or 8 with unused parity bits).

What the data means (text or binary files like Office documents or zip files) etc. is irrelevant. I don't see what you mean by "full potential". You can just use it for ASCII text. It doesn't really matter what range the bytes are in. The encoding of the data is up to you (you can pack lower ASCII data into 7 bit characters, that overflow into the next byte, as SMS does, e.g.), and not a part of DES or any crypto-algorithm. Bytes are bytes. DES handles bytes.


Why can't ransomware practically use RSA to encrypt all files? I understand that a few ransomware have used an RSA public key to encrypt all files belonging to the victim. This is a bullet-proof system in terms of its security because the private key is always safe with the hackers.

But most ransomware use the hybrid encryption approach and during that they make mistakes allowing security researchers to build decryptors. The attractiveness of this hybrid approach lies in the speed of symmetric encryption. But because the hackers makes implementation mistakes in this approach, why don't all hackers switch to asymmetric-only encryption? It seems easier to implement programmatically than the hybrid approach. Is slow speed of RSA the only factor the limits the hackers? How slow is RSA when compared to AES for, let's say, 500 MB of data on an average i5 processor?

I have searched the Internet looking for a comparison between speeds of RSA versus AES for bulk data encryption in modern computers but found nothing. I understand that criminals cannot be reached for comment on why they don't use asymmetric-only approach for bulk encryption but I am looking to understand what could be the practical reason behind why bulk encryption with RSA is so undesirable.

RSA is really very slow compared with symmetric ciphers.
You can check this yourself running e.g. openssl benchmark:

openssl speed rsa

On my machine (and with openssl 1.1.1a) I get

Doing 2048 bits public rsa's for 10s: 330640 2048 bits public RSA's in 10.00s

so we can do ~33k encryptions per second and the size of the encrypted block is less than the modulus, so less than 256 bytes. If the attacker wanted to encrypt 1GB file, it would take about 2 minutes.
On the other hand,

openssl speed aes

shows that AES-CBC can encrypt ~300MB per second

type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes  16384 bytes
aes-128 cbc      94234.08k   136019.99k   137980.25k   304759.81k   304166.23k   315654.14k

so the same 1GB file would be encrypted in 3 seconds.

For the attackers, speed is important, since the faster the files are encrypted, the less likely the process will be interrupted.


Is there any benefit to using a randomly chosen replacement strategy on a string before or after encrypting it? This is more of a mental exercise for me than anything else. I've thought about doing something like this before, mostly to make a broken cipher a little more difficult to decrypt to plain text. I've simplified the strategy below, but in theory, you could use any length of replacement key first.

First, I would randomly choose a number of known length (say 4 digits). Let's use 1976 as an example. Then, I take the plain-text string, and do the following:

convert the string into a byte array.
for the first byte, i add 1. for the second byte, i subtract 9. for the third byte, i add 7, and for the fourth byte, i subtract 6. I repeat this throughout the byte array, then rebuild the string from the byte array. Next, I concatenate the 1976 key to the front of the string. Once that is done, I use standard AES 256 encryption.

Now, in practice, I would use more than just adding and subtracting and a longer integer value, but that gives an example of the "randomization" of the string prior to encryption. The idea is to provide an extra layer of randomness to the encryption scheme. However, I'm not sure if this provides any real value as if the IV/Key has already been obtained then how hard is it really to figure out what I'm doing with the appended integer? Would it be better to use this post-encryption? I'm really curious what the community thinks of this idea. Does it have any merits? What are the drawbacks? How good/bad of an idea is it really?

"However, I'm not sure if this provides any real value as if the IV/Key has already been obtained then how hard is it really to figure out what I'm doing with the appended integer?"

If the adversary has your key, then you have already lost, and there is little that can be done besides generating a new one and keeping it safe. The IV is considered public information and does not need to be kept secret, and does not need measures applied to attempt to keep it secret.

Would it be better to use this post-encryption?

No, it would not improve anything to use this transformation after application of the AES.

I'm really curious what the community thinks of this idea. Does it have any merits?

The internals of a cipher often permute or shuffle the data somehow, in addition to the substitutions they usually do. That itself is a good idea.

You basically are suggesting a simple substitution. Substitution is an important part of an substitution permutation network. Combinations of substitutions and permutations (shuffles), combined with key interaction, can indeed make a strong cipher. The AES is built off of these principles.

The exact transformation that you mention is not particularly novel or capable. Typically the substitution layer is performed via the application of an S-Box, which is very fast, or in situations where resistance to timing attacks is desired, some kind of non linear function that operates in constant time

 What are the drawbacks? How good/bad of an idea is it really?

However, your substitution is totally unnecessary if you are going to be encrypting with AES. The AES is by itself, already secure. Your modification would not improve this fact.

Worst case scenario, your modification could somehow open up a weakness that you had not considered. For example, what key were you planning on using to apply your substitution? Rarely do ciphers use the master key directly in their operations, usually they apply a key schedule first, as this can create a layer of separation between the "real" key and the round key used to actually do the work. Your transformation, considered in isolation, appears to be weak to known plaintext attack that could lead to key recovery.

Long story short, some form of substitution isn't just a good idea for a cipher, it's necessary. However, the AES was literally designed for this purpose, and does a good enough job already.


suggestions for cryptography projects for an ece 3rd year student I am an electronics and communication engg student currently doing my 3rd year second semester. i am interested in info coding and the security aspects of it. As an ECE student i want to know what is the scope of cryptography in my field.

and i also want to know about the projects that i can take up in the field of cryptography.

please anyone help me in this regard. i am good at maths

Cryptography is a broad field and most of it falls naturally under computer science and math. However there are certain areas that are very much within ECE's domain. For an undergraduate project, you typically do not need to find new results, just do a good literature review and perhaps implement/duplicate some of the results.

Here are a few ideas for an ECE student:

Side-channel cryptanalysis. When a cryptographic function is implemented, the implementation itself can leak information that is useful to an attacker. On the hardware side, it could be power consumer or radiation. With an FPGA, you may purposely zap certain gates to introduce faults that may leak useful information. (Wikipedia)
Reverse-engineering chips. Sometimes vendors will implement a cryptographic function without disclosing the details of the function. There have been a number of papers on reverse-engineering RFID chips by inspecting the VLSI layout. There are tools to automatically recognize certain gates or components from images of the circuit. (Example paper)
PUFs. Physically unclonable functions use the natural variance in physical structures to implement cryptographic functions. A number of candidates for PUFs are electronic components. (Wikipedia)
Implementation and Optimization. There is usually always room for implementing a function as optimally as possible in your favourite medium. For ECE: VLSI or FPGA for example. The major functions (AES, SHA, etc) have had attention in this regard but more obscure primitives/protocols may have less attention.
Circuit-based Evaluation. One goal in cryptography is to do computation on encrypted data in a way that does not reveal the data itself. There are generally three classes: two-party computation, multi-party computation, and homomorphic computation. In two-party in particular, an approach is to represent the function being evaluated as a boolean circuit and then use a technique called "garbled circuits" to evaluate. Most researchers look at general techniques for doing this efficiently and with high security; less look at how to best represent a boolean circuit that implements are particular useful function (beyond certain toy examples like Yao's millionaire problem). (Example Paper)

This is a good blog on research that is generally more from the engineering perspective.


Using SHA512 (or other hash) for message authentication I need to encrypt and authenticate a stream of data so that it is resilient against unexpected power loss, so I cannot write authentication data at the end of the stream.

I am currently using AES-GCM, just for encryption, as my understanding is that the authentication tag for GCM must be written at the end of the stream.

What I have in mind to do instead is to buffer the stream into fixed-size blocks, the SHA512 sum of each block, and then encrypt the block and n bits of the SHA512 sum and write them out. (My understanding is that truncating the SAH512 sum to save space is okay.)

My thinking is that, if an attacker wishes to tamper with the data in any given block, there will be a 2^-n chance that the hash calculated on decryption will match the one on-disk, (2^-n chance of the tampering going undetected). I also imagine that tampering with the hash won't improve the chances.

Is my thinking correct?
Is this scheme secure?
Is there a better/more established/more convenient way to do this?

I need to encrypt and authenticate a stream of data so that it is resilient against unexpected power loss, so I cannot write authentication data at the end of the stream.

This is a fairly confusing question you're asking, and I needed to read the whole thing over and over to come to a point where I felt I understood it.  What you want is to authenticate the data you're sending incrementally so that the recipient can establish the authenticity of chunks or prefixes without having to wait for the end of the whole stream.

The solution to this is to move the authenticated encryption inside the protocol that you're using to send data over the stream.  Instead of globally encrypting and authenticating a stream of plaintexts, you probably should send a stream of individually encrypted and authenticated ciphertexts.  AES-GCM will work fine for that—don't play around with homebrew ideas like what you're proposing.  You do have to be very careful about IV reuse.  (And about writing your own cryptography—are you sure you want to do this?)

One nuance here is whether you're trying to authenticate individual messages or stream prefixes.  This is related to the question of what should the recipient do if one message in the stream is adulterated:

Skip it and carry on processing the subsequent ones;
Abort the whole thing and don't process any more messages.

What's the correct thing to do depends on the application.  I'd put a bit of thought into that question.  But for case #2, there are tricks that can be done to cause the authenticity of later messages to depend on that of earlier ones.

  I am currently using AES-GCM, just for encryption, as my understanding is that the authentication tag for GCM must be written at the end of the stream.

There is no logical requirement to write the authentication tag at the end of the stream. It's just a very convenient way of doing it, since:

It allows you to write the ciphertext into the stream incrementally as you compute it;
You can't emit the tag until you've encrypted the whole message anyway.

If you buffer the whole ciphertext and tag into memory before writing them to the stream you could write them in the opposite order if you so preferred.  I figure some specific AES-GCM implementations may be hardcoded to write the tag at the end, though.

  My understanding is that truncating the SHA512 sum to save space is okay.

If you're truncating to 256 bits, there's a newer SHA-2 variant called SHA-512/256 which already does that.  But the larger issue is that SHA-2 is not a message authentication code, so it's not a substitute for GCM's authentication.


Publicly exchanging keys my use case is the following: Sharing a secret on the blockchain from one participant over a smart-contracts with revealing the secret only after some condition is verified (another participant has paid for it).

Since every content on the blockchain is publicly available, I'm looking for a cryptographic way of exchanging keys.

This use case should be quite common for smart-contracts.

I think the notion you're secretly after is Verifiable Delay Functions.

They don't depend on a verifiable condition, they provide a way to ensure that no-one can compute them in a short time (even by massive parallelization).
They can be used during a synchronization step controlled by a smart contract.


TLS 1.3 Secure Renegotiation not supported I get the message "Secure Renegotiation IS NOT supported" if a TLS 1.3 cipher will be chosen at a TLS handshake with openssl s_client. Since TLS 1.3 does not support renegotiation at all I assume that this message can be ignored. Is my assumption correct?

Yes, since TLS1.3 forbids any renegotiation, supporting rfc5746 with it would be meaningless, and rfc8446 doesn't even mention the possibility.

Of course an endpoint that supports both 1.3 and lower versions should (in the 2119-capitalized sense) use 5746 for sessions that negotiate a lower version, and (AFAIK) OpenSSL does.


What is the main difference between Unique signature and Verifiable Random Function? The output of VRF contains two parts, the first is the output of the VRF hashing and the second is the proof of correctness. In a unique signature scheme, the signature also contains two parts which are similar to the VRF.

The previous works pointed out the VRF can be obtained via a unique signature, but in general, they have the same outputs, so I am confusing what are the main differences between them? Is there a generic framework of how to construct a VRF from the unique signature? Or we can say, once obtained a unique signature, then we can say it is a VRF?

A signature scheme has the following two functions for a key pair $(k, K)$:

$\sigma = \operatorname{Sign}_k(m)$
$\mathit{valid?} = \operatorname{Verify}_K(m, \sigma)$

A VRF has slightly more:

$(\sigma, x) = \operatorname{VRF}_k(m)$
$\mathit{valid?} = \operatorname{Verify}_K(m, \sigma, x)$

Without knowledge of the public key $K$ and the signature $\sigma$, the VRF output $x$ appears to be an independent uniform random bit string for each distinct $m$.  That is why it is a verifiably pseudorandom function: except for verifiability, it appears to have independent uniform random outputs.

In contrast, for example, RSA-based signatures typically have a per-key distribution that is distinctive enough to deanonymize signers in practice (popular exposition; actually this was RSA-based ciphertexts but the principle is the same).  While EdDSA signatures do not have a distinctive per-key distribution, they easily distinguished from uniform random bit strings because they encode $(R, s)$ where $R$ is a point on the curve (only about half of such bit strings will be so) and $s$ is an integer below the order of the curve (which is often substantially less than the number of bit strings of the same length).

If there is exactly one $\sigma$ for each $m$ under any particular public key $K$, then we can devise a VRF with the help of a uniform random function $H$ as follows:

$\operatorname{VRF}_k(m) := (\sigma, H(\sigma))$, where $\sigma = \operatorname{Sign}_k(m)$
$\operatorname{Verify}_K(m, \sigma, x) := (\operatorname{Verify}_K(m, \sigma) \mathrel{\text{and}} x \stackrel?= H(\sigma))$

Choosing, e.g., $H = \operatorname{SHA-256}$ makes a practical VRF that is secure against $H$-generic adversaries, or ‘secure in the random oracle model’, because without knowledge of the unique $\sigma$ for any particular $m$, $H(\sigma)$ is a uniform random bit string independent of anything else you can compute.

(More on signatures vs. VRFs with references.)


Is the composition of collision resistant hash with non collision resistant hash a collision resistant hash? Suppose $h_1$ is collision resistant, and $h_2$ isn't.

Will $h(x)=h_2(h_1(x))$ always be collision resistant?

[Edited:] the output of h2 must be uniformly distributed

Will they always be collision resistant? No

For example, let $h_2(x)=0$. Then, $h(x)=h_2(h_1(x))=0$, which certainly isn't collision resistant.

Can it be collision resistant? Yes

For example, suppose we define $h_1(x)=\mathrm{SHA256}(x)$ and

$$
h_2(x)=\begin{cases}
   0 & |x|=1
\\ \mathrm{SHA256}(x) & \mathrm{else}
\end{cases}
$$

Then, since the output of $|h_1(x)|=256$, the composition will leave:
$$h(x)=\mathrm{SHA256}(\mathrm{SHA256}(x))$$
Which is believed to be collision resistant from the collision resistance of Sha256.

But what if $h_2$ is uniformly distributed across a 'sensible' codomain? As before

I add the requirement that it must be uniformly distributed across a sensible codomain since I assume this clarification wishes to prohibit hash functions for which the target space is too small to possibly be secure)

We can trivially create two examples that demonstrate the above properties. Let $W=\{0,1\}^{256}$. Then, as before let $h_1$ be a cryptographically secure hash function, with $h_1 \colon \{0,1\}^* \to W$ (eg SHA256 as above).
Define $h_2(x) = h_1(\mathrm{MSB_{256}}(x))$.

Then $h_2$ is not collision resistant (since for any $x\in W$ and $y\in\{0,1\}^*$ we have $h_2(x)=h_2(x||y)$), but as before $h(x)=h_1(h_1((x))$.

Defining $h_2(x) = h_1(\mathrm{LSB_{256}}(\mathrm{MSB}_{512}(x))$ (ie we extract bits 256->511) we get the composition $h(x)=0$ which is not collision resistant.

A slight issue here might be justifying $h_2$ is uniformly distributed, but this comes down to how you attach a distribution to the set of all random strings - ie the distribution taken by $\{0,1\}^*$


Using Lattice-based cryptography for TLS\SSL Given the general benefits of Lattice-based cryptography, such as:

Post quantum Security
Security from worst case scenario
Efficiency

What could the outlook of shifting from RSA \ ECC-based cryptography to the Lattice one (say NTRU) be?

Would that be feasible?

Are there any drawbacks?

Feasible? Sure, there are lattice algorithms that are competitive in performance with RSA.

However, there are drawbacks, like:

They've been studied less than RSA or ECC, especially the individual algorithms.
The most well studied system, NTRU, is patented.
No generic proof that I know of that there isn't a quantum algorithm to solve them.

The first one is why I doubt TLS will quickly move to lattices at least unless there's significant evidence that a quantum computer capable of breaking current crypto is practical. The third means that even then another public key system might be better, if such can be found.


Independence of answers to queries sent to a random oracle Assume we have an algorithm which asks random oracle $\mathcal{O}$ $Q$ queries $u_1, \ldots, u_Q$. All queries are unique, $u_i \neq u_j$ for $i \neq j$. Queries $u_i$ are random variables, too.

What is the easiest (mathematically correct) way to see that the random variable $(\mathcal{O}(u_1),\ldots,\mathcal{O}(u_Q))$ has uniform distribution -- or -- that $\mathcal{O}(u_i)$ are independent random variables?

It looks like that the standard theorems covered in textbooks - like this one in Stinson - cannot be directly applied.

EDIT:

Here is more formal and simplified version of my question: $A$ is set of all random tapes (or private keys or something), $B$ is is set of all functions from, lets say, $\mathbb{Z}_q$ to $\mathbb{Z}_q$. $\mathcal{A}$ is some algorithm that has parameters $\omega \in A$ and random oracle $\mathcal{O}$ from $B$. We pick elements from $A$ and $B$ with uniform distribution.

For example, assume I want to calculate the probability
$
  P((\omega, \mathcal{O}) \in A\times B| \mathcal{A}(\omega, \mathcal{O}) \text{ succeeds})
$

This can be rewritten as

$
  P((\omega, \mathcal{O}) \in A\times B| \mathcal{A}(\omega, \mathcal{O}(u_1), \ldots, \mathcal{O}(u_Q)) \text{ succeeds})
$

And then I have a Stinson's theorem which can be replaced by some other  other "textbook" or citeable theorem.

The main goal is to prove $(\omega, \mathcal{O}(u_1), \ldots, \mathcal{O}(u_Q))$ has uniform distribution by citing something.

Firstly, note that saying that the queries $u_1,\ldots,u_Q$ are distinct implies that they are not independent, for example, if $u_i=a$ then $u_j\neq a$ for all $j>i$.

Secondly, your argument indeed follows from the definition of a Random Oracle found in Stinson's book. Let $\mathcal{O}:\mathcal{X}\rightarrow \mathcal{Y}$ be a random oracle. That means that for every query $u$ that has not been queried before, it holds that $Pr[\mathcal{O}(u)=y]=1/|\mathcal{Y}|$ for every $y\in \mathcal{Y}$. Now, since $u_1,\ldots,u_Q$ are all distinct it follows that

For all $y\in\mathcal{Y}$ and $i\in[Q]:  Pr[\mathcal{O}(u_i)=y]=\frac{1}{|\mathcal{Y}|}$

$\Rightarrow$ For all $(y_1,\ldots,y_Q)\in\mathcal{Y^Q}$:  $Pr[\mathcal{O}(u_1)=y_1,\ldots, \mathcal{O}(u_Q)=y_Q]= \prod_{i=1}^Q Pr[\mathcal{O}(u_i)=y_i]=\frac{1}{|\mathcal{Y}|^Q} $


How hard is to find the operators of an addition knowing the sum of them? I want to learn whether or no there is a cryptographic primitive,scheme assumption that is based on the following hard problem if it is hard . By hard we mean that we have a polynomial adversary: The attacker obtains a number  $\sigma$ . In order to reverse engineer that or to go one step further for the cryptanalysis she needs to break that number in a set of numbers $m_{1}, m_{2}, m_{3}, \ldots, m_{n} : \sum_{i=1}^{n}m_{i}=\sigma$ . How hard is that problem?

Well, the problem "given a finite set $A$ of integers, is there a subset that sums to a target value $B$" is known as the Subset Sum problem; it is known to be hard.  Specifically, the decisional problem (is there such a sum) is NP-complete, and the computational problem (find the subset) is NP-hard.

That means that if you could solve large instances of this problem quickly, you could use that to solve a lot of interesting problems quickly, including just about any problem in crypto (finding AES keys given plaintext/ciphertext, factoring numbers, etc).

Because of this, assuming this is a hard problem would appear to be a fairly safe assumption.

On the other hand, it's not at all clear problem your problem statement that this is the problem you're relying on.  You are you "add each index of them and construct a table"; what do you mean $n_1[0]$?  If this is bit 0 of message digest $n_0$ and you're adding all the bits 0's from the message digests to form bit 0 of $T$, then you're not relying on subset problem at all; you're relying on the related problem that uses bitwise exclusive or -- that problem is known to be easy.


Generating 64 bit random values using AES-CTR I need to generate 64 bit random values using AES-CTR.

Using fixed 64 bit plain text and sequential nonces can I assume the  higher order 64 bit output values of the AES-CTR to be random with a period of $2^{64}$?

AES-CTR can be used as a random number generator if you don't mind that it never repeats the same 128 bit value - but the chances of that happening are minimal with a true RNG anyway.

In that case there is no need to have any plaintext though: you'd simply create the key stream (the encrypted counter values). If you only have a higher level cipher at your disposal you can simply do this by encrypting zero bytes.

If your key (the seed) is random then you can leave the IV/nonce set to zero as well and just start the counter (encoded as 16 bytes) at all-zeros.

If you'd use only 64 bitsof the 128 bit key stream generated by encrypting the counter then you would not have a repeated block within $2^{64}$ blocks. Although AES-CTR does have a period of $2^{128}$ blocks there is no guarantee that a value of 64 bit isn't repeated earlier.

Of course the cipher still has a period (as in, a long repeated sequence) of $2^{128}$ blocks as the counter will restart at zero when that happens, inconsequential of how many bits are actually used of each block.


Some terms related to secret sharing: Optimality, What does it mean? In any secret sharing scheme we have to develop step by step.
After constructing such scheme we need to reduce share size. Why?
e.g. Robust secret sharing scheme is modified Shamir secret sharing scheme with error correcting REED SOLOMON codes.
In order to gain near optimality we need to reduce share size. Why? what is optimal in any secret sharing scheme? How do i know it's optimal?
From cheater resilient (t,$\delta$) robust secret sharing scheme ,it says that the scheme is optimal. How do they know?

Optimality is actually not a well-defined term for secret sharing, and can refer to a number of different issues. First, one issue that is often considered is the size of the share that each party holds in the scheme. If the size of a party's share equals the size of the secret itself, then the secret sharing scheme is called ideal. (Formally, we don't talk about "size" but that the shares comes from the same domain as the secret.) Shamir's secret sharing scheme is ideal.

Other issues which come up are the threshold: how many parties are needed to reconstruct the secret versus against how many parties security holds, what the threshold is for active/passive security and so on.

In short, the paper should define what they mean by optimal, and especially regarding what parameters.


Flexibility in $RSA$ and $DLOG$ standards? Today's security is based on $RSA$ and $DLOG$ primarily. If both go down then it is hard to imagine a scenario where internet can be salvaged quickly.

Assume $RSA$ with $n$ bit prime factors and $DLOG$ with $n$ bit prime modulus have a (possibly practially realizable (Shor's algorithm still has challenges in implementation) quauntum) algorithm with $\leq(20n)^{2.5}$ time (picked an exponent on par with today's linear programming complexity exponent and $20$ was a reasonable small number). Then if we take $10^{25}$ arithmetic operations as ultimate limit of realizable complexity then if $n\leq 5\times 10^8$ holds we can break it ($(20n)^{2.5}\leq10^{25}\iff(20n)^{}\leq10^{10}\iff2n\leq10^9$).

How large can $RSA$ and $DLOG$ keys be before the standard gives up?

Is it reasonable to assume $10^9$ bit keys are possible with next generation internet?

How large can RSA and DLOG keys be before the standard gives up?

In theory, they can be indefinitely long using some implementation adaptions. However, they would become too impractical compared to post-quantum algorithms which do not require such key lengths that no one will use them.

  Is it reasonable to assume $10^9$ bit keys are possible with next generation internet?

I am not sure what you mean with "next generation internet", but the answer is most likely no, independently of what you mean with this.
The reasoning for this is as follows: the hardness assumptions of RSA and ECC, on which the security of these schemes relies, are indeed based on factorization and the dlog problem. Hardness is here defined as: "there exists no polynomial-time algorithm which can solve this problem". However, with a sufficiently large error-corrected quantum computer and using Shor's algorithm, these hardness assumptions are not hard anymore. I.e.: this algorithm (and for d-log a slightly modified one) can solve these problems in polynomial time.

Solving this issue with keys of $10^9$ will never happen, because there exists plenty of algorithms which are based upon other hardness problems for which no polynomial solving algorithm is known in the presence of such quantum computers. Therefore: no, $10^9$ bit keys will most likely not be used anytime soon (next ~50 years).

If you are interested in public-key post-quantum algorithms which are in a competition by NIST to become the next standard, take a look here: https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions


How does one conduct a known-plaintext attack on an algorithm? My question is two-fold:

Say I am given a total black box and I have n number of plaintexts as inputs that map directly to $n$-number of ciphertexts as outputs. This is all I know, and I do not have access to the algorithm. Is it possible to conduct a known-plaintext attack?
In the event that I do have access to the algorithm's internals, how would one go about attempting a known-plaintext attack on a cryptosystem? What specific weaknesses or traits in the algorithm would one generally be looking for? Is it algorithm-specific or is there a generic process?

If your black-box access entails being able to query the cipher with keys and plaintext of your choice, then it is straightforward to mount a brute-force search for the key if given some plaintext-ciphertext pairs. This will in expectation, however, need about as many queries to the black box as the key space is large.

For strong modern ciphers, this brute force attack is meant to be the best attack already. For a cipher not known to be cryptanalytically broken, knowledge of the internals of the cipher will "only" help you to parallelize the attack and maybe do some inner-loop optimizations.

If "black-box access" means only having some pairs of ciphertext and plaintext but no access to the algorithm or an implementation of it, efficiently implementable algorithms can still be broken in theory given enough data. Briefly, given an algorithm A and some plaintexts P as well as ciphertexts C, checking whether A transforms P to C is doable basically in the time needed to run A on P. Hence, an adversary can for instance enumerate all instruction sequences in a language of their choosing in ascending length and stop when they find a match.

Note that while this is clearly even more impractical than the standard brute force attack on ciphers with a reasonable key size is, checking a solution is a polynomial-time problem in the length of P and A, under reasonable assumptions on A. There is no known proof that problems that are polynomial-time checkable cannot be solved in polynomial time (this is the P versus NP problem), so there is no proof that known plaintext attacks on unknown efficiently implementable ciphers cannot be executed efficiently (although there may be polynomial-time separation results that show that the defender can always get an advantage over the adversary).

However, everyone very strongly conjectures that secure ciphers exist. If that is the case, then of course breaking a strong cipher with only some examples of plaintext-ciphertext pairs will be utterly hopeless.


Securely rekey/re-encrypt AES-encrypted file Suppose I have a big file encrypted using AES (any mode you want) with key kA.
I'd like to give an untrusted proxy a kA->kB "conversion key" so that it re-encodes the file from kA to kB without learning the contents of the file or any of the keys.

Is this possible?

If not, are there any widely-supported encryption algorithms that allow that?

Well, if you use AES in counter-mode, you could give the proxy the XOR of both counter-mode streams; he could then XOR in that XOR with the file encrypted with one key, and that'll give him the file encrypted with the other.

This does have the drawbacks:

This XOR is as large as the file you've encrypted
This XOR is specific to the IV you used to encrypt (and so if multiple files are encrypted this way, you'll need a separate conversion key for each one)
There is no integrity checking on the encryption format.

On the other hand, if we allow the use of public key encryption methods, we can do this with Integrated Encryption Scheme.

Here, the public key is a value $A = g^a$, and ciphertext consists of a pair $g^x$ and the actual message encrypted using symmetric crypto keyed based on the value $C = A^x$ (and so the holder of $a$ the private key can compute $A^x = C^a$, and then use that to decrypt the symmetric portions.

Now, this allows a conversion key $y = ab^{-1} \bmod q$ (where $q$ is the size of the subgroup we're working in); then, the proxy can compute $D = C^y$, and then substitute $D$ in place of $C$ in the ciphertext.  Then, the holder of $b$ the other private key can compute $D^b = C^{(ab^{-1})b} = C^a = A^x$, and then use that value to decrypt.

And, the value $y$ (and the values of the public keys $A, B$) does not give the proxy enough information to deduce the private key values.


Why do we use pseudo random PRNG in cryptographic applications instead of true random number TRNG Cryptographic applications use deterministic algorithm for random number generation that are not statistically random but they appears to be random.

Why do cryptographic applications use PRNGa instead of TRNGa?

Expanding small shared secrets

In many cryptographic systems, it's necessary for the two honest parties to have a shared secret between them such that:

The attacker cannot easily guess it.
It's large enough to protect a large volume of data.

For example, the one-time pad tells us that if two parties have a shared secret at least as large as the message, that is sufficient to communicate the message confidentially.

But the fatal problem then is, how do the parties manage to establish such large shared secrets?  And the practical solution is to:

Establish a small shared secret instead of a large one—say, 128 random bits—as the key.
Use a secure, deterministic PRNG to expand the key into a long, pseudorandom bit stream that's guaranteed to be the same on both sides.

This is for example how stream ciphers work.

Engineering challenges of TRNGs

How do you build a true random number generator so that it's:

Correct: Is the output actually random?  I.e., no bit of the output must be predictable from any other.  How do you prove this?  There are physical processes that science says are truly random, but does your machine introduce some predictable measurement errors into the system, and does your TRNG reliably remove these?
Reliable: Doesn't fail often, and when it does you can tell it did.
Auditable: The users can actually verify for themselves that it is correct and reliable.
Performant: Produces random bits at a sufficiently fast rate.
Efficient: Doesn't use lots of power.
Affordable: Doesn't cost a lot of money.

It's not easy at all!  Cryptographically secure PRNGs are better in nearly all categories.  Their only downside is that by definition they cannot truly random—but given a slow TRNG to provide seeds for the secure PRNG, that's a theoretical, not a practical downside.

Some of the techniques used in true RNGs are actually quite educational about the value of PRNGs.  For example, one common technique in TRNGs is to XOR the TRNG's output with that of a PRNG.  The reason for this is that way if the TRNG's true random components fail silently or are just not correct, the pseudorandom data mixed into the output can serve as a backup to keep the security level above a certain baseline.

That's an example of using a PRNG to address the engineering challenges of building a TRNG.

Cost effectiveness

The cheapest secure solution for most applications is to use a slow source of true random data to periodically seed a secure PRNG.  By allowing that source of true randomness to be very slow (produce random bits at a low rate), it makes all the engineering challenges easier.  By using noise from peripherals that the computer already has (e.g., keyboard, mouse and network timings), it reduces the cost even more, and makes it easier for third parties to audit than a custom, proprietary device would.

The resulting system is not truly random, but it just needs to be good enough, not theoretically perfect.


Why does the NIST Runs Test include a Frequency Test? In the NIST suite of RNG tests (https://csrc.nist.gov/publications/detail/sp/800-22/rev-1a/final), one  of the tests is the Runs Test, which tests counts of runs of 1's and 0's. According to the documentation, you need to first carry out a Frequency Test, which essentially confirms if the number of 1's within the sequence is within $\pm$4 standard deviations (where $\sigma=1/{\sqrt{2n}}$) for $n$ total bits.
There is already a Frequency Monobit Test elsewhere in the test suite, and the test statistic is very similar in each. One calculates $count_{1}/n - 0.5$, and the other calculates $|{count_{1}-count_{0}}|/\sqrt{n}$. Why do we need this second Frequency Test as part of the Runs Test? Why not just let the Runs Test test the Runs, and the Frequency Monobit Test test the frequencies of each bit?

The Monobit test checks the frequency of 0 and 1 over the whole sequence tested. The Frequency test does that on $M$ sub-blocks, where $M$ is an additional parameter. For example, with $M>1$ (and way up), a sequence of $n=8000000$ bits consisting of $4002000$ times 0 followed by $3998000$ times 1, which passes the Monobit test, will fail the Frequency test.

Such detailed examination of the justification of each test should not obscure the big picture: only failing SP-822 (or any statistical test of randomness) matters. SP-822 is good at what it does, but passing a statistical test does not prove anything useful from a cryptographic standpoint. When a generator fails SP-822, the generator is flawed. Don't fall to a converse error!
It's impossible to assess positively the quality of a conditioned¹ random source from its output alone (as SP-822 proceeds). That's a trivial consequence of the existence of practically secure PRNGs. And SP-822 is not applicable in practice to unconditioned random sources (for one thing, they tend to fail the Monobit test. Those that do not for long sequences have some internal de-biasing, which amounts to conditioning).
Remember, Dual_EC_DRBG was developed with the purpose of having a backdoor in crypto gear, and phased out when that got widely known. Meanwhile, Dual_EC_DRBG had become a standard, and people tend to trust standards. A RNG using Dual_EC_DRBG passes SP-822 with flying colors. SP-822 is a de-facto standard on randomness testing. That test and Dual_EC_DRBG are developed by the same organization. I do not make a certain conclusion on intention. Draw your own.

Actual security evaluation of cryptographic random generators should assess:

The physical soundness of the unconditioned random source.
The statistical soundness of an online test that monitors that source on the field, and safely shuts the whole thing off on failure. Principles of the simplest tests of SP-822 apply.
The cryptographic soundness of the conditioning algorithm.
The conformity of the implementation to the above design.

¹ The traditional structure of a RNG comprises a source of randomness followed by conditioning that produce the final output, plus supervision to detect failure. Some classic conditioning techniques include Von Neumann Extractor; LFSR in scrambler mode followed by decimation; and various CSPRNGs.


TLS 1.2 Cipher Suites With AES-GCM – What data (if any) is passed to the AES-GCM cipher as the Additional Authentication Data? TLS 1.2 defines a number of cipher suites that employ AES-GCM, e.g.:

TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256
TLS_ECDHE_ECDSA_WITH_AES_256_GCM_SHA384
TLS_ECDH_ECDSA_WITH_AES_128_GCM_SHA256
TLS_ECDH_ECDSA_WITH_AES_256_GCM_SHA384
TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
TLS_ECDH_RSA_WITH_AES_128_GCM_SHA256
TLS_ECDH_RSA_WITH_AES_256_GCM_SHA384

Being that AES-GCM is an AEAD cipher, it handles both encryption and integrity verification.  Also, it can optionally accept additional authentication data as one of its inputs (in addition to the plaintext, the key, and the iv).  The additional authentication data is not encrypted, but it is included in the integrity verification process.

I’ve read RFC 5289, RFC 5288, RFC 5246, etc., but I’ve not found any mention of what data, if any, is passed to the AES-GCM cipher as the additional authentication data in a TLS 1.2 implementation such as one of the above.

My question is:  In a TLS 1.2 implementation that employs AES-GCM – what data (if any) is passed to the AES-GCM cipher as the additional authentication data?

Actually section 6.2.3.3 of RFC 5246 talks about the associated data:

  The additional authenticated data, which we denote as
  additional_data, is defined as follows:

additional_data = seq_num + TLSCompressed.type +
                    TLSCompressed.version + TLSCompressed.length;

  where "+" denotes concatenation.

So the sequence number, the packet version, the packet type and the packet length are passed as associated data to the cipher.

So why is exactly this data authenticated?

The sequence number: Authenticating this helps prevent re-ordering and replay attacks and binds the sequence number to the data packet.
The protocol version: Authenticating this ensures that if you can't downgrade the protocol version (eg to SSLv3) to exploit weaknesses and learn something about the content of the current packet.
The packet type: I suppose this blocks you from re-using a handshake packet for an application traffic packet (which may have independent sequence number streams)
The packet length: This blocks you from silently chopping some data off somewhere, but is mostly here because it's public data and authenticating it doesn't really hurt.


Finding a solution to a (sort of) discrete logarithm by asking questions Let $p = kq + 1$ and $q$ be primes such that $log$ $q = n$, $log$ $k = n$ and such that the bit size of every prime factor of $k$ is bounded
  by $log$ $n$. Let $g$ be a generator of the unique subgroup of $Z^*_p$
  of order $q$.

  $x \in$ $Z_q$ is picked randomly and you get $y = g^x$.

  You may ask any number of questions of the form $u \in Z^*_p$, which
  will be answered by $u^x$ $mod$ $p$.

  How would you go ahead to compute $x$ efficiently?

Solving the discrete logarithm problem would be nice, but I guess that's out of the question.. :)

I don't get which properties that's given to use, (probably all of them) Any ideas/hints? Appreciate it!

I'll give a sketch of the solution to a quite similar problem (that makes more sense to me). The purpose of this modified problem is to show that it is essential to take $g$ of order exactly $q$ in the given setup, as one otherwise gets an oracle returning $u^x$ given $u$ as in your problem. (I'll show the connection between both problems (yours and mine) at the end of my answer.)

  Let $p = kq + 1$ and $q$ be primes such that $\log{q} \approx n$, $\log{k} \approx n$ and such that the bit size of every prime factor of $k$ is bounded
  by $\log{n}$. Let $g$ be an element of $Z^*_p$ of order $k'q = p-1$, where $k'\mid k$.

  $x \in$ $Z_q$ is picked randomly and you get $g$ and $y = g^x$.

  How would you go ahead to compute $x$ efficiently?

1) Write $k = \prod_i r_i$ as product of (pairwise coprime) prime powers r_i.

As $k$ has only small prime factors, you can find this factorization.

2) Define $g_i := g^\frac{kq}{r_i} = g^\frac{p-1}{r_i}$, and find its order $s_i$ in $Z^*_p$, which has to be a divisor of $r_i$.

3) Set $y_i := y^\frac{kq}{r_i} = y^\frac{p-1}{r_i} \in \langle g_i\rangle$ and determine $x_i \in \{0, 1, \dots, s_i-1\}$ with $g_i^{x_i} = y_i$.

As $s_i$ is the power of a small prime $p_i$, you can find $x_i$ by finding first $x_i \bmod p_i$, then $x_i \bmod p_i^2, \dots$ (please tell me, if you need a further hint for this).

4) Convince yourself that $x_i = x \bmod s_i$ for all $i$, and use the Chinese remainder theorem to find $x'$ with $x' = x \bmod \prod_i s_i$ (by definition $k'=\prod_i s_i$). As $x < q$ (we chose $x \in Z^*_p$), there are not many candidates $x' + l\cdot k'$ for $x$ as long as $\log k' \approx \log q$ (if $k' > q$ one has $x = x'$).

You can get from your problem to mine by finding a generator $u$ of $Z^*_p$ (you are able to find this generators as you know/can find the factorization of $p-1$), and applying once your oracle to obtain $u^x$ (with the nice extra property $k=k'$). I use then the relation between $g$ and $y$ to get a special oracle: $g_i$ corresponds to $u$, and $y_i$ to $u^x$.

Final remark: Instead of picking the random $x$ in $\{0, \dots, q-1\}$ one can could pick $x \in \{0, \dots, p-2\}$ to prevent anyone from finding $x \bmod q$, but giving away unnecessarily information about one's random source doesn't feel good and wastes resources...


RSA signatures without padding? Suppose I have a message $M$ for which I generate an RSA-2048 digital signature as follows:

$H = H(M)$, $H(M)$ being the SHA-256 of the message $M$
$S = H^d \bmod N$

Assume $N = pq$ is properly generated and $d$ is the RSA private key. And I verify the signature as follows:

$S^e \bmod N = H'$

where $H'$ is the SHA-256 of the message to be authenticated. Assume $e$ is the RSA public key.

Since I've not used any padding then are there any flaws with the above approach? What if $e = 3$? What if $e = 2^{16}+1=65537$?

Your guidance is much appreciated.

One property that this unpadded system is that it is homomorphic; if $A^d = X$ and $B^d = Y$, then we know that $(AB)^d = XY$, and it doesn't matter if we don't know what $d$ is.  More generally, if we have a collection of $H_1, H_2, H_3, ... H_n$, and a collection of signatures $S_1, S_2, S_3, ..., S_n$, then for any set of integers $e_1, e_2, e_3, ..., e_n$, we have:

$$(S_1^{e_1} S_2^{e_2} S_3^{e_3} ... S_n^{e_n})^d = H_1^{e_1} H_2^{e_2} H_3^{e_3} ... H_n^{e_n} $$

So, if we take a large collection of valid message and signatures pairs, hash the messages, and then factor the hashes.  Then, we look for multiplicative combinations of those hashes that yield a hash that we haven't seen (going through a long list of messages to hash); if we find a message that hashes to a value we know a linear combination of, we can immediately deduce the signature.

The attack works for any value of $e$


Is it safe to initialize secret keys by just reading /dev/random on Linux? For a software, I don't want the user to choose weak keys, so I plan to just read the needed number of bytes from /dev/random to create the needed secret keys. Is it safe to do so?

Yes, in any algorithm where keys are just random numbers, reading them from /dev/random is safe.

However, /dev/random blocks if the kernel's entropy estimate goes to zero so it is often a good idea to use a user space CSPRNG seeded from /dev/random or /dev/urandom for session keys and other similar random numbers that are used in bulk. The newer getrandom interface may be preferable when available.

Using /dev/urandom or getrandom directly is also fine, when you do not need a high rate of randomness, as they are rather slow (on Linux < 4.8 at least).


Common modulus attack with not coprime exponents lets suppose we have the public keys $(n,e_1)$ and $(n,e_2)$, such that $\gcd(e_1,e_2)=d>1$, and the same message encrypted with these two keys.

I'm trying to see if common modulus attack on RSA can be adapted to these problem where $e_1$ and $e_2$ are not coprime, but I always get stuck at some point where I should calculate a discrete logarithm, which is obviouslly not viable in an attack to a cryptosystem.

Any ideas about if it is possible this adaption?

No, it's not possible (or so we hope).  If you could, you could break RSA.

Suppose you had an Oracle that, given $n, e_1, e_2, m^{e_1}, m^{e_2}$ with $\gcd(e_1, e_2) = d$, and which is able to output $m$.  We can assume that the Oracle only works for a specific $e_1, e_2$ pair.

Then, suppose you were given $c = m^d$, and wanted to recover $m$.  Here is what you could do:

Compute $c_1 = c^{e_1/d}$, and $c_2 = c^{e_2/d}$

We note that $c_1 = m^{e_1}$ and $c_2 = m^{e_2}$.

We give $n, e_1, e_2, c_1, c_2$ to our Oracle; our inputs matches the Oracle requirements and so it produces $m$, thus solving the original RSA problem.


What is / How would I calculate the number of bits(?) I need to make the probability of a collision very small? If I wanted to create a TOTP-esque algorithm that generated a string n characters long, with each character being a base64 character, generated from a user secret r Base64 characters long, every s seconds, for each of u number of users, where the probability of collision is very small, how would I calculate the length of the string that was needed?

In case my wording is bad (I'm new to this), here's an example: Say it's generated every 30 seconds from the user's secret, I have 100,000,000 users, the algorithm output is 8 characters long, and the secret for each user is a 32 character Base64 string randomly generated when the user signed up. What would the probability be that two users got the same algorithm output as each other in any one 30s* period? How would I figure out how many characters I would need to make it a one in a million chance?

* Like TOTP, for all users, the 30s period would be the same, i.e. between seconds 0-29 or 30-59 on the clock.

If I wanted to create a TOTP-esque algorithm that generated a string n characters long, with each character being a base64 character, generated from a user secret r Base64 characters long, every s seconds, for each of u number of users, where the probability of collision is very small, how would I calculate the length of the string that was needed?

Well, the probability that two specific users get the same r secret is $2^{-6r}$; there are $u(u-1)/2$ distinct pairs of users, hence the probability that there exists a pair somewhere with the same secret is no more than $2^{-6r} u(u-1)/2$ - with the values of $r, u$ you mentioned ($r=32, u=100,000,000$), this is tiny (circa $2^{-138.8}$, and so we can safely ignore that.

Now, the probability that, during a specific s second time interval, that two specific users get the same n character sequence is $2^{-6n}$; again, there are $u(u-1)/2$ distinct pairs of users, hence the probability that there exists a pair somewhere with the same output is no more than $2^{-6n} u(u-1)/2$

Now, you suggest $n=8$, if you plug that into the above equation with $u=100,000,000$, you get a value larger than 1 (hence that provides no meaningful bound on the collision probability, and in practice means that there likely exists several collisions).

To deduce what $n$ would need to be to make the probability bounded by $10^{-6}$, we would need to solve the problem $10^{-6} \ge 2^{-6n} u(u-1)/2$; solving this numerically for $u=100,000,000$ gives $n \ge 12.014...$; that is, an $n$ of 12 isn't quite enough to give you the probability you're looking for (but it's close).

Now, if you want that $10^{-6}$ probability to span over $k$ intervals (that is, that there is a collision anywhere in the $k$ $s$-second span, you'd need to solve $10^{-6} \ge k \cdot 2^{-6n} u(u-1)/2$


Is ECDSA signature strongly EUF-CMA? I read, here, that ECDSA signature is EUF-CMA but not SUF-CMA, aka sEUF-CMA (for strong existential unforgeability under adaptively chosen message attacks; see terminology there).

Specifically, the assertion is that given an ECDSA signature for a message, it is possible to transform it into a different signature that pass verification for that same message.

Is there such issue, and where exactly does it lie?

mathematical definition
standardized definition of signature in some edition of ANS X9.62 (paywalled), SEC-1, or FIPS 186
some implementations

From SEC1 v2.0 (§4.1, pp. 43–47), a public key is a point $Q \in E$, and a signature on a message $m$ is a pair of integers $(r, s)$ satisfying the signature equation (condensed from several steps):

\begin{equation*}
  r \stackrel?= f\bigl(x([H(m) s^{-1}]G + [r s^{-1}]Q)\bigr),
\end{equation*}

where $f\colon \mathbb Z/p\mathbb Z \to \mathbb Z/n\mathbb Z$ projects the least nonnegative integer representative of an element of the coordinate field onto the scalar ring.  Here $G$ is the standard base point, and $H$ is a hash function mapping messages to scalars.

This equation is invariant under the transformation $\phi\colon (r, s) \mapsto (r, -s)$ because $(-s)^{-1} = -(s^{-1})$, $[-\alpha]P = -[\alpha]P$, $(-A) + (-B) = -(A + B)$, and $x(P) = x(-P)$.  It is also obviously invariant under the transformation $\psi\colon (r, s) \mapsto (r, s + n)$ because $s$ is used only as a scalar.

There are three additional requirements specified:

$r$ and $s$ must lie in the interval $[1, n - 1]$, where $n$ is the order of the group.
If $H$ returns invalid then the signature verification must fail.
$[H(m) s^{-1}]G + [r s^{-1}]Q$ must not be the point at infinity.

The only requirement relevant to strong unforgeability is (1), because it rules out the transformations $\phi$ and $\psi$ individually.  But it does not rule out, e.g., $\psi \mathbin\circ \phi$, equivalent to $(r, s) \mapsto \bigl(r, (-s) \bmod n\bigr)$.

Conceivably the signature scheme could require that $s$ be chosen to be ‘even’ like in ANSI X9.62 point compression, or be chosen to be in the lower half of the interval $[1, n - 1]$.  But such requirements are not imposed by verifiers, and so ECDSA cannot provide strong unforgeability.

There are also other obvious ways that an implementation could fail to provide sEUF-CMA:

The implementation could fail to check the intervals of $r$ and $s$.  (However, I don't know any that do.)
The implementation could allow for many different encodings of a single integer.  For example, it could allow BER or DER encodings in some ASN.1 format—because the standard doesn't specify a byte encoding of integers; the signature scheme is really defined in terms of integers, a mistake avoided by EdDSA.

This is the first source of transaction malleability that was reported in Bitcoin, prompting implementations to accept only the unique DER encodings of signatures and reject other encodings, before someone noticed the negation vector too a year and a half later.  (Exercise for the reader aching for a trip down a rabbit hole: Chronicle the saga of transaction malleability in MtGox and figure out what's up with the bankruptcy proceedings these days.)


For two LUKS volumes made with the same password, can stealing the encryption key from one volume allow access to the other? A running computer has two LUKS volumes that were made with the same password. One volume is open (key is in RAM), the other is closed.

If the running computer is stolen, is the closed volume safe?

If sha256 is broken, is the closed volume safe?

It should be safe. If the running computer is stolen and memory is read, it's the master key that will be revealed, allowing decryption of only that volume. The password itself is only used transiently when you open the volume to decrypt the master key. The other volume, despite using the same password to decrypt its constituent master key, will have a different master key.

When you use a system like LUKS, you are not encrypting data directly with your password. Rather, a completely random key is generated that is used to encrypt your data. This key is called the master key, sometimes called a data encryption key. This master key is itself encrypted with another key (derived from your password), called the slot key, or key encryption key. The encrypted master key is then stored directly in the encrypted volume. Because each volume will use a different master key, revealing one master key says nothing about the other, nor does it say anything about your password.

An attacker can attempt to brute force your password. This is done by guessing a password, processing it, and seeing if it can successfully decrypt the master key. They will only succeed if your password is very weak due to the processing algorithm LUKS uses, called PBKDF2. This algorithm runs your password through a hash function a huge number of times. It is intended to take approximately one second on a consumer computer. While waiting one second to see if your password is correct won't bother the end-user, it does mean that cracking the password becomes significantly harder.