Using the output of a stream cipher, how to guarantee the integrity of 4 bytes of data? I am designing a simple and secure stream communication protocol. My idea was to build each message sent to the wire as:

(message size || clear text || UHASH(message size || clear text)) $\oplus$ unique stream cipher output

where UHASH is the main function from UMAC (see question Using UMAC with stream cypher), || is concatenation and $\oplus$ is exclusive or.

The problem is that I found it was very easy to DoS attack my system; all it takes is to flip a high order bit of the 4 byte message size, and the receiver will wait for a multiple gigabyte message before having the chance to verify the MAC.

My solution is, if the message is bigger than some reasonably small size, I will add a MAC just after the size, validating it, so no very long message will be expected without validation. It seems to work, but given the overhead of calculated a 8 bytes keyed MAC from a 4 byte value, I wondered if there is any simple way of guaranteeing the integrity of such a small value using only a stream cypher and a few bytes more than the value I want to protect.

Do you know of any? For instance, let $\times$ be multiplication mod $2^{32}$, sending such a header:

(message size $\oplus$ cipher output 1) || (message size $\times$ cipher output 2)

would solve my problem? I understand that the probability of forgery can not be smaller than $1 / 2^{n} $ for the n extra verifications bits I send, but how to guarantee this chance is close to the minimum?

So you have a small integer, and you want to transmit it in such a way that (a) you don't particularly care if the attacker finds out what that integer is, but (b) no matter what the attacker changes or substitutes, you don't want the receiver to be tricked into thinking you sent some other number (in particular, some other much larger number).

securing the integer

As you've already figured out, that is exactly the purpose of a MAC such as a UMAC
and the purpose of a digital signature.

There are many protocols (including gzip and MP3) that add a CRC immediately after the header, in order to allow the receiver to immediately reject a packet with accidental noise in the "length" field (a), (b), for exactly the reason you mention.

I've seen a few ad-hoc constructions where the transmitter sends the number N
followed by some simple function of N, such as (N+1), (~N), (-N), N itself again, CRC(N), fletcher_checksum(N), etc.

Alas, as you already know, a standard CRC is vulnerable to malicious modification (even when encrypted by a stream cipher):
an attacker who knows the exact position of the length field and the CRC that covers it
can flip the high bit of the length field, and then flip the effected bits of the CRC,
resulting in a valid-looking header -- even if the entire message -- length, CRC, and all -- is protected by a "perfectly-secure" one-time pad.
(Most other "simple function of N" are just as vulnerable).

(Does switching from a stream cipher to a block cipher help?)

Your idea of using a MAC such as UMAC to protect the header (including the "length" field and perhaps also including a few bytes of random nonce) helps a lot, but it doesn't completely fix the DoS issue you mention:

message = header || MAC(header) || clear text || MAC( header || clear text )

then transmit

( message ) ⊕ unique stream cipher

The " Should we MAC-then-encrypt or encrypt-then-MAC? " question implies that it may be better to do that in the opposite order:

header = (length || other stuff) ⊕ unique stream cipher
body = (clear text of message) ⊕ unique stream cipher

then transmit

header || MAC( header ) || body || MAC( header || body )

Either way, the attacker won't be able to "blindly" DoS your system by sending a short message that looks like a valid header for a gigabytes-long message, unless he comes up with a valid-looking MAC(header) -- which is difficult.

securing the integer isn't enough

However, if you ever really do start sending a valid message with a valid header indicating "gigabytes of data will follow", and then if the attacker manages to insert or delete or change any bits or bytes in the following message, then the receiver will still get hung up doing useless work processing those gigabytes of data, only to throw them all away in the end.
(And what happens next week when the attacker sends a short message that replays that valid "gigabytes of data follows" message header again?)

alternatives that don't require securing the integer

For this reason, many protocols and file formats (ZMODEM, IPv4, IPv6, gzip, MP3, etc.) put a hard limit on the maximum length of a packet (with a "length" field of 16 or fewer bits), forcing larger amounts of data to be chopped up into a series of packets.
Rather than "a 4 byte message size",
they have, for example, "a 12 bit message size field",
and then files of data longer than 4 KBytes are sent as a series of packets,
each packet with its own independent CRC or MAC or digital signature.

In addition to avoiding the "DoS" problem you describe, breaking up long messages into packets
also has other advantages.
When a few packets are damaged by "innocent" noise,
the system can figure out which packets were damaged,
and then resend just those packets,
rather than re-sending the multi-gigabyte file all over again from the beginning.

Possibly related questions:

Can you make a hash out of a stream cipher?
Converting a stream cipher into a block cipher


How to encrypt plain-text message using Diffie-Hellman algorithm Let's say bob says Hi and Alice says Hello, With the knowledge of n and g, how can we encrypt those message using Diffie-hellman or any ECDH

If you look at the Wikipedia page of Diffie–Hellman key exchange you will see that, the algorithm is actually a key exchange protocol.

That is; two parties agree on a new key such that any of the two parties doesn't know before the protocol.

We use this protocol to generate a new key, and transfer the messages by using a symmetric encryption algorithm like AES with the generated key.

If you are looking for an encryption based on the Diffie-Hellman assumption you should check ElGamal Encryption


Decrypting the same message with the same IV using aes-256-cbc Is it safe to use the same IV when decrypting the exact same encrypted message. From my understanding, there is a security flaw when using the same IV for numerous different messages, as attackers can deduce patterns.
Also is aes-256-cbc the correct encryption method and mode for this scenario. If not, which ones are better?

First of all IV is decided while encrypting, you must decrypt using the same IV that was used during encryption. So, the question should really be about encrypting same message with same IV not about decrypting.
In CBC mode, using same IV and same key for different messages can help you detect the common prefixes in the message which diverges after encountering the first different block. That's why using same IV is never semantically secure as you can easily see where the messages diverge, that is information is leaked even if you are not allowed to repeat messages. Back to the question and similarly, using same IV and key for the same message will always produce same ciphertext, thus you can easily see repeated encrypted message for seen ciphertext. If this much of information reveal is acceptable to you, it's OK but it may not be OK to everybody.
There is no "correct" encryption mode in this scenario, it depends on what type of security you want and is important that you know the risks involved. CBC mode has some flaws and should not be used unauthenticated. It is vulnerable to bit flipping attacks (flipping bits on ciphertext produces predictable change in the next block) and can be devastating if the application accepts random block just before the targeted block or if it is the first block (in which case you can achieve the same by bit-flipping the IV). Similarly, it may be vulnerable to padding oracle attacks depending on what type of system it is used with and what kind of information it reveals deliberately or unwittingly. My best advise is using authenticated encryption modes like GCM or GCM-SIV.
Using same IV on different message wouldn't be as bad in CBC mode as it would be for CTR or OFB or GCM mode (for these, consequences can be devastating) and using same IV for same message in these modes would pose the same problem, detection of repeated messages due to repeated ciphertext and it all depends on whether if they are OK with it.


Deriving a key for HMAC, using PBKDF2 What is the recommended way to derive a key for an HMAC-SHA256, from a passphrase and salt?

I'd like to compute an HMAC-SHA256.  I have a passphrase, and a message.

I note that RFC-7518 (JWA) states that for HMAC,

  A key of the same size as the hash output (for instance, 256 bits for
  "HS256") or larger MUST be used with this algorithm. (This
  requirement is based on Section 5.3.4 (Security Effect of the HMAC
  Key) of NIST SP 800-117, which states that the
  effective security strength is the minimum of the security strength
  of the key and two times the size of the internal hash value.)

From this I conclude that it is not recommended to use the bytes directly from the passphrase for the key.  The passphrase may not have the appropriate entropy, if it is not 32 ascii characters in length. Even then, still ascii.

Question 1. correct?

ok, next up is to derive a key.  I note that PBKDF2 can rely on HMAC-SHA256 to produce keys.

Question 2.  But .... now I am in a turtles situation, am I not?  I am using a HMAC-SHA256 with a low-entropy key, to derive a supposedly higher-entropy key for an HMAC-SHA256.

I had a heck of a time searching this forum, because every question uses the term hmac, password, pbkdf2, and sha-256.  Basically I want to know if it is sensible to use PBKDF2 with HMAC-SHA256... to derive a key to be used in an HMAC-SHA256.

No, you should not use a password directly as an HMAC key.

However, it is fine to use HMAC as part of a key derivation function, which generates keys from a password. However, do not mistake the output as naturally having higher entropy than whatever you put in. "password" has essentially 0-bits of entropy, and running it through a KDF will not magically give it 256 more.

Using PKDF2 with HMAC-SHA256 as its PRF to generate a key from a password which will then be used as an HMAC key for other purposes is completely fine. The iteration must be high enough, which at this point in time is around a quarter of a million, which takes about 0.1s on a moderately fast computer.


Can a LFSR has more than one repeat cycle? It's clear that an LFSR has finite states and eventually will end up with repeating cycle. However, is it possible for an LFSR to have more than one repeating cycle? For example, with initial state $A$, its goes to cycle $C_a$, and for initial state $B$, it ends up with cycle $C_b$.

There is a very nice recent paper available here by Chang, Ezermann, Ling and Wang, which has addressed this problem for arbitrary alphabet $\mathbb{F}_q$ and arbitrary characteristic polynomials, including those with divisors that are powers of irreducible polynomials.

Let $\Omega(f)$ be the set of sequences satisfying $f$ as their characteristic polynomial.

This paper determines the cycle structure of $\Omega(f)$ fully for an arbitrary $f$ and gives a method to identify a state from each distinct cycle in $\Omega(f)$, a longstanding open problem.


Verifying randomness and uniqueness of TRNG output We need to verify two claims about a set of numbers:

They are random
They are unique in the set (the set is about 200 billion (2TB bin storage))

Supposedly, the numbers were generated by a TRNG (based on a radiation detector). The TRNG itself is a PCI Express card (which we do not have yet) and is probably a TRNG feeding a CSPRNG.

What ways are there to verify the claims? For randomness there are the NIST and other specs and tools.

But how can one tie a verification of the first claim to verifying the second (uniqueness in the set)? Keep in mind that the output of the TRNG has almost certainly been filtered from duplicates. That is most probably going to break the randomness tests.

There is no such thing as a random number and as such it is a category error to attempt to verify whether a particular set of numbers is ‘random’.  There are random generators of numbers; the relevant question is whether you—or, more importantly, a well-funded adversary—can predict the output when you don't know it a priori.  To answer that, you must:

Study the physics of mechanism inside the device.  Hire the world's best theoretical physicists to find the best model with humanity's current understanding of physics for how the mechanism behaves.

What verification can you do here?  You, or the experimental physicists you hired, can devise experiments to rule out alternative hypotheses for how physics might work.  But there's nothing at this stage that you can meaningfully do to the output of your RNG device.

Study the engineering of the device.  Hire competent engineers to determine whether there are ways for the device to fail, and if so, model how it will behave when it does fail.

What verification can you do here?  You, or the statisticians you hired too, can devise a hypothesis test to distinguish a failed component from a working component based on the output of your RNG device.
Make sure that computing the hypothesis test doesn't leak secrets through side channels.

If there is a CSPRNG involved, study the cryptography of the CSPRNG.  Hire the smartest cryptanalysts in the world to find distinguishers for the CSPRNG.

What verification can you do here?  You, or the cryptography engineers you hired too, can write automatic tests using known-answer test vectors to confirm that the CSPRNG implements the same design that has been subjected to decades of scrutiny and vetted by cryptanalysts publishing in serious peer-reviewed academic conferences around the world.
Note that the CSPRNG is essentially guaranteed to prevent hardware health tests, which is why you should apply those first to the hardware RNG output before conditioning it with a CSPRNG.

Alternatively, if you don't like these answers, I hear you can buy a book of certified random numbers from RAND Corporation, so named presumably because they're experts on the matter.

As for detecting duplicates, it depends on what units the data are in.  Duplicate bits?  Well, there's only two possible bits, so you probably have duplicates unless you've found new kinds of bits hitherto unknown to humankind!  Duplicate terabit-length bit strings?  You probably have only one of those even if you have several terabytes of data.  But maybe you meant something like 32-bit or 256-bit strings.  One way to detect duplicates in a large list is to sort it—costing $O(n \log n)$ time in the naive view of things, or $O(n \sqrt n)$ in the more realistic area-time metric which may become relevant in large volumes of data—and then scan through it for duplicates.  But this seems to be a general non-cryptographic algorithm question.


Diffie-Hellman private key recover with non-prime modulus Say we have a classic Diffie-Hellman key exchange. We have the following parameters of a public key:

p,g,y

Where $p$ is the modulus, $g$ is the base, $y$ is the public key, and $x$ is the private key in the following equation:

$y = g^x \bmod p$

It happens that the modulus is a composite number, which can be factored into primes.

How can someone find $x$, thus solving in the discrete logarith problem (DLP), by factorizing the modulus into primes, and solving the smaller DLP's with the primes, then combining them with chinese remainder theorem?

We start by finding the factorization of $p$ as $\prod p_i$; then find the $x_i$ with $g^{x_i}\equiv y\pmod{p_i}$ using an auxiliary algorithm to solve the DLP, perhaps Pollard's rho and/or Pohlig-Helman.

I'll assume that the $p_i$ are distinct, which was the case in the original question. They thus are coprime, and by the Chinese Remainder Theorem $g^x\equiv y\pmod p$ is equivalent to $\forall i, g^x\equiv y\pmod{p_i}$.

Fermat's little theorem tells us that $g^{p_i-1}\equiv1\pmod{p_i}$, since $p_i$ is a prime not dividing $g$. Therefore, $g^x\equiv g^{x\bmod(p_i-1)}\pmod{p_i}$. Therefore it is sufficient to find $x$ such that $\forall i,x\equiv x_i\pmod{p_i-1}$ (see final section for a better alternative).

Problem is, the moduli $m_i=p_i-1$ are not coprime: for a start, they all are divisible by $2$. That prevents a different use of the regular CRT to find $x$. We need to reduce the $m_i$ in order to make them coprime, while leaving their Least Common Multiple unchanged.

Assuming that we can fully factor the $m_i$: we collect every prime $q_j$ in these factorizations, and find it's maximal multiplicity $k_j$ (that is the maximal $k_j$ so that $q_j^{k_j}$ divides at least one of the $m_i$). Then for each $q_j$, we select one (of possibly several) $m_i$ that $q_j^{k_j}$ divides, and we divide each other $m_i$ by $q_j$ as many times as possible.
Note 1: Each time we divide an $m_i$ by $q_j^{k_{j,i}}$, we can check that $x_i\equiv x_j\pmod{q_j^{k_{k,j}}}$, and otherwise conclude that there is no solution.
Note 2: We can avoid full factorization of the $m_i$ and use Greatest Common Divisor computations, but that's slightly involved; see this.

If $x\equiv x_i\pmod{p_i-1}$, then $x\equiv x_i\pmod{m_i}$ holds for the reduced $m_i$. The converse holds if we made the checks in note 1. We can now find a suitable $x$ using the regular CRT, requiring coprime $m_i$. We do not need to recompute the $x_i$, but we can reduce them modulo $m_i$.

If we did not perform the checks in note 1, we need a final check that $g^x\equiv y\pmod p$.

Another issue is that $x\equiv x_i\pmod{p_i-1}$ is a sufficient, but not necessary condition for $g^x\equiv g^{x_i}\pmod{p_i}$ to hold. Thus, the CRT applied as above can find an $x$ that's needlessly larger than needed. A solution to this is to initialize $m_i$ with the order of $g$ modulo $p_i$, that is the smallest positive $m_i$ with $g^{m_i}\equiv1\pmod{p_i}$. That's some divisor of $p_i-1$, not always $p_i-1$ itself.


Message input format for RSA algorithm I was trying to implement the RSA algorithm myself. I have written the key generation part. My question is if I have the word "apple" which I want to encrypt, do I have to convert each alphabet to ASCII and then apply RSA to each letter or are there some other way?

It would make sense to encrypt as many bytes as possible at the same time. For example, a word like apple can be written as this sequence of byte values in hexadecimal 61 70 70 6c 65. You can treat this as a 40-bit number 0x6170706c65, which is equal to 418498243685. When this number is retrieved after decrypting the ciphertext, just convert it back into hexadecimal to get the original byte values.

Obviously you would need an RSA modulus of at least 40 bits to encrypt a word of this length. In practice, it would have to be a lot longer than that. An important part of RSA encryption is the use of randomized padding. Without it, the word apple would always be encrypted to the same value, so an attacker could easily encrypt every word in the dictionary and compare the results with your ciphertext to find out what word you had encrypted.

Standard padding schemes like OAEP recommend the use of at least 64 random bits to ensure that the likelihood of the same word being encrypted the same way is negligibly small. You also need to ensure that your modulus can't easily be factored, which means it should be a number of at least 1024 bits.


Case Scenarios where Identity Based identification (IBI) Scheme can be employed I was reading about identity based Identification scheme today. There are lot of articles and research paper on it. There is active research being done in this are of IBI schemes.
My question is simple. Are there any real life situation(case scenarios) where Identity based identification scheme can be used as a cryptographic primitive?
Thanks for reading. I would be grateful for any response.

Perhaps an extensible version of the Twitter blue checkmark scheme?
A trusted central authority (Jack) sets up a parameterised system that allows signing keys to be produced whose verification keys match identifiers. A Twitter service user (Lil Nas) sets up an account with Jack. Jack carefully verifies that Lil Nas is whom they claim (or simply allows them to select an unused identifier) and issues them with the signing key that matches their identifier. In addition to signing all of their transactions on Twitter so that anyone can verify the connection between the identifier and tweets, Lil Nas could also use the key to sign and validate transactions on other platforms such as TikTok or Instagram or DMs, uniquely tying the content to the owner of the account on Twitter.
Users only need the system parameters from Jack and a single signature verification to tie content to identifier, which is probably more lightweight and robust than PKI certificate-based solutions.


What does modular inversion mean? I'm trying to implement an e-voting algorithm, which is described at the paper "Internet Voting Protocol Based on Improved Implicit Security" by Abhishek Parakh & Subhash Kak.

At the Example 1 described in the paper where we have m1=85, at the step 2 it says

"2. Choose randomly and uniformly a number r1 = 101
and compute r2 = m1*(r1)^-1 = 85*(101)^-1=85*28=67mod257"

How is this possible? I mean how can 101^-1 be 28?

Notice that the result says 67 mod 257.
All calculations here are being done modulo 257. So, $101^{-1}$ is actually the modular inverse of $101 \bmod 257$, which is 28. Similarly, $85 \cdot 28$ is also done modulo 257.


Exploit RSA , given some information about n Every week Bob updates his public RSA modulus $n=p*q$ and encryption
  exponent $e$ by picking a new pair of primes $p$ and $q$ and a new exponent
  $e$. After several weeks, bob becomes lazy and decides to keep the prime
  $p$ fixed and only updates the other prime $q$ every week. Eve hears about
  this. How can she exploit this information to decrypt messages sent to
  Bob using his public key ?

I don't know how to solve it, any help or hint would be much appreciated.
I understand we need to retrieve $p$ and then we can get any $q_i$, and from there decipher the messages, but how can we do that ? okay so $n_1 = pq_1, n_2 = pq_2 , n_3 =pq_3$ , so on ... How do we get $p$

The question spezifies $n_1 = p*q_1$, $n_2 = p*q_2$. With that we can calculate $gcd(n_1,n_2) = p$ which lets us solve $n_1 / p = q_1$ and $n_2 / p = q_1$. Now we have every information needed to calculate the private part of Bob's key and thereby decrypt all messages sent to him.


Questions about the certificate authority procedures I am beginner in cryptography and now I try to understand certificate process.

I read this answer and have some questions about the enrollment process:

  The general procedure to issue certificates in a Public Key
  Infraestructure is moreless the following.

  1) the client generates a key pair, private and public

  2) the client generates a CSR (Certificate Signing Request) including
  attributes like Common Name and the Public key. Signs it with the
  private key and sends it to the server

  3) The server builds the X509 Certificate with the CSR data, sins it
  with the CA private key and returns the X509 to client

  4) the client stores the private key and the certificate in a KeyStore

It's not clear to me when client encrypt CSR (Certificate Signing Request) by client's private key and send to CA server ---> How the Server can read this CSR?
The CA server build X.509 and sign with CA private key. If I have client B, how client B get client A public key?
I wrote the code in Android to generate RSA key pair. Next step, what should I do to get certificate from CA server?
About CA server, I find two open source: OpenCA and EJBCA. What should I choose?

I am not clear about this. Thanks in advance.

 1. The answer cited states

  2) the client generates a CSR (Certificate Signing Request) including attributes like Common Name and the Public key. Signs it with the private key and sends it to the server

Notice that the client signs the CSR; the client does not encrypt the CSR. This leaves the data in the CSR (mostly, the public key and its attribute) in clear form, directly readable. The signature of the CSR can be verified against the public key in the CSR (this acts as a verification of consistency, and prevents an entity asserting that it generated the private key from pretending not having issued the CSR).

The CSR is defined in RFC 2986:

   CertificationRequest ::= SEQUENCE {
        certificationRequestInfo CertificationRequestInfo,
        signatureAlgorithm AlgorithmIdentifier{{ SignatureAlgorithms }},
        signature          BIT STRING
   }

The signature field is the RSA signature of the CertificationRequestInfo according to the AlgorithmIdentifier (which must be compatible with the type of key for which the certificate is requested from the CA). In the context of RSA, the big picture is that the CertificationRequestInfo is hashed, some padding is added (per RSASSA-PKCS1-v1_5 or RSASSA-PSS of PKCS#1), then the RSA private key function $x\to x^d\bmod N$ is applied to form the signature (with some conversions between integer and bytestring). Notice that signing uses the private key, which is usually kept private to the party asking for the certificate; and signature verification by the CA will use the public key for which it is asked the certificate, which is embedded in clear in CertificationRequestInfo. There is no encryption involved (RSA encryption uses a different padding, the public key for encryption, and the private key for decryption).

 2. The usual way for client B to obtains A's public key is to

obtain A's certificate (as issued to A by the CA server), usually from A, or from a public registry (not necessarily trusted).
check that certificate using the CA server's public key, assumed authentic/trusted,
extract A's public key from the certificate

 3. See point 2) in reference, cited above. The hard part is convincing the CA to issue the certificate, which typically requires proof of control of the domain(s) in the Common Name field.

 4. We don't do recommendations.


How can I break this encryption scheme? Let $p$ be a large public prime. Alice holds a private key $(e_1,d_1) \in Z_{p-1}^*$ such that $e_1 d_1 = 1 \mod {p-1}$. Bob also holds a different private key $(e_2,d_2)$ with the same property.

Let's say Alice wants to send a message $\large m \in Z_p^*$ to Bob:

$1.$ Alice computes and sends $\large m^{e_1} \mod p$ to Bob.
$2.$ Bob computes and sends $\large m^{e_1e_2} \mod p$ to Alice.
$3.$ Alice computes and sends $\large m^{e_1e_2d_1} = m^{e_2} \mod p $ to Bob.
$4.$ Bob decrypts by computing $\large m^{e_2d_2} = m \mod p$

Assuming Eve can read (but not modify) the messages exchanged between Alice and Bob, can she obtain any meaningful information about $\large m$ ? What happens if Alice and Bob use the same protocol to exchange multiple messages $\large m_1,m_2,...,m_t$ using the same private keys ?

This is the Shamir Three Pass protocol; it turns out the attacker can deduce some information about $m$; whether that information is meaningful depends on exactly what you are sensitive to.

Exactly what information is leaked turns out to depend on the factorization of $p-1$ (assuming, of course, that $p$ is large enough to make solving the discete problem infeasible); if $p-1$ has a factor $q$, the attacker can deduce the value of $m^{(p-1)/q}$ with $O(\sqrt{q})$ effort.  If $p$ is a strong prime, that is, if $(p-1)/2$ is also prime, then the only thing that is leaked is the value of $m^{(p-1)/2}$, that is, whether $m$ is a quadratic residue modulo $p$.

As for sending multiple messages $m_1, m_2, ..., m_t$ using the same private keys, well, if the messages are independent, we can show that there cannot be a weakness that reveals even one of the messages (the proof goes as follows: if there were something where, given $t$ independent exchanges $m_1, m_2, ..., m_t$, it has a nontrivial probability of giving us $m_i$ for some $i$; then we can take a single exchange and blind it $t$ times to generate $t$ independent looking exchanges; if our multi-exchanged weakness revealed one of the blinded messages, we can translate that back to the original message).  However, this proof technique relies on the messages being independent; if the messages had relationships between them, it is possible that the attacker could deduce that relationship (however, they still wouldn't be able to reconstruct the messages).


What is the practical impact of using System.Random which is not cryptographically random? I recently noticed a .NET software using PBKDF to derive an encryption key from a password string. This password string was dynamically generated using System.Random. Now, I know that System.Random is not really cryptographically random and should not be used for security purposes. Moreover, there are several flaws in .NET's implementation of System.Random.

But my question is this:

What is the practical impact of using System.Random to create a password string and deriving a key from it. Is it really possible for us to reproduce the key at a later time? Are there feasible attacks that will allow me to deduce the random string generated in this context with high probability? Or is it the kind of vulnerability that can only be exploited in specific "lab" conditions or scenarios?

You asked for the practical impact, so the answer is that for \$120 I could probably have your entire password database done by tomorrow.

Here is your program, or something similar to it:

using System;
using System.Text;
using System.Security.Cryptography;

class Program {
    static void Main(string[] args) {
        byte[] pwd = new byte[128];
        byte[] salt = Encoding.ASCII.GetBytes("saltsalt");

        var rand = new Random();
        rand.NextBytes(pwd);
        Rfc2898DeriveBytes k = new Rfc2898DeriveBytes(pwd, salt, 1000);
        Console.WriteLine(System.Convert.ToBase64String(k.GetBytes(16)));
    }
}

We should spend a bit of time talking about your salt. I've assumed it's fixed. You'd usually randomly generate it - if you use a single System.Random instance for both the salt and the password then the attack is basically the same. If you're creating two System.Random instances, one after the other, then you're unlikely to gain anything given how the default seed is generated. If your salt is based on an incrementing counter or usernames or something, what I'm about to say only really applies to attacking a single password rather than an entire database. You should still be concerned either way.

I compiled this and ran it on my own machine, and it gave me the key IDWrj6Fd9c4kqJ6A2FHDEg==.

Let's try and break it! System.Random is well-documented: https://docs.microsoft.com/en-us/dotnet/api/system.random.-ctor?view=netframework-4.8. It uses a 32 bit integer key, and in fact if the key is negative the docs tell us that it actually uses the key's absolute value for some reason. Handy! That's only 31 bits! Let's break it with this program:

using System;
using System.Text;
using System.Linq;
using System.Security.Cryptography;

class Program {
    static void Main(string[] args) {
        byte[] target = System.Convert.FromBase64String("IDWrj6Fd9c4kqJ6A2FHDEg==");
        byte[] pwd = new byte[128];
        byte[] salt = Encoding.ASCII.GetBytes("saltsalt");

        for (int i = 0; i < Int32.MaxValue; i++){
            if (i % 1024 == 0) {
                Console.WriteLine(i);
            }
            var rand = new Random(i);
            rand.NextBytes(pwd);
            Rfc2898DeriveBytes k = new Rfc2898DeriveBytes(pwd, salt, 1000);
            if (k.GetBytes(16).SequenceEqual(target)){
                Console.WriteLine("pwnt");
                Console.WriteLine(i);
                Environment.Exit(0);
            }
        }
    }
}

How long will this take to run?

dnSpy is a handy tool for reverse-engineering C# applications, and we can use it to take a look at what the default constructor for System.Random does. Yours might be different, but in mine an unseeded System.Random sets the seed to Environment.TickCount, which is the number of milliseconds that have passed since the computer was booted up. I don't leave my computer running for more than a couple of hours at a time, so Environment.TickCount is probably not going to be any bigger than 36,000,000. Watching the keys go by, I'm trying about 14,336 keys per minute. 36000000/14336 = 2511 minutes to try all the feasible keys, so it should finish within about 40 hours.

40 hours of a crappy C# program on a laptop is not secure at all. Even if you picked your seed better, 2147483648/14336 = 149796 minutes, so about 2,400 hours. I suppose I could spend some time re-writing my trash-tier C# program so that it runs faster - it's definitely really slow and can be improved massively - but I don't care enough about your passwords to do that. It's easier to just run a few thousand instances starting at different seeds for an hour each.

Amazon will sell me CPU hours at around \$0.05 per hour so it'd cost me \$120, plus a bit of time and faff writing the code and getting it on their servers, to crack your entire password database. Probably less, since my laptop is likely slower than their compute nodes.

Most of the time here is spent actually computing the PBKDF2 function. PBKDF2 is pretty great and you should still use it - it's designed to be slow precisely so that attacks like this are inefficient. The \$120 estimate is based on using 1,000 iterations in your PBKDF2, which takes a couple of milliseconds per hash on my machine. You could make this attack cost \$1200 by just tuning that parameter to 10,000 instead, though a determined attacker would still happily pay that to get their hands on your users' data. If you wanted this attack to cost me $1,200,000, you could use 10,000,000 iterations! You'd also be wasting a couple of hours every time you wanted a password. I don't know what your application is doing, but if it's spending all that time computing hashes then it'd probably make more money mining Bitcoin or something.

Basing your password scheme on non-cryptographic random number generator isn't a very good idea. Use this one instead: https://docs.microsoft.com/en-us/dotnet/api/system.security.cryptography.rngcryptoserviceprovider.getbytes?view=netframework-4.8. If you were to instead generate 128 bytes from a CSPRNG, then this kind of brute force would start costing me several quadrillion dollars of compute time, which is a few hundred times the GDP of the entire planet. No organisation has anything close to this level of compute power.


What vulnerabilities would open up if PGP authentication didn't have integrity checking? It is my understanding that PGP has both an integrity check and an authentication check. What vulnerabilities would open up if it didn't have that integrity check?

It seems like the authentication check is also basically an integrity check because the authentication would be a signature of the message. So if the message changed, the signature would be off.

Digital signatures provide authentication, data integrity and non-repudiation. Thus, you are right to say that the authentication check is also basically an integrity check. If it didn't have an integrity check (i.e. no digital signatures) then you cannot be sure that the message you received is the original and unmodified version sent by the claimed sender. But I think in this case, since the authentication is also provided by the signatures, if there is no integrity then you wont have authentication too.


How to convert AES to a PRNG in order to run NIST Statistical Test Suite? I want to run statistical tests on my implementation of AES. How should I convert it into a PRNG? Is there a standard way to go about doing this? I could not find much information about this although this was done by NIST while during the selection of AES back in the days.

The answer is simple. AES is in itself a pseudorandom function, so an output from a single block encryption will produce 128-bits of pseudorandom numbers.

Now to use AES to generate longer sequences, you will have to use a block-cipher mode that lets you do the same.

Here is a small list of a few very popular modes ment for PRNGs:

Counter(CTR): Counter mode turns a block cipher into a synchronous stream cipher. It requires an IV or nonce which is combined with a counter and encrypted with a block cipher. The counter can be any non repeating function, however a simple increment by one is secure enough, and not to mention, the most efficient.

Output Feedback (OFB): This also turns a block cipher into a synchronous stream cipher. It starts encryption with an IV, and operates by encrypting the previous block.

Cipher Feedback (CFB): This one converts a block cipher into a self-synchronous stream cipher. It starts with an IV, XORs the output to get the first ciphertext block, and uses every previous ciphertext block as the next IV.

You could also use other modes too, but they might not be well suited for use in stream ciphers, so they will be slow. Otherwise, the ultimate answer to your question is to use a secure block cipher mode. And, not to mention, they work well with hash functions as well.


SVP algorithms and complexity I took  image from Simons Institute's presentation. Complexity classes of Approximate SVP problem according to approximation factors are given in the table. My question is, What is the meaning of blue arrow -Crypto- in this picture?

Lattice-based cryptography is based on the hardness of certain lattice problems (almost tautologically). The region marked "crypto" denotes the region of approximation factors $\gamma$ such that:

We know how to construct cryptographic primitives assuming the hardness of $\mathsf{SVP}_\gamma$
It is plausible that $\mathsf{SVP}_\gamma$ is hard (as there are not known poly-time algorithms).


Algebraic structures in RSA Why do we need a field for RSA and what are the two operations in this field?
Why can't we have a ring or group for example? Because in a group you also have inverse elements.

RSA is not done over field. When using RSA, you rely on the fact that the adversary does not know the order of the multiplicative group, i.e. he does not known the value of Euler's totient function and he is unable to compute it.

Over field, computing it is trivial.


Encryting data with password for local storage using libsodium I want to encrypt data that is stored on the hard disk using a user-entered password. For this I look into the sodium docs and all I can find for symmetric encryption is authenticated encryption.

This method requires a "nonce" which is needed again in decryption. If I understand correctly, nonces are important for communication, but for my case they are not needed. Correct?

Also to generate a key from the user entered password requires salt, which must be the same every time.

Is authenticated encryption really the correct choice for my task? If yes, how should I handle the nonce?
How should I handle the salt for generating the key? Should I always use the same? Or where should I store it?

A nonce ensures that the same plaintext will always be mapped to different ciphertexts using the same key. Schemes requiring a nonce should always get a nonce, even for file-encryption you can't guarantee that your users won't encrypt the very same file twice, for reasons only known to them.

Now to answer your questions:

Authenticated encryption (AE) is always the mode of choice, except for full-disk encryption (FDE), where you'd have a severe penalty. But as you don't do FDE, AE is the right choice for you.
Regarding the nonce, you have several possibilities.

You can store it in plain before your file.
You can use your password based key derivation function (PBKDF) to derive the nonce in the same call as you derive the key.
(not recommended) You could hold it constant, assuming the key is different each time.
(not recommended) You could increment it always, but generating at random is easier concerning management I'd say.

Using a different salt each time won't hurt you, but reusing the salt may hurt you, so don't reuse salts. Using always the same salt may end up in same keys (as soon as a user supplies the same password twice) and salting is used to prevent "known-hash" attacks, which in fact fails it purpose if you reuse the salt and an attacker can simply try pre-calculated values. So use a different (unpredictable) salt in each case.
Where should you store the salt? The salt don't need to be secret, so you can store it in plain at the beginning of the file.


How is wpa2 authentication structured I would like to understand the cryptography behind Wpa2. As far as I know, there are 4 messages on the 4-way handshake and three of them are values concatenated with hashes.
First, I am trying to understand how the PTK is generated. I believe that it is:

H(an||stn||amac||stmac||PSK)

Where "h" function is sha1, "an" is the ap nonce, "stn" is the client nonce, "amac" is ap's mac address, "stmac" is client's Mac address and PSK is the shared key,
But I might be totally wrong.
Second, the second message on the handshake is

Stn || H(an || KCK)

Right?
My question is if it is the way I wrote or it is different.

Thanks in advance

In pairwise key hierarchy there are two root keys: pre-shared key (PSK) and Authentication, Authorization, and Accounting Key (AAAK). From these two keys pairwise master key (PMK) is derived. In the case of PSK, PMK is equal to PSK. In other case, PMK is obtained by taking the first 256 bits of AAAK. Now, to the question about generating pairwise transient key (PTK).

PTK is generated from PMK by using pseudorandom function (PRF) which is based on HMAC-SHA-1. The formula will be: PTK=PRF(PMK, X, an||stn||amac||stmac). Where X is the parameter indicating the length of PTK. Note that, in CCMP X=384 bits, whereas in TKIP X=512 bits.

Unfortunately, I'll not be able to answer your second question. If nobody else will reply, I'll do it later. The good reference is this document IEEE802.11i-2004


Cheating in a commitment scheme based on discrete log Question:

Consider the following commitment scheme:
Public parameters: large primes $q$ and $p$ such that $p = 2\cdot q + 1$, and two generators $g, g'$ of a $q$-order subgroup of $\mathbb Z_p^*$.

Alice commits to $t$ in $\mathbb Z_q$ by uniformly picking $r$ from $\mathbb Z_q$, and sending $g^t \cdot g'^r$.
She opens the commitment by sending $s$ and $r$.
Suppose both parties are poly-time bounded.
If Bob gets to pick the public parameters, can he somehow cheat? (Alice verifies the parameters in poly time)

Attempted solution:

If he can cheat, I think Bob needs to choose $q$ and $p$ in a smart way, because even if he picks $g$ and $g'$ to be equal, he is stuck with computing discrete log, which isn't possible in poly-time.

I thought maybe Bob can pick $q$ to be a Carmichael number, then Alice will think it is actually prime (by checking with Miller–Rabin algorithm).

Two problem I ran into with this:

I'm not sure how much it helps him to solve the problem — he can solve it modulo the prime factors of $q$ and use CRT, but if the factors aren't small enough its still exponential.
Maybe there is no prime $p$ such that $p=2q+1$ for a Carmichael number $q$.

I think my solution fails because of the problems above... would appreciate a pointer in the right direction.

Assuming that Alice verifies that:

$p = 2q + 1$ with $p, q$ prime
$g, g'$ are generators of order $q$

then Bob cannot cheat.

First note that $g$ and $g'$ generate the same subgroup, such that $g' = g^\alpha$ for some integer $\alpha$. Given a signature value $s = g^t g'^r = g^{t + \alpha r}$, there are $q$ possible messages $t' \bmod q$, and for every $t'$ there exists a unique value $r' \bmod q$ such that

$$r' \equiv \frac{t - t' + \alpha r}{\alpha} \pmod q$$

and:

$$g^tg'^r \equiv g^{t'}g'^{r'} \pmod p$$

Without further knowledge of $t$ or $r$, every pair $(t', r')$ that satisfies the signature is equally likely. So if Bob only knows $(p, q, g, g', s)$, he cannot deduce any information from the signature.

Note that if Alice knows $\alpha$, she can cheat by calculating $r'$ for any message $t'$ and revealing $(t', r')$ instead of $(t, r)$.


KFB mode - key feedback Please, could someone explain to me how the Key feedback mode (KFB) mode works and what the IV in output block stands for? And what properties does the "constant input" has to provide? Should it be random / unpredictable / fixed ?

Then it's encrypted with $K$ which is previous output and then it's xored with the plaintext. So the IV is there to encrypt the first block I suppose. Is that its function?

The KFB mode of operation graphic from Wikipedia:

Section 2.4.1 of the KFB specs (NIST) isn’t really any help either:

The output of the block cipher is used as the new key, and also passed to the "output block" function, which is referenced in the NIST document as $B^m_R$.

The purpose of the IV $R$ and the function $B^m_R$ is to reduce the output to a smaller size in a manner that hides the true output of $f$. Too large an output allows key recovery.

The output of this function is an $m$-bit value, which is then used to build the keystream. The inputs are $R$ and the $n$-bit output of the block cipher. $R$ is a binary $m \times n$ matrix, and is multiplied against the block cipher output modulo 2 arranged as an $n \times 1$ matrix, resulting in a matrix of $m \times 1$ bits, which is used for the output.

An example of this uses the following:

$f = $ AES-128
$n = 128$
$m = 8$

$R$ would be an $8 \times 128$ matrix and require 128 bytes to build, and when multiplied against the 128-bit output of AES, would result in 8 bits of data (1 byte) for the keystream. $R$ must be unique to each message, and must be random and non-zero, but does not need to be secret. It can be built using a smaller amount of bits using appropriate methods (such as HKDF), as long as at least $n$ bits are used to generate it.

The constant input $p$ does not have any special requirement and is generally some constant, possibly even all 0 bits.

It is obvious that with a small output and the need to perform the key schedule for every iteration, the efficiency of KFB is very low, and thus it is generally not used for practical applications, despite the provable security bounds.

I assume a partial key feedback mode could be made using AES-256 with 128 of the key bits fixed, and the rest fed back from the output, or using some kind of shift mechanism.


Why do the messages in IND-CPA have to be of same length I understand the general idea of IND-CPA, however I fail to understand why the messages the adversary chooses have to be of same length. I guess that with variable length messages there would always exist a successful attack and therefore CPA security would not exist. Can anyone guide me into a direction on how such an attack would look like?

Here is an outline of such a distinguisher would work; if you submit a one byte plaintext, then the resulting ciphertext length will follow some probability distribution (with many ciphers, it will be one fixed length; we'll consider the more general case where it is probabilistic); for this probability distribution, we'll have some $N$ where the probability of the length being less than $N$ is $\ge 0.75$.

So, we submit two plaintexts; one consisting of 1 byte, and the other consisting of $N+1$ random bytes.  If the ciphertext corresponds to the short plaintext, the ciphertext will be of length $< N$ with probability $> 0.75$; if the ciphertext consists to the long plaintext, the ciphertext will be of length $< N$ with probability at most $\frac{1}{256}$ (can be shown by the pigeon-hole principle); hence just looking at the length of the ciphertext can serve as the distinguisher.

Obviously, one way to get around this approach would be to pad out all encrypted messages to a fixed length (and have an arbitrary length bound on plaintexts).  However, this sort of thing is expensive in practice; the leaking of the plaintext length is generally considered acceptable.


Determining a cryptographic algorithm by description I found a signing algorithm while analyzing obfuscated source code.

I only have a basic knowledge about cryptography.  I want any clue that can help me to figure out if is a known and named cryptographic algorithm or a variant, if is strong and breakable, or how the signer generates the signature.

The point is if this is a case of an unbreakable algorithm stop and not try anything, or continue my work trying to break.

The Algorithm:

Having $\mathit{message}$ and $\mathit{signature}$ clearly separated in a file:

First calculate a $\mathit{message\_digest}$:

$\mathit{message\_digest} = \mathrm{padding} \mathop\Vert \operatorname{SHA-1}(\mathit{message})$

Where
$\mathrm{padding} = 0001 \mathop\Vert \mathrm{ff}(105\ \mathrm{times}) \mathop\Vert 00 = $
0001FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00

And then check if this expression is true:

$\mathit{signature}^3 \equiv \mathit{message\_digest} \pmod{\mathit{key}}$

Where $\mathit{key} =$
C01D9FD2747B89681255F0C934610183CB45E2C57E511DBB4D651D2AD1F9B4E91D31169D3D444F91074A8EAF3F688EEC9E0E5E76F52CAF61A6ECC4A5A2154997755754E68D7C6BC1EE9C2B64B03C3157E83242A8AA8311371354363FAE8D0D5C843CEB0844FB2C3C499E1C41313A729000550038363AEF2BF8E20346B36C6B65

I have also found the follow signed message in the source code that I analise:

For a message that i know  with $\mathit{message\_digest} = $
1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF008CBB319AB06BA3F4E05625984ED2D89E42C51813

The $\mathit{signature}\ =$
5D3C1672CC314D8E50D302790D3BE9FB0CC5286A0D050BD83EA920B0F90C8E86A95E471CD34C3F81DDA89A14DE03781266F623975BD8B9CB95608EAFDE8426A7E0AEFA60DD80E76A652397D466674E439EADB30103F9A15F4EE6022DFCB8D36CBFABE1D922BBE5C7011242AE5DBAB7A35BF7C970BB1B45563176A5CFE3CBC23A

It's RSA signature validation, using the PKCS-1.5 signature padding, with $e=3$, and the RSA modulus given by $\mathit{key}$.

It's a circa 1024 bit key; assuming $\mathit{key}$ is a properly chosen RSA modulus, nowadays it would be considered potentially breakable (in the sense that you could recover the private key, and hence be able to sign any message you want), however it would be a major effort.

If you're asking whether you can trust it, well, probably not; a well funded adversary could likely break it.  If you're asking whether you can break it, well, no; you're not a well funded adversary.


Is HTTPS encryption using the RSA algorithm? According to this article HTTPS and RSA is the same thing: https://tiptopsecurity.com/how-does-https-work-rsa-encryption-explained/

From other sources I learn that they are both asymmetric encryption methods.

What is the difference between the two?

What is the difference between the two?

That question feels like the question "what is the difference between a truck and an 8 cylinder engine?"

They are different, in the sense that they serve different goals.  HTTPS may use RSA (just like a truck may use an 8 cylinder engine), however HTTPS has a lot more to it (just like a truck consists of a lot more than the engine).

RSA is a cryptographical primitive; it can be used to implement public key encryption (as the page mentions); that is, someone can have a public key (which they can distribute); anyone can use that public key to encrypt messages that only the holder of the private key can read.  RSA can also implement signatures; someone with the private key can 'sign' messages, and anyone with the public key can verify that that message was 'signed'.

HTTPS is a cryptographical protocol; in particular, it tries to be a method of implementing security for transit HTTP traffic.  It makes sure that the HTTP traffic you get is actually from the web server you think it is, and that no one can read it or modify it in transit.  It can use RSA as one of the cryptographical primitives it relies on, but it doesn't have to (actually, the current trend is to get away from RSA public key encryption in favor of other primitives).  In addition, it also relies on other cryptographical primitives as well.


Hash function without avalanche effect but with few collisions I am searching for a hash function which has these attributes:

low Avalanche Effect, similiar files should get similiar outputs
low number of collisions (if I have 0*10000 in one file, and 0*99999 + 1 in another the hash should differ and should not collide to easily)

The use case is "bruteforcing" a file hashed by the function, so I give a input file of 0*10000 and then bruteforce the input file.

By reducing the avalanche effect I hope that I can speed up the process by analyzing the difference (fc5e038d38a57032085441e7fe7010b0 is the output hash of the original file and as my bruteforce gets near the original file the hash should have less and less difference like fc5e038d38a57032085441e7XXXXXXX)

Is this even mathematically possible? Wouldn't a hash with these properties lead to a ton of collisions especially when I bruteforce it?

Sure. The probability of collisions depends on:

How your symbols in the messages are distributed: Do messages have particular structure? Do some elements occur more often than the others?
How long the hash code is.
The structure of the hash code algorithm itself: Does it produce some hash codes more often than the others?

If all symbols are equally distributed and algorithm produces hash codes that are also equally distributed, then collision depends only on the hash code length. If hash code length is 512 bits, then the collision probability (with above mentioned assumptions) is $2^{-512}$.

The simplest function that fits your requirements is following:

hash(M) = M mod 2^512

If fits your requirements fully. To calculate it, you only need the last 64 bytes of the message. It means it is extremely fast. And the collision rate is the same as that of SHA-512.

If it is extremely fast, why nobody uses it? Namely because of your requirements: If has no avalanche effect. Hash codes are used normally to detect changes in the message. If there is no avalanche effect, changes will not be detected (in my example changes will be detected only in the last 64 bytes of the message, not in the previous bytes). I'm wondering for what purpose would you use such hash code.

To brute-forcing: If you exclude the avalanche effect, it means you will use only small part of the message to create the hash code. This means that also an attacker will consider only a small part of the message to brute-force. Means, brute-forcing will pretty easy.


What issues are there while using Linux's /dev/urandom for generating cryptographic keys? As of Linux 5.1 the /dev/random no longer uses the blocking pool. There is a talk about the change on the page Removing the Linux /dev/random blocking pool

I believe that Linux's blocking pool has outlived its usefulness. Linux's CRNG generates output that is good enough to use even for key generation. The blocking pool is not stronger in any material way, and keeping it around requires a lot of infrastructure of dubious value.

This series should not break any existing programs. /dev/urandom is unchanged. /dev/random will still block just after booting, but it will block less than it used to. getentropy() with existing flags will return output that is, for practical purposes, just as strong as before.

Lutomirski noted that there is still the open question of whether the kernel should provide so-called "true random numbers", which is, to a certain extent, what the blocking pool was meant to do. He can only see one reason to do so: "compliance with government standards". He suggested that if the kernel were to provide that, it should be done through an entirely different interface—or be punted to user space by providing a way for it to extract raw event samples that could be used to create such a blocking pool.

and later

For cryptographers and others who really need a TRNG, Ts'o is also in favor of providing them a way to collect their own entropy in user space to use as they see fit. Entropy collection is not something that the kernel can reliably do on all of the different hardware that it supports, nor can it estimate the amount of entropy provided by the different sources, he said. (The bolds are mine)

So, what issues are there while using Linux's /dev/urandom for generating cryptographic keys?

Using /dev/urandom to generate cryptographic keys or secrets can be an issue when the state of the OS is not unique. This is the typically case when a VM was just booted from a template: the state of the CSPRNG could be shared among multiple VMs. In cases similar to this one, it is important to use /dev/random or getrandom() instead of /dev/urandom, so that the output of the CSPRNG blocks until it has collected enough entropy.
Of course, VM clones need to be rebooted or booted up from a shutdown state in order for the entropy count to be reset to zero.
The output of /dev/urandom and /dev/random comes from ChaCha20. To consider it insecure to create cryptographic keys once the inner state of ChaCha20 is initialized with enough entropy, one has to either:

know the inner state of ChaCha20,
or break the ChaCha20 cipher, which is today considered one of the most secure ones.

The remaining issue is how to count entropy. The Linux kernel is extremely conservative on this point, and the inner state of the CSPRNG most likely have far more entropy than counted (around two orders of magnitude more). However, to count it exactly is mathematically impossible.
Disclaimer: This answer is valid for the Linux kernel from version 4.8 to  version 5.9, which is the latest version at the time of writing of this answer. The Linux CSPRNG was heavily refactored in versions 4.8 (introduction of the ChaCha20 cipher) and in version 5.6 (simplification of the architecture), with minor changes introduced in version 4.17 and along the way.


Length of ElGamal signature compared to RSA signature In his original work (1) on the ElGamal encryption and signature scheme Taher ElGamal states in chapter V. section B.:

  For  the  signature  scheme  using  the  above  arguments  for   the
  sizes of the numbers in our system and the RSA system,  the  signature
  is  double  the  size  of  the  document.  Then  the   size  of  the
  signature  is  the  same  size  as  that  needed  for  the   RSA
  scheme, and half the size of the signature for the new
  signature scheme that depends on quadratic forms [...]

However, I was under the impression that (schoolbook) RSA signatures have roughly the same length as the corresponding modulo n, while ElGamal signatures are roughly twice the size of their corresponding modulo p.

Could somebody please clarify?

Mistakes happen.

The author's scheme adds a signature about twice as large as $p$, when RSA signature (of the textbook variety of the reference) adds a signature about as large as $n$. It is clearly assumed that the public prime modulus $p$ is about the size of the RSA public composite moduli $n$.It follows that the size of the signature in the proposed scheme is twice that in RSA.


Diffie–Hellman key exchange, why it's hard to break it? I'm a bit confused why it's hard to break Diffie–Hellman

Let's take the example

ALICE has G, a, and n

BOB had G, b and n

Eve (the third party) succeded to intercept G, n, $G^a,  G^b$

ALICE generate the key G^(ab) mod n

BOB generate same key G^ba mod n

What I don't understand is why Eve cant' get a or b by knowing G^a and G^b.?

For me he can just use dichotomy:

Eve will take a random number r_a.

    if G^r_a$ < G^a /* already known */
        increase(r_a); /* by power ietration for example, +1 +100, +1000, +10000 */
    else
        decrease(r_a);
    adjust(r_a);

The straight-forward method you outlined doesn't work, because $G^a$ is not monotonic in $a$; we can have $G^{r_a} < G^a$ even though $r_a > a$.  This happens because we're working modulo $n$, rather than doing exponentiation in the real numbers or integers.

For example, if we have $n=101$ and $G=2$ (for a toy example), then we have:

$$G^8 = 54 > G^{10} = 14$$

even though $8 < 10$

In fact, a practical method for doing probabilistic [1] evaluation of whether $a < b$ given $G^a \bmod n, G^b \bmod n$ (for the values of $n$ we actually use in cryptography) would be of great interest (and would essentially break all crypto based on modular exponentation)

[1] By probabilistic evaluation, I mean that the method doesn't have to give us the correct answer in all cases; it would be sufficient if it was correct with some probability somewhat more than 0.5


Generate a unique 64 bit numeric database key without collisions at $2^{32}$ birthday threshold? What is the best way to generate a unique 64 bit numeric database key from a string?

For example: if the string is a URL, you could generate a 64 bit key using SipHash or by truncating a SHA256 hash to 64 bits, but collisions are likely at $2^{32}$ (~ 4 billion) entries.

However, if instead you truncated the hash to (64 bits - X bits), and concatenated the resulting hash with the first X bits of the input string, you would reduce the chance of collisions since two similar strings are unlikely to produce the same hash code:

key_bits = 64
x_bits = 8
hash_code = sha256(url_string)
key = truncate(hash_code, key_bits - x_bits) + truncate(url_string, x_bits)

Is this correct? Is there a better way?

Unfortunately, without some additional assumptions about the strings (e.g. that the first 8 bytes are unique), there is no way to reduce the chance of collision below the usual chance levels.  If you need unique 64-bit ids, the options are:

Do a database lookup when generating keys and pick another key if it is already in use (you state that you want to avoid this).
Ignore duplicate keys, e.g. set things up so that only one of the two entries is kept.  As long as you don't go much above $2^{32}$ entries, the expected number of collisions will be very low, and depending on your task, it may be acceptable to ignore a small fraction of the entries.


Plausible Deniability in Schnorr How does a dishonest verifier affect plausible deniability of the interactive Schnorr protocol?

A dishonest verifier does not need to sample the challenge randomly. What if he just computes it as the evaluation of a one-way function on let's say a string "Alice authenticated, it's true". Later it can publish the string and the description of the function. What does this say about the deniability of the transcript of the protocol? Guess that should be sufficient to figure out the details on your own.


How can a lattice attack be applied to ECDSA signatures? The aim is to check if it is possible to break the ECDSA cryptosystem under the following criteria.

Suppose that each ECDSA signature is generated by using the GLV method for point multiplication (the random nonce $k$ used in each signature is decomposed into $k_1$and $k_2$).
For every ECDSA signature, I can obtain few bits (least significant bits, most significant bits, ...) of the respective $k_1$ and $k_2$.

Is it possible to carry out a lattice attack to gain the value of the underlying secret key ($\alpha$)? If yes, then can you explain the attack in detail?

PS: I have a beginner level understanding of ECDSA and lattices.

Sure you can do. There are many lattice attacks, using your second assumption, to ECDSA (which also applied to DSA). For instance see  Smart and Howgrave-Graham and Shparlinski and Nguyen. All the lattice attacks base on finding small solutions (for the ephemeral key $k$ and the private key $a$) to the signing equation $sk-ra\equiv H(m)\pmod q.$ If you have enough signatures (i.e. enough $k_i$) then you construct a linear system $\bmod q$ and then a suitable lattice and if you have enough bits from every $k_i$ and $a$ and enough messages you can solve the CVP problem. Also you can apply Coppersmith method to the signing equation.


Of what use is my code for finding prime numbers of a certain size? I've developed a bit of Mathematica code that can find primes within a range of numbers. For example, if I wanted all the primes between one million and two million, it could do that. Of what use is this code I invented ?

The only thing I could think of was that if one wanted to find two primes of a certain size for cryptography keys.

And the code could be used to test a specific number for primality, quickly.

And with the addition of code, it could be made to search for primes of a certain format, like safe primes.

I just invented this last week

Copy the following into Mathematica, select all, right-click on Convert To, choose StandardForm.

N[Sum[2/10^((n*(Floor[c/n] + 1) - c)*s), {n, 1, Floor[Sqrt[ c]]}] + Sum[ 2/(10^((n*(Floor[c/n] + 1) - c)*s)* (10^(ns) - 1)), {n, 1, Floor[Sqrt[ c]]}] + Sum[2/(10^((o^2 - o - c) s)*(10^(o*s) - 1)), {o, Floor[Sqrt[c]] + 1, max}], ((max + 1)^2 - c)*s]; AbsoluteTiming[Flatten[ Position[Partition[ RealDigits[%][[1]], s, s, -1], {(0) .., 2}]]] + c
-end
c=crossover s=spacing

The crossover is the number which you want to surpass. The spacing is difficult to determine, so I'll say that in general, if you use a number which is equal to the number of digits of the max^2, you should be safe. So for all primes up to $100^2 = 10000$, that is five digits, so use a 5 for the spacing. Follow this rule and you should be safe.

For those who are wondering, the code is based on a bigger structure of numbers formed by the Sieve of Eratosthenes.

I'm sorry to say that your code is likely to have essentially zero use.

Primes used for cryptography (e.g., RSA), are on the order of 2,048 and 4,096 bits of length, or respectively roughly 616 and 1,233 digits long. Algorithms already exist to rapidly find (random) primes of this size, and unless you've broken new ground in number theory, your approach is slower.

Additionally, the general trend lately is moving away from systems like RSA towards elliptic-curve based cryptosystems which have no need for the generation of primes.


A hash function for sets that from a hash of a set and a subset of it doesn't reveal the hash of the remaining elements in the set I'm looking for a function to compute a hash of a set.

It needs to satisfy two properties:

If someone published a hash $h(S)$ of a set $S$ and a hash $h(S')$ of some subset $S' \subset S$ of it, I should not be able to compute the hash of $S \setminus S'$ from $h(S)$ and $h(S')$.
From the hashes $h(S_1)$ and $h(S_2)$ of two disjoint sets $S_1$ and $S_2$, I should be able to compute the hash $h(S)$ of their union $S = S_1 \cup S_2$.

Does such a hash function exist?

Here is an idea which mostly addresses what you appear to want; I'm not happy with it, however I thought I'd share it just in case.

Our 'hashes' are vectors of $n$ elements, each element being either a number between 0 and $p-1$, or the special symbol $\bot$.

The hash of a singleton element $s$ (that is, a set that consists of a single element) is computed by selecting the $n$ elements to be numbers deterministically (e.g. using the bits from SHAKE(s)), and then selecting $b$ of the $n$ indicies (again, deterministically), and setting each of those $b$ indicies to $\bot$.

And, to combine two hashes (using Ilmari's notation, to compute $c = a \otimes b$), you perform the following operation element-wise to the two hashes):

$c_i = \bot$ if $a_i = \bot$ or $b_i = \bot$

Otherwise, $c_i = a_i + b_i \bmod p$

It should be obvious that the above operator is both associative and commutative.

And, assuming $p, n, b$ are properly set, then given $a \otimes b$ and $a$, it should be highly probable that $b$ cannot be recovered (as there is likely be to some element $i$ in $a$ for which you have $a_i = \bot$ and $b_i \ne \bot$; in that case, you have no information on $b_i$, and so any of the $n$ possible values are equiprobable.

Of course, the hashes are quite large, and this noninvertability is only probable (and even that is true only if the sets $a, b$ are not too large).


Is this is a secure use of AES-CTR? Here is a hypothetical application of AES-CTR encryption.

Encryption:

Step 1: Generate random key and IV for new object;
Step 2: Use said key and iv to encrypt some data, which is then
stored on a content server;
Step 3: Encrypt key and IV using some secret master key, and store
the wrapped keys in a database table.

Important: For each new object that we want to encrypt, a new key and IV are randomly generated.

Decryption:

Step 1: Retrieve encrypted key and IV relevant to object that we want
to decrypt
Step 2: Decrypt key and IV using master key
Step 3: Use decrypted key and IV to decrypt object

I would like to know if this is an acceptable way to proceed with AES-CTR (assuming the master key is handled securely, and we are also hashing content to ensure integrity)?

If not, could you please suggest a more secure way to manage key and iv for a given object?

Yes this seems secure.

Note that for CTR we use a nonce not an IV but it has similar role. Depending on your operational requirements there may be simpler secure methods. The key question is how the shared secret is managed, of course.


Simple message authentication code I used to figure that message authentication codes function like digital signatures: a hash of a message is calculated and then encrypted with a secret key. To verify the authenticity of a message, the recipient calculates the hash of the message, decrypts the MAC with the secret key, and compares the two. I have not seen a single MAC that works like this. Is this insecure?

Actually, there are Carter-Wegman MACs that work like this; of course, there the "hash" function is not a cryptographical hash function, but instead it is an almost-universal hash (with a key).

If we replace this almost-universal hash, well, we run into some potential problems.

The first one is the malleability of some encryption methods.  If we were to use, say, counter mode, then it would be easy to modify the message arbitrarily.  All one would need to do is compute the hashes of both the original message, and the modified one, and xor in both to the encrypted MAC; this modified MAC would decrypt to the hash of the modified message.  Carter-Wegman MACs don't run into this problem, because we assume that an attacker cannot compute the almost-universal hash function (because they don't have the key).

One way to attempt to get around this problem is simply use ECB mode, and encrypt only one block -- that is certainly not malleable.  This runs into the second potential problem -- hash collisions.  If we use only 128 bits of the hash, someone can find two plaintexts that share those 128 bits, obtain the MAC for one, and then he has found a valid MAC for the other message.  While clearly this isn't as severe as the first problem (where the attacker can generate a valid MAC for any message), it's still enough for us to be wary of this.  Again, Carter-Wegman MACs don't run into this problem.

So, it can potentially work; however we need to choose our encryption method carefully.


Diffie-Hellman secret key choices I'm trying to understand why the secret keys used by Alice and Bob in Diffie-Hellman are $a,b ∈ ℤ∗p$.

Say $a$ is $p - 1$, wouldn't the transmitted $g^a$ be 1 mod $p$ by $FLT$? Now anytime a passive listener sees a 1 being transmitted would know one of the secret keys and could easily compute the message. I'm sure I'm missing something obvious but I can't figure it out.

The "obvious" (it really isn't that obvious) thing you are missing is: The same reasoning could be applied to literally any other private key! There is nothing special about $a=\lvert(\mathbb Z/p\mathbb Z)^\times\rvert=p-1$ (which would, by the way, more commonly be represented as $0$ modulo itself), except that checking for it is particularly easy. For instance, if an attacker suspects that your private key is $42$, they can simply compute $g^{42}\bmod p$ and compare it to the public key $g^a\bmod p$ you transmitted. Does this imply that $42$ is a weak private key?

The reason why Diffie-Hellman (and in fact, similar fallacies apply to any cryptosystem) can still be secure is that the probability of each single key occurring is negligible. An attacker can test whether your private key equals something, but it takes a certain amount of time (a bit less for $a=0$, but still). When the set of possible keys is reasonably large, the attacker can't search through a meaningful subset of in their lifetime, hence they will, with overwhelming probability, not be able to guess the correct private key.


Cryptographic function that can 'pack' numbers Is there a cryptographic algorithm that can 'pack' a bunch of strings/numbers and "confirm" if a string/numbers exists (later in the code) while keeping the output hidden?

For example, I have algorithm X, to which I can run something like:

// From Alice's side
algo1 = new X(key);

algo1.pack(100)
algo1.pack(200)
algo1.pack(300)

algo1.finalize()
print(algo1.output) // Prints a bunch of random bytes

//Later, somewhere in Bob's code
algo2 = new X(key, algo1.output);

algo2.has(111) // false
algo2.has(222) // false
algo2.has(100) // true
algo2.has(200) // true

I do realize this can be done with an encrypted database, but I am searching for a solution in an algorithm.

The purpose is data hiding: in case algo1.output as well as key are revealed to an attacker, they would still have to know the values in the set to get a truthful answer (100, 200 and 300 in the case above), which would protect the integrity of those values, even if the key and algo1.output are revealed

They would then have to rely on brute-force methods to extract those values, which could make it expensive for the attacker.

It seems we can use commitment schemes with homomorphic hiding and binding properties here. Often these commitment schemes are used for secure multiparty computation, and zero knowledge proof generation purposes.
A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value (or chosen statement) while keeping it hidden to others, with the ability to reveal the committed value later. Commitment schemes are designed so that a party cannot change the value or statement after they have committed to it: that is, commitment schemes are binding.
Commitment schemes are a way for one counterparty to commit to a value such that the value committed remains private, but can be revealed at a later time when the committing party divulges a necessary parameter of the commitment process. Strong commitment schemes must be both information hiding and computationally binding.
There are different types of commitment schemes.Pedersen commitment scheme is a popular one. There are other approaches such as Polynomial commitment schemes as well.
EDIT based on Comments
The purpose of commitment scheme here would be to commit on the existence of a number ( a packed number ) and then keeping the output hidden until there is a requirement for revealing it. An algorithm for packing the numbers can be implemented using arithmetic circuits, functional encryption etc. The advantage of secure multi-party computation will be to delegate the packing operation to multiple parties and aggregating the result of the operations. This is the perspective on recommending commitment schemes and multi-party computation.


Reduction to cdp,dl or cdh? Assuming a randomize encoding scheme that takes as input a secret key $\mathsf{sk} \in \mathbb{Z}_p$ for a large prime number $p$. Then the algorithm outputs $g^{\mathsf{sk}x}, x \in \mathbb{Z}_p^*$. Analyzing the privacy of the scheme where we can reduce its security for dinstinguishing encodings of $x$ based on an indistinguishability based definition?

Actually, the algorithm is distinguishable.

Let us assume that the attacker has two input, output pairs $(x, fx), (y, fy)$.  Then, he can test whether $fy^x = fx^y$.  If $fx = g^{sk\cdot x}$ and $fy = g^{sk\cdot y}$, this test will succeed, as $fy^x = g^{sk\cdot y \cdot x} = g^{sk\cdot x \cdot y} = fx^y$.

Furthermore, given $x$ and $g^{sk \cdot x}$, the attacker can (with nontrivial probability) recover $g^{sk}$.  The nontrivial probability is that whether $x^{-1} \bmod p-1$ exists; if it does, then $g^{sk} = (g^{sk \cdot x})^{x^{-1}}$.  The attacker can use that to evaluate the function for any input.

The above assumes that the attacker knows $p$.  Even if he doesn't, he can still practically distinguish (and recover $p$) if the sets he was given had inputs there were either

Small, for example, if the inputs $x, y, z$ are sufficiently small that the attacker can compute $\gcd(fy^x-fx^y, fz^x-fx^z)$
Related (e.g. $x, 2x, 4x$ with the corresponding outputs).


Basic attacks on McEliece; finding S and P Take a McEliece cryptosystem with public generator matrix $G' = S G P$ where $G$ is a generator of a secret code with known fast decoding (not necessarily a Goppa code over $\mathbb{F}_2$), $S$ is random & non-singular and $P$ is a permutation.

Let's say an attacker Eve has a way to find $G$ from $G'$ but not $S$ or $P$. How would Eve now continue the attack on a encrypted codeword $c = mSGP+e$?

There are ways to find $P$, if you know $SG$: Support splitting algorithm, but I don't see how Eve can continue without $S$.

Clarification / Example / Thoughts from previous answers

One of the problems is, that $P$ changes the code enough already, that it will be hard to decode. This is an example over $\mathbb{F}_2$

$G:=\left( \begin{eqnarray} 1 & 1 & 0 & 0 & 1 \\ 0 & 0  & 1 & 1 & 1 \end{eqnarray} \right)$ generates the code
$\mathcal{C} = \mathbb{F}_2^2G= \left\{ (0,0,0,0,0),(1,1,0,0,1),(0,0,1,1,1),(1,1,1,1,0) \right\}$.
Take the permutation that switches the 2nd and 3rd component
$P = (23)$.

The generator $GP$ now generates the code
$\mathcal{C}P = \left\{ (0,0,0,0,0),(1,0,1,0,1),(0,1,0,1,1),(1,1,1,1,0) \right\}$.

Take a codeword in $\mathcal{C}P$:
$c = (1,0,1,0,1) \in \mathcal{C}P$ and an error vector $e=(1,0,0,0,0)$.

$y=c+e=(0,0,1,0,1)$ has distance 1 to a codeword in $\mathcal{C}P$; so for someone who knows $P$ it could be translated into a codeword in $\mathcal{C}$ and decoded with $G$.

$y$ also has a distance of 1 to a codeword in $\mathcal{C}$, but to the wrong one; so simple decoding does not work.

After another good read through the current research papers [1, 2, 3] I'm not so sure anymore that the above stated problem does indeed have a solution, yet. I think it heavily depends on the chosen code $G$ whether it is possible to break the system; and all system breaking algorithms gave $S$ as well (or their equivalent in the Niederreiter cryptosstem).

I now do not think it is possible to retrieve $S$ given $G$ alone.


Using cryptographically random password as both the password and the salt This question is theoretical, but will help with my understanding.

All of my passwords are securely generated using 64 random letters (both uppercase and lowercase) and numbers.

Using the argon2i password hashing algorithm, if I supply this long random password for both the message and the salt, will it still remain reasonably secure. In all cases the salt will be equal to the password being hashed.

My understanding about salts leads me to think, since the password is already sufficiently complex and random, that the salt always being the same exact value as the message/pw doesn't necessarily make the password reasonably discoverable. How does this apply to argon2i?

The whole point of a salt is to be unique to a set-password operation, so that attackers can't reuse work when they target multiple accounts (multiple users on the same server, multiple servers, or both). Using the password as the salt completely defeats the purpose.

The salt does not need to be unguessable or secret. The reason it's almost always a long-ish random string is to be statistically unique (in the literal sense), not to be securely unique: it's random so that the chance of two set-passwords using the same salt accidentally is negligible, not so that an adversary cannot guess it. A unique server name plus thread identifier plus timestamp would work as well, but that's not commonly done because it's hard to ensure you get a unique string this way in all environments (e.g. on a cloned virtual machine).

Most libraries automatically generate a random salt during the set-password operation and store the salt with other metadata together with the output of the password hashing function. In most programming environments, you'd need to do some extra processing to force a different salt during the set-password and check-password operations, and to change the storage format so that the salt is not stored (otherwise you'd just be storing your password in plain text). Do not do this extra processing: it would add complexity, only to reduce security even if implemented perfectly.

A password with 64 characters on a 62-character alphabet has about 381 bits of entropy, which is overkill: any data that it protects, or its transmission in communication, would at most be protected by a 256-bit key. 43 characters would give you 256 bits. 20 characters would give you 119 bits. With a password that long (and randomly generated, otherwise length is irrelevant), you don't actually need a password hashing mechanism: the purpose of password hashing mechanisms as opposed to ordinary hashing is to make guessing harder, but guessing a 119-bit secret is infeasible in the first place. So from a theoretical perspective, because your password is already high-entropy, using Argon2i or any other password hashing function with a defective salt won't actually reduce the security of your system. But you still shouldn't do it, both in case the system is ever used with a “normal” (lower-entropy) password and because it would increase the implementation complexity.


Identification Schemes and Internet of Things I was reading an article titled "A Novel Method for Polar Form of Any Degree of
Multivariate Polynomials with Applications in IoT" (doi:10.3390/s19040903)
I read the following statement:

"Identification schemes are the most important elements for many area, such as devices connected to the Internet"

I do not fully understand that statement. Why not other schemes? What makes Identification Scheme so useful for IoT?

All that this part in the introduction is really saying is that identification is important to IoT. Much as we can say that, for electronic banking transactions, privacy is important (because otherwise people could read your financial transactions) but authentication is more important (because otherwise people could actually steal your money, which is worse), this introduction claims that identification is the most important security objective for many areas, including IoT. It's not saying other objectives are not important, and whether or not you can objectively rank these criteria and agree that identification comes out on top isn't really the point - it's just saying that identification is an important objective for IoT.
As for why it's important, suppose you have an IoT device that unlocks the door to your car, or to your house. Before unlocking the door in response to a request, it's really important that the system is able to determine that the request came from your unlocking device, and not from someone else's unlocking device - i.e. it's important that it identifies your device. It may be that you couldn't care less about privacy - if "unlock my door" were the only message that's capable of being understood by the system, for example, then even if you encrypt it any eavesdropper will still know what the message is, so you gain nothing by concealing it.


Does Cut-Choose technique for yao garbled circuit provide statistical security? Yao Garbled circuit is 2 parties secure computation protocol between Semi honest adversaries. However, the cut-and-choose mechanism complies semi-honest garbled circuits into the one secure against malicious adversaries. Specifically, it provides statistical security against malicious garbler (circuit creator).

My question is as cut-and-choose provides statistical security, can garbler be "unbounded"?

Cut-and-choose is not a specific protocol that we can analyze, but a general technique whose details can be realized in many ways.

The basic idea of cut-and-choose is to generate many garbled circuits, open some of them to test for correctness, and evaluate the rest. The goal is to ensure that most (or, in some protocols, at least one) circuits used for evaluation are correct. If this condition holds, even of those "correct" circuits were generated by a corrupt garbler, there is no problem. Furthermore, the analysis of how many circuits to generate/open doesn't consider the running time of the corrupt garbler. It is a purely statistical argument. So this central idea of garbled circuits is naturally safe in the presence of an unbounded garbler.

But there are other parts of a "cut-and-choose protocol":

The garbler must provide garbled inputs to the receiver, using oblivious transfer (OT). Naturally the OT protocol must be secure against an unbounded sender, and this is possible.
The protocol must prevent the garbler from using inconsistent inputs across different garbled circuits. Different protocols vary widely in how they realize these properties. I believe that some are secure against an unbounded garbler, and probably others are not.
The protocol must prevent the garbler from causing the receiver to abort with input-dependent probability. Again, whether this is safe against an unbounded garbler depends on how the mechanism is realized. I think that some techniques are safe and others are not.


Factoring RSA weak modulus Given a public key for RSA, I have extracted the modulus which looks like this :

Public-Key: (2049 bit)
Modulus:
    01:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:02:19:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:fe:
    f8:45
Exponent: 65537 (0x10001)

If we remove the first 01 for the sign, we have a 2048 modulus and we can remove the zeros. So I guess the modulus will be :

219FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEF845

My problem now is to factorize this 1036 bit modulus. I think that the FF pattern gives us a hint but I can't find it.

Could you please help?

Thank you

As fgrieu points out, the number to factor can be written as
$$
n = 2^{2048} + 538\cdot 2^{1024} - 67515\,.
$$
We can identify this number with the polynomial $f(x) = x^2 + 538x - 67515$,
 with $n = f(2^{1024})$. Furthermore, if we factor this polynomial as $f(x) = g(x)\cdot h(x)$ then $n = f(2^{1024}) = g(2^{1024})\cdot h(2^{1024}) = p\cdot q$ since polynomial evaluation is homomorphic.

Since this is a simple quadratic equation, it is easy enough to find that $f(x) = (x - 105)(x + 643)$. Thus, the factors are $2^{1024} - 105$ and $2^{1024} + 643$.

The Fermat factorization algorithm is particularly efficient for integers whose factors are very close together. This happens to be the case here.


Effective key length of Two-Key Triple-DES What's the effective key length of Two-Key Triple-DES, for some (possibly several) reasonably well-defined and sensible definitions of effective key length, say assuming attack using ample chosen plaintext?

A sensible definition of effective key length (in bits) of a block cipher under some attack assumptions could be: one plus the base-2 logarithm of the number of evaluations of the cipher (for arbitrary key and plaintext) that could have been made for a cost equivalent to the expected cost of recovering the key using the best known attack applicable to said assumptions.

By this definition, for any secure block cipher, effective key length is at most about the number of key bits that can influence the output. Proof sketch: consider brute force key search, and that a block cipher having a cost of evaluation not much larger than a comparison would be insecure.

Two-Key Triple-DES (also known as TDEA Keying option 2) is a 64-bit block cipher with a 16-octet key, of which 112 bits can influence the output, defined by
$$\operatorname{3DES}(K_1\|K_2,P)=\operatorname{DES}(K_1,\operatorname{DES}^{-1}(K_2,\operatorname{DES}(K_1,P)))$$
where $K_1$ and $K_2$ are 8-octet keys, of which 56 bits can influence the output.

NIST has stated that with $2^{40}$ plaintext/ciphertext pairs, the security is at least 80 bits, but gives no upper bound beyond the obvious 112 bits, which is quite a wide margin.

The effective key length of 3DES assuming two or three chosen plaintexts (per the definition proposed) is no more than about 109.5 bits (see proof below); that obviously can only be lower with more (chosen) plaintext/ciphertext pairs.

One of the best known attack is: Paul C. van Oorschot and Michael J. Wiener: A Known-Plaintext Attack on Two-Key Triple Encryption (in proceedings of Eurocrypt 1990); but it is not easily translated into effective key length, at least for the definition that I propose, for the cost is dominated by memory accesses.

The 109.5 bits upper bound stated is 112, minus $\log_2(3)\approx 1.58$ because the core attack loop only performs a DES thus is about 3 times less costly than a 3DES, minus 1 thanks to the the complementation property, plus a little something for the two comparisons in the core loop.

More in details: 3DES inherit from DES the complementation property:
$$\forall K, \forall P, \operatorname{3DES}(\overline K,\overline P)=\overline{\operatorname{3DES}(K,P)}$$
and that allows a brute force search with maximum cost quite close to $2^{111}$ DES encryptions, that is $\approx2^{111}/3$ 3DES encryptions (and expected cost half that), with two or three chosen plaintexts:

obtain, for some $P$, the ciphertexts $\operatorname{3DES}(K,P)\to C$ and $\operatorname{3DES}(K,\overline P)\to C'$
for each of $2^{55}$ value of $K_1$ with high bit zero

compute $\operatorname{DES}(K_1,P)\to A$, $\operatorname{DES}^{-1}(K_1,C)\to B$, $\operatorname{DES}^{-1}(K_1,\overline{C'})\to B'$
for each of $2^{56}$ value of $K_2$

compute $\operatorname{DES}^{-1}(K_2,A)\to X$; this step dominates the cost
if $X=B$ (implying $\operatorname{3DES}(K_1\|K_2,P)=C$)

if $\operatorname{3DES}(K_1\|K_2,\overline P)=C'$, output $K_1\|K_2$

if $X=B'$ (implying $\operatorname{3DES}(\overline{K_1\|K_2},\overline P)=C'$)

if $\operatorname{3DES}(\overline{K_1\|K_2},P)=C$, output $\overline{K_1\|K_2}$

This is guaranteed to output the right $K$, and (heuristically) will seldom output others for random choice of $K$; and then another plaintext/ciphertext pair allows to rule out a false positive with overwhelming odds. The cost is dominated by $2^{111}$ DES at step (1); $2^{112}$ relatively cheap comparisons at steps (2) and (3), with very occasional false positives costing an expected $3\cdot 2^{48}$ evaluations of DES for their resolution; and the $3\cdot 2^{55}$ DES for computation of $A$, $B$, $B'$.

This attack is impractical: the total effort devoted to bitcoin mining (which is comparable in nature) as of February 2016 would have explored much less than one millionth of the search space for a single attacked key.

Des is 56 bits/key   with 2Des   the key is is 56*2 or 112bits.  It is not multiplicative like 56 * 55

3des is EDE  encrypt with k1, decrypt with k2 and encrypt with k3.  or 3*56 or 168 bits.  Quit often, cypherblock chaining is used with the sicond or third pass.  The cbc makes it even or difficult to guess the encryption keys.Decryption = DED


What are the memory requirements for this type of search if the hash function has an output length n bits? Let us suppose that we perform a collision search to find a pair $x_1$, $x_2$ with $x_1 \neq x_2$ such that $h(x_1)=h(x_2)$ for a given hash function, and we would like to specify the memory requirements for this type of search.

What does memory requirements means in this question ?

The naive approach

A naive algorithm for a research of collision is the following:

choose $x_1$
compute $h(x_1)$
Choose $x_2 \gets x_1 + 1$ ($x_2$ takes the value $x_1 + 1$)
compute $h(x_2)$ and verify if it matches $h(x_1)$
if it does not, do $x_2 \gets x_2 + 1$
go back to step 4, repeat and rinse.

How much memory do we need for this algorithm to work?
Well we need to store only $x_1$ and $x_2$. You can also store $h(x_1)$ in order to not compute it each time.

So if $h$ has a $b$ bits inputs, you need... $2 \times b$ memory to find your collision ($b$ for $x_1$ and $b$ for $x_2$).
This is the memory requirement for THIS search algorithm.

However this algorithm is clearly inefficient. Assuming the output of your hash function is $n$ bits. You have $2^n$ hash possibles. This will lead to an average of $\frac{2^n}{2}$ tentative... Clearly not feasible with a complexity of $O(2^{n-1})$.

The multi-target attack

In the previous attack we targeted a specific or fixed value ($x_1$). A more advanced attack consist of storing all the previous attempts and each time you try a new value of $x_2$, thus the multi-target.

The algorithm is the following:

consider an empty list $lst$.
choose $x$
add $x$ to $lst$
Choose $x' \gets x + 1$
Check if there is $x \in lst$ such that $h(x') = h(x)$
Add $x'$ to $lst$
Compute $x' \gets x' + 1$
go back to step 5, repeat and rinse.

I will let you guess the memory requirement for this algorithm.

In term of complexity, if you consider a list of $2^m$ elements, the complexity of this attack is $O(2^{n-m})$.


What is the maximum message size when using ECDSA (specifically secp256k1? I'm guessing that the message must conform to 256 bits but I was not able to find documentation of any message length limits.

The first step of ECDSA (and most signature mechanisms in actual use) is hashing the message, both in signature production and verification. The result of this hash is then truncated to fit the group size; that's truncated to 255-bit for secp256k1.

Hence what limits the size of the message to be signed is the limit built into the hash, typically due to a fixed-size counter. That limit is usually $2^{64}-1$ bit (e.g. for SHA-256, typically used for secp256k1) or more (e.g. $2^{128}-1$ bit for SHA-512 or SHA-512/256, which would be usable as a substitute for SHA-256 with secp256k1).

$2^{64}-1$ bit is just shy of 2 exbibyte and >2.3 exabyte (several days worth of the current mobile traffic worldwide per this source). This is not a practical issue with usual hashes, which are sequential: hashing that at a rate of $10^9$ blocks of 512-bit per second (much more than anything a single sequential device currently achieves) would require more than a year. For hashing real large messages, we need a parallelizable hash, typically a hash tree. It would also be a good idea to sign subtrees of manageable size, to avoid storing exabytes of data only to find afterwards that it does not check.

Some APIs to ECDSA expect the hash to be done externally, and typically start at the truncation step. Technically, they do not fully implement ECDSA. For secp256k1, such API would probably process the low-order 255-bit of their pre-hashed message input. For signature production at least, it is important (prudent and perhaps essential) to only allow a hash (PRF secure in the ROM) to be fed there, as it is necessary for conformance, is an assumption in ECSDA security proofs/arguments, and doing otherwise at least allows existential forgery (perhaps worse).

Further, some APIs to ECDSA signature production take as input the random they use to sign (or the generator they use to generate that). It is then essential to only allow that input to be (or yield, for a generator) a random secret exclusively used for that purpose and a single signature; doing otherwise would jeopardize the confidentiality of the private key.


Proving the right encrypted message was sent Total amateur to crypto here but I've searched and searched and am at the extent of my knowledge. I've gone down several avenues to satisfy what I'm looking for but I'm just going to describe what I'd like to achieve and see what comes back.

I am creating a transactional peer to peer pub/sub network and I need the following:

A publisher, Alice, broadcasts to the network an encrypted message. She will then make money by selling the key to decrypt that message to subscribers (say Bob). I need an encryption scheme such that anyone on the network (say Charles) can look at the broadcast from Alice (which can include other items separate from the ciphertext, if needed) and the transaction between Alice and Bob and verify that Alice gave the correct key to Bob without having the key himself.

A simple way to achieve this is with asymmetric cryptography, by letting both Alice and then Bob broadcast a message to the network with the shared private key. This message should be a digital signature, proving that both Alice and Bob have knowledge of that private key.