Can a user of a password-protected Wi-Fi sniff on other user's communication? Imagine a Wi-Fi network protected by WEP/WPA/WPA2. Users can join the network in case they know the pre-shared key of the access point.

Is it possible for a user A (who has successfully logged into the network) to sniff on the data communication of another user B, entirely because A uses the same pre-shared key like B (and C, D, E....)?

Well, it depends on the which protocol is being used.

For WEP and WPA, the keys used are derived directly from the pre-shared keys; that means that as long as you know the pre-shared keys, you can immediately decrypt packets as well.

On the other hand, WPA2 is somewhat stronger; the two sides exchange nonces to derive the keys.  Hence, unless you listen into the initial exchange, you're out of luck.  On the other hand, depending on when you start listening, this might not be that great of an improvement.


Compression function to guarantee randomness of one time pads? First of all, I would like to note that I am not building my own crypto.  I am simply curious and would like to learn.

What I am wondering is this: if we are worried about randomness of something like a one time pad, why don't we run the pad through a compression process (like bzip) to eliminate any patterns?  Wouldn't we essentially then be working with data guaranteed not to have patterns (at least over the chunk size of the compression algorithm)?

Is anyone doing this?  Would it even work?  If not, why not?

A one time pad (OTP) should by definition not have any patterns. An entropy source can have patterns, but an OTP by definition should consist of pure random bits.

In general you can create something that is close to a true random number generator by applying a cryptographic hash function over the output of an entropy source. According to NIST you should however provide twice the entropy within the input compared with the output. A cryptographic hash function is often referred to as a compression function.

Such a compression function should however not be confused with the underlying compression functions used for creating zip or bzip (etcetera) archives. Those are fully reversible compression functions, and will therefore only add some complexity, not security.

So there is probably somebody doing this, but no, it won't work.


Using only 4 Bytes of AES-CMAC if i calculate a AES_CMAC for 64 Bytes, i get a 16 Byte CMAC.

Is it ok to use only the first 4 Bytes for authentication?

Can i assume that if the first 4 bytes are correct, the other bytes must be ok too?

Thank you!

With AES_CMAC, tag truncation acts like you would expect; if an attacker generates a message and a random tag, then they have a $2^{-32}$ (or one in 4 billion chance) of happening to pick the correct random tag (and getting the message accepted), and with AES_CMAC, there's nothing they can do to improve on that.

Is a $2^{-32}$ success probability per attempt by the attacker acceptable?  Well, that depends on what your authenticating (and the cost to you of accepting an invalid message); in some scenarios, that might be quite acceptable, in others (e.g. doing financial transfers) it might not.


How can I prove in zero knowldege that an ElGamal shuffle is correct for a special setting? In a special ElGamal encryption scheme, every user has an ElGamal encryption key-pair using the same cyclic group $G$ and generator $g$.

The system has a special function :

$$ \mathrm{ShuffleEncrypt}(m_1, m_2, h_1, h_2 ) = \text{RandomPermutationOf} ( \operatorname{Enc}( h_1,m_1) , \operatorname{Enc}( h_2, m_2) ) = ( a, b)$$

$m_1$ and $m_2$ are plaintexts.

So given two public keys $h_1$ and $h_2$ and two plaintexts the function encrypts them and shuffles the resulting ElGamal ciphertexts ($a$ and $b$).

I want to prove in zero knowledge that $\mathrm{ShuffleEncrypt}$ was correctly done:

$m_1$, $m_2$ and the ElGamal randomization values must be kept hidden.
The ZNP must prove that $m_1$ and $m_2$ were known to the party doing $\mathrm{ShuffleEncrypt}$.

The verifier knows $h_1$, $h_2$, $a$ and $b$.

The ZN proof probably involves hiding both base an exponent values.
Since there are many users, they cannot jointly compute a master shared key nor any other shared secret.

Any idea?
(Maybe another public key cryptosystem is better suited for this kind of ZNP.)

I don't understand the question (what is public? what is secret? what is the definition of all variables and functions?), but I can give you a pointer to literature that I strongly expect is highly relevant:

Take a look at mixnets.  There's an enormous amount of research literature on the subject.  It solves the following sort of problem (as well as variations): given a list of ciphertexts, Alice randomly permutes and decrypts them and then outputs the list of plaintexts, and now Alice wants to prove in zero knowledge that she did this correctly, without revealing the linkage between ciphertexts and plaintexts.  Sounds like exactly what you need.

P.S. It sounds like your system is a special case of a mixnet, with only two ciphertexts.  You might be able to design a custom protocol, using a disjunctive zero-knowledge proofs.  There's a standard way to prove $\phi \vee \psi$ in zero-knowledge, without disclosing which is true (assuming you have a zero-knowledge protocol for $\phi$ and a zero-knowledge protocol for $\psi$).  Also, there's a standard way to prove that $m$ is a correct decryption of ciphertext $c$.  So, you could try using these methods to prove that $(D(a)=m_1 \wedge D(b)=m_2) \vee (D(a)=m_2 \wedge D(b)=m_1)$.  You'll probably want to use a proof of knowledge.


Is there a PRNG algorithm that allows to switch between states directly, not calling next()? Basically I need a function with the following interface:

getRandomBytes(uint128 seed, uint64 state, uint16 byteCount)

Consecutive calls with the same seed and state must give the same results.

What algorithm should I look at?

Probably the easiest one with regards to the protocol is a XOF, an eXtendable Output Function. Two have been defined as part of SHA-3, called SHAKE-128 and SHAKE-256. These have a single input of any length, and can output as many bytes as required.

Of course SHA-3 is relatively new, so not all runtimes / API's may support the SHAKE variants out of the box.

In your case you would feed it the 128 bit seed concatenated with the 64 bit state. There should be no need for two separate variables.


Does the Message Integrity Check in WPA(2) standard solve the problem of non-repudiation? Whether the receiver can be sure that the message is sent by the source only and not spoofed by someone else?

No it doesn't.

Message Authentication Codes (MACs, which in networking some may call MIC in order to differenciate from Media Access Control) are symmetric-key primitives that only provides authenticity and integrity of the message exchange. Non-repudiation requires public-key cryptography.


Can post-quantum algorithms be run on commercial devices? Noob alert! Can we run quantum safe algorithms on commercial devices (like phones, laptops, etc)? I've seen some messaging apps and vpn providers marketing themselves as quantum-proof. How likely is that all these claims are bogus for marketing (imo, very)?

Post-quantum cryptography addresses the problem of developing public-schemes whose underlying assumptions are (believed to be) quantum resilient, i.e., the assumptions hold even in the presence of quantum computers.

There are many proposals for the underlying assumption and this leads to several branches like lattice-based cryptography, multivariate cryptography, code-based cryptography, hash-based cryptography or isogeny-based cryptography, among others.
The cool thing about these assumptions and techniques is that they can be implemented in classical computers.
In fact, many of these are already implemented and there is a competition driven by NIST to standardize some of these.

So, yes, these primitives are usable nowadays. Maybe these companies use a scheme of this nature, that may be the case.


Blockchain without cryptography Because blockchain is decentralized, what would happen if there was no cryptography anymore to protect the blockchain? I know it would not be used anymore but why? "Hackers" could reverse transactions but I can't think of anything else...

Blockchain is a decentralized append-only ledger.
If it does not use cryptography to achieve the goal of being append-only, then it would likely not provide any real guarantee of being append-only. It would only provide such a guarantee as long as it was used as prescribed.
For instance, we could create an append-only data structure in a program, and simply program the API to refuse to make any modifications other than appending new data.
However, that does not guarantee that no other modifications could be made to the underlying data, there could exist many ways to work around the provided API to insert/remove/etc. as desired - if you don't use the provided API you can do anything you want to the underlying data. If there is no form of cryptography protecting the integrity of the information, then any peers that attempt to read this data structure have no way of knowing it has been tampered with.
Without cryptography, "append-only" is more of a suggestion/recommendation rather than a matter of technical capability. It is merely inconvenient rather than computationally intractable.


Is HMAC padding the same as bcrypt? I have been watching Christof Paar on his YouTube lectures also I used bcrypt to store two passwords with salts and I find that I have a few questions.

I am interested in what bcrypt does to the start of the final hash.

$2a$10$

I have two thoughts on this:

I know that Christof is speaking about HMACS in the lecture above not bcrypt, but the start of the final hash does seem alot like what he describes as 'padding', is it the same?.
The first part ($2a) is saying that there are two vars; a salt and a message, but I am not sure what the a is for here? The second part is the iterations or something to do with the salt length I think as there is no space between the salt and the message.

This is not padding, nor is it related to the concept.

The output from the bcrypt library you're using is in a format inspired by Linux crypt(3) format. Dollar signs are field separators. 2a is the algorithm identifier. The full list is:

ID  | Method
─────────────────────────────────────────────────────────
1   | MD5
2a  | Blowfish (not in mainline glibc; added in some
    | Linux distributions)
5   | SHA-256 (since glibc 2.7)
6   | SHA-512 (since glibc 2.7)

The second field, 10, is the strength factor; I believe this corresponds to $2^{10}$ iterations of the algorithm. The salt and hash are stored concatenated with one-another — they are both fixed widths (128 bits for the salt, 184 bits for the hash), so it is easy to extract them.


Hashing a counter to prevent distinguishers in CTR mode Because a block cipher is a PRP and thus bijective, the fact that the input in CTR mode never repeats means that each block of keystream will be unique. This creates a distinguisher from random data following the birthday bound if enough data is encrypted even before the counter repeats, especially if the block size is too small. Stream ciphers like ChaCha20 avoid this issue by feeding a counter into a PRF instead of a PRP, meaning blocks of keystream will repeat according to the birthday bound.

Is it feasible to mitigate this problem with a PRP by feeding the nonce and counter through a very fast and deterministic hashing function first? Because the input to the block cipher is not secret in CTR mode, it would not need to be a secure hash function. All it would need to do is admit collisions due to the birthday bound, allowing for a repeating block in the keystream after roughly $2^{n/2}$ blocks.

Is this correct? If so, what is the fastest hash function which has the required properties?

I'm reading the question as generating a keystream per: $S_i\gets E_K(F(\mathrm{IV},i))$ where $F$ is a public function built from a hash function; for incremental index $i$ starting from $0$ and public random $\mathrm{IV}$, with $F$ having a sizable collision rate when $i$ varies; and for $E$ a block cipher with secret key $K$.

That is quite insecure: the location of the collisions, that is values of $i$, $j$ with $i\ne j$ and $F(\mathrm{IV},i)=F(\mathrm{IV},j)$, can be found by an adversary from the public $\mathrm{IV}$. And then knowledge that $K_i=K_j$ can be used to mount an attack allowing decryption of some plaintext fragment from partially known plaintext.


How do digital certificates work, and why is it not possible to reverse engineer one from a signed file? Digital certificates are used quite commonly these days, for signing files. They are used by various operating systems to ensure reliability and security. For example, Android requires that each of the apps submitted on the Android Market is signed with a certificate, and any updates are signed with the same certificate. This prevents anyone who hacks the account from replacing the application with their own, possible malicious one.

My question has two parts:

How do these certificates actually work? Is it similar to how digital signatures work?
Why is it impossible to reverse engineer and create the certificate from a file that has been signed with it? Would the answer change if you have both a signed and an unsigned copy of the same file? Does this vary on an algorithm to algorithm basis?

To simplify, let's say that our certificate has been generated by the key tool in the Java JDK, uses the RSA algorithm, has a key size of 2048 bits (does this matter?) and has a validity of 10000 days.

Such certificates are basically just an implementation of digital signatures. One certificate is used to sign the data using a private key, and a corresponding verification certificate is given to the user along with the signature and the data. The user uses the verification certificate to verify that the file matches its signature.

You can't reverse engineer the signing certificate from the verification certificate because of the cryptographic properties of public/private keys. Whatever signing algorithm they are using, the private key should be underivable from the public key. Exactly why this is difficult (or at least believed to be difficult) depends on the exact algorithm being used, but as a general rule they all have this property.

An example situation, for a made-up app store/market system:

Developer creates an account in a market place through the Market Owner and gives the Market Owner a copy of their public certificate.
Developer signs an app with their private certificate and gives the app, signature, and public certificate to Market Owner.
Market Owner verifies that the certificate matches the one for Developer on their records.
Market Owner verifies that the signature of the app is valid using the public certificate.
Market strips off the signature and certificate from the app.
Market signs the app using their own private certificate and puts the signature and public certificate in the app.
Anyone who downloads the app verifies that the public certificate matches their device's local copy (it may have a built-in copy of said certificate) and they verify the app's signature from the Market Owner's public certificate.

There are a lot of variations and complexities that arise. What happens when a certificate is compromised, how to you revoke it? What if the user loses his certificate? What if the Market Owner wants to use multiple certificates? What about certificate expiry dates? Etc. But that's a general model for how the this kind of system could work using certificates.


Is this MAC-then-encrypt scheme secure? I have the following requirements:

64 bits (8 bytes) of data ($D$) that requires confidentiality and integrity;
the data itself is a nonce, never need to authenticate/encrypt the same value twice (e.g. a counter);
I can only use AES cipher (128-bits key);
I can have a maximum of 128 bits as output (one block).

Given two different AES-128 keys ($K_\mathrm A$ for Authentication, $K_\mathrm E$ for Encryption), I'm using the following MAC-then-Encrypt scheme:

compute $\mathit{MAC} = \operatorname{CMAC}(K_\mathrm A, D, 8)$ (see RFC 4493)
truncate the MAC to get the tag: $T = \operatorname{MSB}_{64}(\mathit{MAC})$ (see NIST 800-38B)
get the plaintext $P = D\mathop\Vert T$ (16 bytes)
get the ciphertext $C = \operatorname{AES}(K_\mathrm E, P)$ by using AES/ECB/NoPadding mode

I generally know that MAC-then-Encrypt schemes can be secure, but I'm not able to demonstrate it for this scheme. Could you elaborate on that? Is there any improvement I can do?

I know that a good alternative would be AES-GCM (or CCM). Is there any way to fit into a single block of ciphertext by using AES-GCM on 8 bytes of data?

The lack of a generic security reduction for MAC-then-encrypt is basically only for pathological cases where an encryption scheme admits modifications to the ciphertext that don't affect the plaintext, like AES-CTR with an extra bit of key stream appended to the message on encryption and ignored on decryption.

So is your AES-CMAC-then-AES scheme or an AES-GCM variant secure?

AES-CMAC-then-AES.
What you described is a deterministic nonceless authenticated encryption scheme.  As such, it can't conceal repeated messages, but otherwise it provides confidentiality and authentication, as long as you reject invalid MAC tags before even thinking about the data.  Finding a way to reject replayed messages is your responsibility.

AES-GCM.
AES-GCM is a deterministic nonce-based authenticated encryption scheme.  That is, AES-GCM is a different kind of cryptosystem from AES-CMAC-then-AES.  If you can provide a 96-bit nonce for each message, e.g. a message sequence number, then it provides about the same security.*

AES-GCM is also quirky about nonce sizes: With a nonce size other than 96 bits, AES-GCM's security diminishes, because of the low but nonnegligible probability of collision in the internal 96-bit nonce derivation.  And, of course, with a repeated nonce, AES-GCM's security vanishes.

But for the scenario you described, both more complex than you need!

(CAVEAT LECTOR: This is not a peer-reviewed academic journal of cryptographic designs.  This is a pseudonymous stranger on the internet blathering crypto at you.)

You could use $C = \operatorname{AES}_k(D \mathbin\Vert 0^{64})$, and reject decryption if the message does not end with 64 zero bits.

For uniform random permutation $\pi\colon \{0,1\}^{128} \to \{0,1\}^{128}$, the adversary's chance of guessing a ciphertext $C'$ for which $\pi(C')$ has 64 trailing zero bits in one try is $2^{-64}$, which is the best you could hope for with an 8-byte authenticator anyway.

Obviously, $\operatorname{AES}_k^{-1}$ for uniform random $k \in \{0,1\}^{128}$ or $k \in \{0,1\}^{256}$ is not exactly a uniform random choice of permutation, but the attacker's advantage knowing $\pi = \operatorname{AES}_k^{-1}$ for some key $k$ is negligible: even in their worst case when $D$ is uniform, they have a far better chance of guessing $D$ or forging $C'$ than of guessing $k$.

* The short messages are critical here because the attacker's forgery probability is about $2^{-\tau}$ for CMAC but $\ell \cdot 2^{-\tau}$ for GCM, for $\tau$-bit tags and up to $128\ell$-bit messages, when the tag size $\tau$ is much smaller than the cipher block size 128.

Specifically, let $n$ be the block size in bits; $\tau$, the tag size in bits; $\ell$, the maximum message length in $n$-bit blocks; $q$, the number of oracle queries; and $f$, the number of forgery attempts.  Assume a uniform random permutation; $\operatorname{AES}_k$ is a good enough approximation.  For CMAC, the attacker's forgery probability is bounded by $$O(q \ell^2) 2^{-n} + 1 - \operatorname{Binom}(0; f, 2^{-\tau}) = O(q \ell^2) 2^{-n} + 1 - (1 - 2^{-\tau})^f,$$ which, for $f \lll 2^\tau$, is approximately $O(q \ell^2) 2^{-n} + f 2^{-\tau}$.  For GCM, the attacker's forgery probability is bounded by $$1 - \operatorname{Binom}(0; f, \ell 2^{-\tau}) = 1 - (1 - \ell 2^{-\tau})^f \approx f \ell 2^{-\tau}.$$

If $\tau$ is, say, 32, and you authenticate messages of up to 64 KB, CMAC limits the forger's success to about one in four billion, while GCM limits the forger's success to about one in four thousand.


How to ask for an Identity confirmation without revealing Let us say Alice has a list of public keys of her contacts. Bob wants to contact Ted and Bob has public key of Ted.

Now, Is it possible to confirm that Alice has the same public key, without revealing that Bob wants to contact Ted? If we ask directly Alice, there will loss in privacy for both the users. Is there any relevant concept in Cryptography that can help me here ?

There are two ways that I see.

First, Oblivious Transfer allows a requester to retrieve relevant information (and only relevant information) from the sender without the requester revealing which piece of information they're after.  This would allow the Bob to obtain the key that Alice has for Ted, without Alice knowing that Bob is interested in Ted's key.  Depending on the scenario, this could be a vulnerability in the case that Bob has the wrong key -- this protocol would allow him to obtain the correct one from Alice.

Second, Secure Computation allows Bob to obtain the value of $f(x,y)$ where $x$ is only known to Bob and $y$ only known to Alice (and $f$ is mutually known).  Let's say that Bob knows that Ted's key is stored at position $i$ of Alice's contact list.  Then we could have $y=$Alice's contacts, $x=(i,t)$ where $t$ is they key Bob has for Ted.  Then $f(x,y)=[[y[i] == t]]$.


Game with symmetric key Alice and Bob are playing Rock-paper-scissors.

Alice chooses $a \leftarrow\{stone, paper, scissors\}$ and a nonce $R_A$ used as symmetric key for encryption

$$A → B : A, R_A(a)$$

Bob chooses $b \leftarrow\{stone,paper, scissors\}$ and nonce $R_B$

$$B → A : B, R_B(b)$$

$$A → B : A, R_A$$

Now Bob decodes $R_A(a)$ and knows a and so he knows who is the winner

$$B → A : B, R_B$$

Now Alice decodes $R_B(b)$ and knows $b$ and so he knows who is the winner

What are the possible fraudulent behaviours the players could engage in?

You don't specify your encryption method. To show you why that is important, I'm going to pick a really bad one. Let's say we use a stream cipher to encrypt. "stone" and "paper" have the same length, so we are good there, but "scissors" is longer. So, if Alice chooses "scissors", Bob can see the ciphertext length and know what she picked and choose "stone". Therefore, if Alice chooses "scissors", Bob always wins.

If you pick your encryption method so that the ciphertext lengths are always the same, this attack is mitigated.

Bob, once he knows whether or not he wins, could refuse to send $R_B$.

The major flaw, however, is, even if you pick a really good encryption method (say AES-CBC with a fixed length size), you are doing nothing for integrity checking when integrity is really the primary concern here.

The proper way to do this would be to have Alice and Bob each publish a commitment to their choice. Then they open the commitment publicly. This could be done, for example, with HMAC. Choose a random key $k$ and publish $HMAC(k,m)$ where $m$ is the choice. Once both have done this, they can each publish $m,k$. That way they can verify that the choice hasn't changed.


A key-derivation function that is as strong as the stronger of PBKDF2 and scrypt I want a key stretching system that's as strong as the stronger of scrypt and PBKDF2.  The consensus now is that scrypt is by far the better system, but that might change if in the future, a weakness is found in Salsa20. Here is a proposed system that I dreamed up, does it seem like a good idea?

First run scrypt and produce twice as much key material as needed. Use $N$, $r$ and $p$ parameters as normal.

$k_0 = \mathrm{scrypt}(\mathrm{key},\mathrm{salt},2 \cdot \mathrm{len},N,r,p)$

Then split the key $k_0$ into to equal pieces, $k_1$, and $k_2$.  Now run PBKDF2, picking a sizable $c$ parameter:

$k_3 = \mathrm{PBKDF2}(k_2, \mathrm{salt}, \mathrm{len}, c)$

Finally, output $k_1 \oplus k_3$.

I was thinking that advantage of this construction over a more naive one (or just turning up the $c$ parameter in the PBKDF2 final round of scrypt) is that the original key isn't used as an input to the weaker PBKDF2, and that the output of PBKDF2 can't weaken the output of scrypt.  However, if scrypt turns out to be easier than expected due to a Salsa20 weakness, then it still is necessary to brute-force PBKDF2.

scrypt uses PBKDF2 internally, so it's absolutely crucial to prevent nasty interactions. My suggestion would be a simpler scheme (using simplified syntax):

$k = \mathrm{scrypt}(\text{key}, \text{salt} \mathbin\| 0x0) \oplus \mathrm{PBKDF2}(\text{key}, \text{salt} \mathbin\| 0x1)$

This does exactly what you want - that is, the output key has exactly the strength of the stronger of the two, without nasty interactions. Your construction may or may not have the same property, but the close relationship of scrypt and PBKDF2 makes me rather nervous.


Secure implementation of public key cryptography Reading online I've found out that for example the RSA implementation that you usually find on textook is not secure.
Where I can find some secure implementation of algorithm such as RSA, ECDH, ECDSA?

(written in C or C++ or python)

Libsodium is written/implementable in C++, C and Python. It implements lots of crypto systems, such as public key cryptography. Here is the intro in the docs: https://libsodium.gitbook.io/doc/


Calculating the Min Entropy of a string of bits Let's say you are looking to collect some randomness from your computer. At a given time stamp, you can always collect the following 16bits as part of the time stamp:

First 5 bits are fixed and always the same
The next 4 bits are not perfectly random and exhibit a probability of 1/8 for the different possibilities
Finally the last 7 bits are perfectly random, always

What would be the min entropy of one time stamp?

My intuition thinks the min entropy would be 3 bits (from the 4 imperfect bits) + 7bits from the last section, giving Min Entropy = 10 bits for one time stamp. Does this make sense?

EDIT: Rephrased the 2nd bullet point

If your probabilities are exact, then your math is right. But even if they are off by the slightest amount (e.g. $2^{-10000}$), it doesn't hold any more. For a practical system like timestamps in a computer, it's quite unlikely that your have exact values for the probabilities. If those probabilities are average measurements, then the resulting entropy is also only an average and not a lower bound (minimum).


IKEv2 DH Group on SonicWall I am developing internal standards for IPsec VPN setup on SonicWall firewalls, and I have been learning about IKEv2.  When IKEv2 "mode" is selected, the UI disables the DH Group, Encryption, and Authentication fields, and I can't find what values are used, anywhere in the documentation.  Does IKEv2 have some mechanism by which it negotiates those fields to the "highest common denominator"?  If not, I'll just call tech support on Monday.

Does IKEv2 have some mechanism by which it negotiates those fields to the "highest common denominator"?

Well, IKEv2 allows the initiator to list what DH Groups, Encryption algorithms and Authentication algorithms (among others), and in what combinations; the responder then selects from that list what will be used.  It's actually pretty flexible (except for DH group; that's a bit kludgy, as the initiator has to select a 'main one', and if the responder doesn't like it, it needs to list what DH group it really wants, and we take another round trip with that group).

Now, the initiator lists things in preference order (e.g. the encryption algorithm it would prefer is listed first), and the responder is supposed to respect that order.  There's no built in logic within the IKE protocol itself that says, for example, AES-GCM is better (or worse) then ChaCha20; that's something for the initiator to decide.

  When IKEv2 "mode" is selected, the UI disables the DH Group, Encryption, and Authentication fields, and I can't find what values are used, anywhere in the documentation.

This is definitely something that ought to be both changeable and documented; if would appear unlikely that you could come up with a single policy that would make everyone happy.


RSA Decryption with Private Key but no public exponent I manually set the RSA private key, given the private exponent and modulus. When I use this key to decrypt a message encrypted using a public key (also set with public exponent and modulus) seems to fail with a: "Need public exponent" message in OpenSSL.

Should RSA private key also require the public exponent for decryption, or is this specific to OpenSSL?

There's nothing inherent in the RSA decryption operation that requires the public exponent; it's just:

  $P = C^d \mod N$

(or a slightly more complex version involving the CRT parameters)

So, strictly speaking, OpenSSL doesn't have to insist on it.

On the other hand, there are some protections against side channel attacks that involve the public modulus:

If they blind the message before performing RSA, the standard way to do this is to break this up into these operations:

Select a random $r$ and $r^{-1} \bmod N$
Compute $C_{blind} = r^e C \bmod N$
Compute $P_{blind} = C_{blind} ^ d \bmod N$
Compute $P = r^{-1} P_{blind} \bmod N$

To protect against differential fault analysis attacks (where they deliberately attempt to induce an error, and attempt to deduce information from the erroneous result); the standard way to protect against this is:

Compute $P = C^d \bmod N$
Compute $C_2 = P^e \bmod N$
Check if $C = C_2$; if not, discard the result and signal error.

Both of the above use the public exponent $e$ in their computations; hence they need to know it.

OpenSSL is able to do message blinding; I suspect that's why they always insist on it.


Does knowing that the exponent is in a certain range help solving discrete log? given:
$c=g^i \bmod P$
$g$ generator for group with group size $\varphi(P)$
$g,P,\varphi(P)$,c is known by the attacker
He wants to know $i$.

Now the attacker also knows $j,k$ with $j<i<k$
$k-j$ is too big to compute them all but it is much smaller than group size.

Does this knowledge about $i$ help the attacker?

The basic baby-step-giant-step algorithm can be tweaked to make use of this information.
The following algorithm takes $\Theta(\!\sqrt{k-j})$ group operations.

Let $h:=c\cdot g^{-j-1}$, which equals $g^{i-j-1}$.
Pick some integer $m\geq\sqrt{k-j-1}$.
Initialize an empty lookup table $T$.
For all $0\leq a<m$, compute $g^{ma}$ and store $T[g^{ma}]:=a$.
For all $0\leq b<m$, compute $g^{-b}h$ and check if $g^{-b}h$ is in $T$. When a match is found, return $j+1+m\cdot T[g^{-b}h]+b$.

Note that this is almost exactly the standard BSGS algorithm, except for replacing the unknown exponent $i$ by $i-j-1$ in step 1 and adjusting the output accordingly in step 5.

Correctness:
If the algorithm returns something, it must be of the form $r=j+1+m\alpha+\beta$ with $0\leq\alpha,\beta<m$ and $T[g^{-\beta}h]=T[g^{m\alpha}]$.
This implies
$$
g^r
= g^{j+1+m\alpha+\beta}
= g^{j+1-\beta+(i-j-1)+\beta}
= g^i
\text,
$$
hence $r=i$ (modulo the order of $g$).

Completeness: Let $b:=(i-j-1)\bmod m$ and $a:=(i-j-1-b)/m$.
These values are in the range $0\leq a,b<m$ and satisfy $-b+i-j-1=ma$, hence will be found by the algorithm.


Rationale for NORX/Ketje/Keyak not being chosen for the CAESAR final portfolio Was any specific rationale given on why none of the sponge-based AEAD algorithms (specifically NORX, Keyak, and Ketje) of the 3rd round candidates of the CAESAR competition made it to the final portfolio? If so, where can I find additional details?

This is an interesting question ,  here are some main points to identify major differences between Caesar winners and above-mentioned algorithm

Background

Norx is LRX- Duplex based authenticated encryption scheme designed
for lightweight and high-performance use cases.
Ketje is Keccak-f-Duplex based authenticated encryption  scheme  designed for lightweight (except Ketje Major for high performance)
Keyak is Keccak-f-Duplex based authenticated encryption  scheme  designed for high-performance (except River Keyak for lightweight)
The winners of Lightweight use case are Ascon (SPN-duplex based authenticated encryption cipher and Acorn (stream based authenticated encryption).
The winners of high-performance case are AEGIS (AES-Block cipher authenticated encryption), OCB (AES-XEX authenticated encryption)  and  MORUS (LRX-stream cipher )

Performance

A hardware benchmark on Virtex6 , Virtex-7 and Straix-IV shows the Acorn and Ascon have the lowest Area/$A_{GCM}$ compared to Norx , Ketje and Keyak (0.16 and 0.4 on average).
The hardware performance in term of throughput/ Area and throughtput/AES-GCM throughput for AEGIS and MORUS across Virtex6 , Virtex-7 and Straix-IV are very high compared to OCB , Ketje , Norx and Keyak.
The software performance in this chart shows the , AEGIS, OCB and MORUS have lower cycles per bytes (higher performance ) compared to Ketje , Norx and Keyak.

Security

A paper presented in FSE 17 (cryptanalysis of NORX2) concluded Almost practical forgery and key recovery attack on NORX v2.0.

Further Details

ATHENa project is hardware benchmark of Caesar candidates
eBACS: ECRYPT Benchmarking of Cryptographic Systems

PS:Iam happy to see if someone provide more selection rationals.


Backdoor Designer Key Recovery in LowMC-M The paper https://eprint.iacr.org/2020/986.pdf proposed a framework for embedding a malicious backdoor in LowMC cipher, that will later help the designer to recover the secret key in the known-plaintext attack setting.
As the framework is scalable, suppose a cipher with 16 bit block size of 3 rounds is constructed. The framework generates the necessary constant parameters (RC, key matrices, linear layer matrices etc.) for designing a cipher along with deterministic differential characteristics for key recovery. For the above setting with 2 differential characteristics embedded, it generates  as
How the designer knowing the tweak pairs and the Plaintext differences can be able to recover the key in a short span of time in contrast to an attacker not knowing any of these parameters.
How the key can be recovered using plain differential cryptanalysis in this setting, I am confused or not getting the elaboration presented on page 17 and page 19? Will the designer be able to recover the round keys or the main key being input to cipher?
According to the article, only one differential characteristics (tweak pair) is able to recover the key, but for enhanced security more should be embedded? How one differential characteristics (tweak pair) embedded over r-1 round will be able to recover the key?

This would be done by a last round attack. The attacker would collect a crib of known pairs of inputs that differ by the plaintext difference (01010001101011 in your example). They would then run through $2^{16}$ guesses for the last round key, for each guess they would be able calculate the difference between each pair in round $r-1$ (by running just one round of the decryption process) and look for instances of the target difference (0111101010100100 in your case). In cases where they had guessed incorrectly, the target difference would not show up (or perhaps once); in the case of a correct guess the target would show up repeatedly.
Once the last round key is known, this drastically cuts down the number of main keys that could have produced it and (depending on key schedule) the main keys that are possible can then be exhausted.


Why XOFs are more convenient than Hash Functions in modeling Random Oracles In this answer, it is mentioned that

  Easier instantiation of random oracles. Some security proofs rely on the so-called random oracle model to prove the security of a given scheme. Normally you'd use some artificial construction around a fixed-size hash function to get the desired output size, but with XOFs you can just plug them right in without having to fear any mistakes on your side potentially breaking the proofs (most people don't know/understand in many cases, me included).

and NIST.FIPS.202 says

  Extendable-output functions are different from hash functions, but it is possible to use them in similar ways, with the flexibility to be adapted directly to the requirements of individual applications, subject to additional security considerations.

Is it just the fixed-size problem of hash functions? Like in this question  Can MGF1 within OAEP and PSS be replaced by a XOF?

Actually, we can create arbitrary length from the hash functions by $h_0 = H(m)$ then $h_i = H(h|i), i>0$ and the output is $h_0\|h_1\|\ldots$ - I'm not claiming this is collision-free.

At page 24 of the NIST document, however, with the section titled as Additional Consideration for Extendable-Output Functions;

  XOFs have the potential for generating related outputs—a property that designers of security applications/protocols/systems may not expect of
  hash functions.

So;

Why XOFs are better than Hash Functions in modeling Random oracles?

Suppose you are instantiating a cryptosystem, such as RSA-FDH signatures with 2048-bit modulus, or EdDSA over a $b$-bit curve for $b \gg 256$ like edwards448, which needs a sizable hash function modeled by a random oracle.  But the hash functions available at your disposal are only SHA-2.

EdDSA needs a $2b$-bit hash function.  For edwards25519, it was enough to use SHA-512, but not for edwards448.
RSA-FDH with a 2048-bit modulus needs a ${\approx}2048$-bit hash function.  None of the SHA-2 hash functions are big enough for this.

What do you do?  In order to instantiate one of these cryptosystems, you have to pick some way to compose the SHA-2 functions into a larger-output hash function.  It's not a priori obvious what instantiation to choose.

One might naively choose $H(x) \mathbin\| H(H(x)) \mathbin\| \dotsb \mathbin\| H^n(x)$, but this is manifestly not indifferentiable from a random oracle.  (You and I might not choose this, but I have seen people reach for it in practice.)
One might choose $H(x \mathbin\| 1) \mathbin\| H(x \mathbin\| 2) \mathbin\| \dotsb \mathbin\| H(x \mathbin\| n)$; of course, one must also choose how wide the numbers are, how they're padded, etc.
One might choose $H(H(x) \mathbin\| 1) \mathbin\| H(H(x) \mathbin\| 2) \mathbin\| \dotsb \mathbin\| H(H(x) \mathbin\| n)$ like you suggested, but it's not clear what purpose the extra $H(x)$ serves.

Personally I would choose option (2) with little-endian 64-bit integers, but justifying that choice requires further thought and explanation, and not everyone will make the same choice.  With a standard XOF there is no need to think about these questions: you just ask SHAKE128 for as long an output as you want.

This is part of why Ed448 was designed not to use SHA3-512 (in some counter mode or whatever) by analogy with Ed25519's use of SHA-512, but instead uses SHAKE256 with an appropriately long output.  The complexity of the OAEP standard arises in part because there were no XOFs available so one had to be invented (the ‘MGF’); it would have been much simpler and easier to understand if XOFs were available.


Probability that an attacker wins the discrete logarithm game when exponents are drawn from a subset Suppose $g$ is a generator of an order $p$ cyclic group in which discrete logarithm is hard and $p$ is a prime (i.e., given $g^x$ for a random $x \in \{0,1,\ldots, p-1\}$, it is hard to recover $x$ except with $negl(\lambda)$, where $negl(\lambda)$ is a negligible function of the security parameter $\lambda$).

My question is as follows: what happens if I am given $g^y$ such that $y$ is chosen randomly from $\{0, 1, \ldots, q-1\}$ for some $q < p$, is there a way to quantify the hardness of discrete logarithm in terms of $q$? perhaps, something like: probability that one recovers $y$ is at most $\frac{1}{q} + negl(\lambda)$ and the probability is taken over the choice of $y$, or is there no way to quantify this?

I am mainly interested in knowing what happens in practice when one does this. For instance, in most libraries, the exponents are chosen to be 160 bits even though $p$ is 1024 bits.

(I posted this on math.stackexchange, but no responses. So, I am moving the question here by deleting it from there.)

Assume there exists an adversary for your q-subset DL problem that will be successful with probability $\mathsf{succ(\lambda)}$.
If you just use this adversary to attack the original DL problem, he will get an input that comes from the set it expects with probability $q/p$ and will therefore be succesfull with probability at least $q/p \cdot \mathsf{succ(\lambda)}$.
However we know that the DL problem is hard.
Thus, we can bound the success probability of the adversary:
$$\mathsf{negl}(\lambda) \ge q/p \cdot \mathsf{succ(\lambda)}$$
$$p/q\cdot\mathsf{negl}(\lambda) \ge \mathsf{succ(\lambda)}$$

Thus we get a bound for the success probability against your q-subset DL problem.

Whether this bound is helpful, depends on $q$. As long as $p/q$ is polynomial, the upper bound is still a negligible function. So at least in theory this is still a hard problem.

In practice and for a fixed group size that is of course a completely different story.

Of course, if $p/q$ is superpolynomial, then the all bets are off and this upper bound does not help you in any way.


Is RSA padding needed for single recipient, one-time, unique random message? I want a way to encrypt files using this process: https://crypto.stackexchange.com/a/15 . That is: generate a random password, use that to AES-encrypt a file, and use an RSA public key to encrypt the random password.

I can arrange for the password (= AES key) to be randomly generated every single time, and can arrange things so that doing so again with either the same or a different RSA key will result in a new AES password being generated. My question is whether I need to use padding when doing RSA encryption of the unique AES key.

I've read the answers to several closely related questions, especially Is RSA of a random nonce with no padding safe? and also Does RSA padding have to be unpredictable if the payload is?, which state that padding is necessary. But, as I read the replies, it seems to be necessary in the context of multiple recipients, in which there multiple RSA public keys, but only one random AES password (random but generated once only, not generated anew for each RSA key / recipient).

Basically, in my case, I don't see how padding an already known-to-be-uniquely-random message would make it any more random.

So: Am I just confused and missing something, or are the linked answers only emphasizing
the need for padding in multiple recipient cases (where the password stays the same)?

I recommend that you stick with the standard padding methods, even in your scenario.

Here's one reason, if your 'random password' consists only of the AES key, and you use the raw RSA operation on it (that is, zero pad it to the size of the RSA modulus, and then compute $M^e \bmod N$), then yes, there does exist weaknesses; there's a meet-in-the-middle attack on it that will search through possible values of $M$ faster than brute force.

Here's how that would work; in a preprocessing phase, the attacker would generate two lists of integers between 1 and $2^{128/2}$ (assuming we're attacking a 128 bit AES key) $A_i$ and $B_i$.  Then, he computes two lists, one consisting of the values $A_i ^ {-e} \bmod N$, and the other consisting of the values $B_i ^ e \bmod N$

Now, when the attacker sees an encrypted message $M^e \bmod N$, he computes the list $(M^e \bmod N) \cdot (A_i ^ {-e} \bmod N) = (M \cdot A_i^{-1})^e \bmod N$, and then scans that list for values in common with the $B_i ^ e \bmod N$ list (which can be done by sorting the lists and doing one pass through both of them).  If there is a pair with $(M \cdot A_i^{-1})^e \bmod N = B_j ^ e \bmod N$, the attacker then knows the value $M = A_i \cdot B_j$.

If the size of the lists $A_i$, $B_i$ are $k$ elements long, the attacker has just searched through $k^2$ values of the message in $O(k \log k)$ time.

Now, I'm not sure how much concern this attack would be in practice; however, RSA with standard padding methods do not have this concern; that would appear (to me at least) enough of a reason to stick with the standard methods.

Another way to look at it; raw RSA (that is, RSA without padding) is fragile; while RSA with good padding is not.  Given that good padding is easy to do, why wouldn't you do good padding?


Prove the size of a message in a succinct way A party A gives me a commitment of a message $m$ and want to convince B that is $|m|=L$. The proof myst be:

Non-interactive (a prover can convince me by sending me one message)
Succint (constant or sublinear size in the length of m)

I was looking into the NIZK space but I could not think of any solution.

Note: I have a candidate which however, it really is an overkill:

  Create a SNARK proof that proves the witness: $m$ such that length is $L$ and hash is $H(m)$, where $H$ is a cryptographic hash function and $H(m)$ is public knowledge (so verifier knows)

If the commitment is additively homomorphic then there are methods of doing this. They relate more to the numeric range, but these are essentially equivalent. First, it is possible to use the proofs of non-negativity of Helga Lipmaa in On Diophantine Complexity and Statistical Zero-Knowledge Arguments. These prove maximum by using the additive homomorphic property to subtract the minimum value, and then have the prover prove that the result is non-negative. Simpler solutions (some a bit weaker) appear in Efficient Proofs that a Committed Number Lies in an Interval. I don't remember if these can be made non-interactive using Fiat-Shamir, but I think that they can (and they are enough for you to start doing your own research into it).


Adding curve25519 to tinyec I am testing a TLS server that uses x25519 for key exchange. I am relying on Scapy-ssl_tls for building the TLS connection. However, this tool uses tinyec as its crypto library, and tinyec  does not have curve25519 in its registry, thus this whole setup does not work.
Does anybody know how could I add the curve25519 to tinyec? Since its 'registry' is just a bunch of hardcoded values (see below), I assume if I had these values for curve25519, that should be enough for my testing.
                     "secp192r1": {"p": 0xfffffffffffffffffffffffffffffffeffffffffffffffff,
                                   "a": 0xfffffffffffffffffffffffffffffffefffffffffffffffc,
                                   "b": 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1,
                                   "g": (0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012,
                                         0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811),
                                   "n": 0xffffffffffffffffffffffff99def836146bc9b1b4d22831,
                                   "h": 0x1},

Tinyec only supports Weierstrass curves, with an equation of the form $y^2 = x^3 + a x + b$. Curve25519 is a Montgomery curve, with an equation of the form $B y^2 = x^3 + A x^2 + x$. Tinyec's arithmetic can't do Curve25519 since its $A$ parameter is nonzero.
It would be less work to adapt Scapy-ssl_tls to one of the existing interfaces to Curve25519 than to write Montgomery curve arithmetic yourself.


Multiplication and squaring the binary polynomials I have tried to calculate $trace$ of a coordinate $X$ of EC in binary representation. Before that I tried to pre-calculate traces of the various bits of $X$ using formula:
$$Tr(X) = Tr(\sum_{i = 0}^{m-1} c_ix_i)= \sum_{i = 0}^{m-1}(c_i Tr(x_i) )$$

For the field $F_{2^{163}}$ that i use  we have only 2 cases $x_i$ that yield  $Tr(x_i) = 1$ to common $trace$. This cases  when $i$ - 0 and 157. With 0 is ok
but for others cases squaring the polynomials and reduction by modulus lead to the performance issues.

I would be appreciated if anyone proposes a more effective approach to such calculations. Or any references to ready implementations or services which can be used to calculate traces

What do you mean by trace of "bits" of $X$? How do you define $x_i$?

Since $263$ is prime, the field $\mathbb{F}_{2^{163}}$ has no subfields other than the prime field $\mathbb{F}_2.$ This means that the trace function $$Tr:\mathbb{F}_{2^{163}}\rightarrow \mathbb{F}_2$$ is the only trace which exists for this field. However, this means that the function $Tr(u)$ is equidistributed on $\mathbb{F}_{2}$, which means it is $0$ half the time and $1$ half the time as $u$ ranges over $\mathbb{F}_{2^{163}}.$

This property would also apply to any "bit" of $X$, reasonably defined as the coordinate of $X$ with respect to some basis element.

Edit:  If as in my comment $u=\alpha^i$, squaring gives $u^2=\alpha^{2i}.$
So square of $e_i$ is $e_{2i}$ but if $2i\geq n=163$  it needs to be reduced mod the field defining polynomial.

In $\mathbb{F}_{2^4}$. defined by $\alpha^4+\alpha+1=0,$
$\alpha=e_1=0010,$ $\alpha^2=e_2=0100,$ but $\alpha^4=\alpha+1=e_1+e_0=0011.$


How can we effectively compute the sqrt of some element in the group? I only know one way, if this group is a cyclic group, and we know the element can be expressed in $g^m$, then $g^{(m/2)}$ is the answer.

Another question, if $m$ is an odd number, can we be sure there is no answer?
Is it possible to find another generator $g_1$ and an even number $k$ that satisfy the element = $g_1^k$?

If we don't know whether or not the group is cyclic group, the complexity to find the sqrt or to confirm such an answer not exists is as difficult as DLP ?

TL;DR: Efficient algorithm only exist in specific cases. The problem, in its full generality (finite abelian groups) is equivalent to the integer factorization problem.

  How can we effectively compute the square root of an element in a group?

One case where we can compute a square root is when the group order is known and it is odd.
Any element $g$ in a group has the following property: if $q$ is the order of the group, then $g^q=1$. This is due to Lagrage's Theorem. Equivalently, $g^{q+1}=g$. If $q$ is odd then $\frac{q+1}{2}$ is an integer, hence we can compute $h:= g^{\frac{q+1}{2}}$, which is a square root of $g$.

Another case is the following: Assume $G$ is isomorphic to the direct product group of $k$ copies of the group of order 2 and a group of order odd $q$:
$$
G \simeq \mathbb{G}_q \times  \prod_{i=1}^k \mathbb{Z}_2
$$
where $\mathbb{G}_q$ denotes a group of order $q$ and $\mathbb{Z}_2$ the group of order 2. Also, importantly, assume you know how to compute this isomorphism.

In the group of order 2, the non-unit element is its own inverse, hence it has no square root. This implies the following: Let $g \in G$. Apply the isomorphism to get the representation of $g$ as an element in the direct product above: $g = (g', g_1, ..., g_k)$, where $g' \in \mathbb{G}_q$ and $g_i$ is in the $i$'th $\mathbb{Z}_2$. If there exists $i$ such that $g_i$ is not the unit element, then $g$ does not have a square root.

On the other hand, if $g_i$ is the unit element in all copies of $\mathbb{G}_2$, then the problem reduces to the case of a group of odd order: you just raise $g$ to the power of $\frac{q+1}{2}$.

  Another question, if $m$ is an odd number, can we be sure there is no answer?

No. The above explains this too. Actually, for the above, you don't need to know $m$ (which is typically the case).

  Is it possible to find another generator $g_1$ and an even number $k$ that satisfy the element is equal to $g^k$?

The above addresses this too, since it fully describes the set of squares in the group.

EDIT:

In "Oded Goldreich, Computational complexity: a conceptual perspective" it is shown that finding square roots modulo composite numbers is a computational problem equivalent to integer factorization. Hence, don't expect any "general purpose" algorithm, only algorithm for special cases. One such case is the multiplicative group of invertible element in a field of prime size $p$ - called Tonelli-Shanks.


If attacker knows salt and hash, how is salt effective? Maybe I'm missing something, but if my salt and hashed/salted password are stored in the same place, how is salting any more secure than just hashing? Does this just rely on attackers not knowing how the salt is incorporated into the hash?

The resume of that other answer could be:

When you have a password hashed, it's hard (very hard) to find out what was the original password: you have to try all combinations, until you find the hash. That's brute-force.

Someone can speed up a bit this process, by pre-computing many passwords: he'll store all those passwords / hashes, and will try to find it when he needs.

Someone can also see that two hashes are the same, and then he'll know that both passwords are the same.

To avoid these weakness, you use salt: it's a not-secret value, unique to each login/password pair. That way, the 1st problem (pre-computed hashes) won't work anymore, because he should have generated those pre-computed tables (called rainbow tables) including the salt.

The 2nd problem is also addressed: since each login will have it's salt, even if the same password was used, the hash will be different, since (salt1 + password) is different from (salt2 + password).

And there is also some marginal benefit: the password ends up being longer, since it'll have the salt + password. Of course, it's not any help if you think that the salt isn't secret and the password will be brute-forced. The attacker will simply compute all the combinations appending the salt. But it's a benefit if you think that the salt, alone, has 8 characters (for example): then any pre-computed table with 8 or less characters is useless, because (salt + password) will be longer than 8 characters.


Is Shoup's Practical Threshold Signatures considered secure? I am planning to use threshold cryptography in a Java application. So far, I have only found ThresSig and a ECDSA implementation used in TwoFactorBtcWallet. However, ThresSig is based on a 15-years old scheme, Shoup's Practical Threshold Signatures, and I can't figure out how to re-use the aforementioned ECDSA implementation for my own needs (I am not even sure if the code supports more than 2 parties).

Are Shoup's Practical Threshold Signatures considered secure nowadays? Are there any well-known pitfalls or recommendation on sizes, etc.? If not, is ECDSA an appropriate building block and how?

Shoup proved security of his scheme in the random oracle model, which means that it should be "as secure" as RSA itself assuming you use a sufficiently strong hash function, which today should be SHA-2.

More important than the scheme itself, any implementation should be considered with some suspicion given the substantial history of buggy cryptosystems in the world; RSA is at least a tiny bit more forgiving than DSA/ECDSA in this regard.

In any case, I would suspect that threshold schemes, given their relative complexity, have some potential for side channel attacks, e.g., on timing.

Unless you require actual threshold signature capability, in which case one really needs to understand the schemes and implementations in depth, I would suggest using alternative methods that accomplish the same goal.

For example, one can simulate $t$-of-$n$ threshold signatures by issuing $n$ certificates and requiring that any $t$ of them sign a message before accepting that message. This unfortunately sacrifices some properties of threshold signatures (e.g., privacy) but can be more easily implemented using standard libraries.


What is preventing chaotic cryptology from practical use? What factor is preventing cryptography based on chaos theory from being of practical use? Is it because of the unpredictability of the system?

All chaotic crypto papers I have seen lack rigorous security analysis, their main shortcoming being that there is no understood mathematical machinery of the type used in non-chaotic crypto such as:

low differential probability
low linear bias
guaranteed period, window, nonlinearity properties

Also, most chaotic systems are continuous, need infinite precision real numbers to represent, so since sampling/quantization will be needed, some of the properties of chaos may be lost.

Most chaotic crypto papers appear in the general physics/engineering literature, and are not even seen by most crypto researchers.

So, why would anyone use them when there are well understood techniques with long history of resisting cryptanalysis. The chaotic crypto authors display computational evidence (equidistribution only, in most cases) and quit.

If they dont properly cryptanalyze their designs no one else will. However, typical chaotic systems are almost impossible to analyze theoretically, their state trajectories are uncontrollable, by definition.


Why use a date-dependent substring of a pre-shared key instead of just the key? I've recently come across a situation where one system passes an encrypted payload to another system. The payload is encrypted using a pre-shared key. However, instead of just using the key itself, a calculation is made using the current day and month to produce an integer value. This value is then used to retrieve a substring of the key. So if the output of the calculation is 10, the key used to encrypt the payload is a substring of the original key beginning at the index of 10. Both systems have this logic.

I understand this prevents someone who possesses the key but not the aforementioned logic from decrypting payloads, but is this necessary or an industry standard solution to this problem? I've never encountered it before and I'm not sure what terms to use for further research.

Any insight is appreciated!

EDIT: I suppose the original "key" isn't really a key...it's a password the keys are derived from.

It is definitely not an industry standard solution. It looks like what the system designer wants to enforce is changing the key everyday. Essentially, it is a naive (and not secure) session key scheme such that each session lasts a day.

The idea of using session key is quite common in secure communication. Cryptanalysis becomes easier if the attacker can have more ciphertexts encrypted with a specific key. Thus often we want to limit the amount of data encrypted under a particular key. This is done by key exchange/establishment protocols that generate random, short-lived keys and secure distribute to sender/receiver. The random keys are called session keys because they are only used in one session. The security of the distribution usually requires e.g. a pre-shared key or asymmetric keys.

Going back to the scheme you mentioned, it is not secure because of many design flaws, e.g. the session keys are not randomly generated, are related to the pre-shared key, and can be re-used. It does not provide much additional security, e.g. if the attacker possess the pre-shared key, he can enumerate the session keys without much effort. It may even weaken the security of the system.


Is a digital signature of use if you don't also encrypt the message containing it? I'm sure this has been asked before. Its just too blindingly obvious.

from wikipedia

"Digital signatures, in which a message is signed with the sender's private key and can be verified by anyone who has access to the sender's public key."

So lets say Bob sends Alice an unencrypted message, and Charlie overhears it. What's to stop Charlie from signing his own messages with that private key and  henceforth having the ability to impersonate Bob?

So is there a point to digitally signing some message that isn't also encrypted? Or are all communications using digital signatures also encrypted? Wikipedia made it seem like there were two independent ideas, but I can't see a use case for signing-without-encrypting, where I can for encrypting-without-signing and encrypting-and-signing.

So lets say Bob sends Alice an unencrypted message, and Charlie overhears it. What's to stop Charlie from signing his own messages with that private key and henceforth having the ability to impersonate Bob?

Alice already possesses Bob's public key $\text{pub}_{B}$, and Bob is the only one that has access to the corresponding private key, $\text{priv}_{B}$.

The private key is not shared with anyone, while the public key can be published.

Bob can use $\text{priv}_{B}$ to perform the sign procedure which creates a signature $s$ from a message $m$.

Then Alice acquires $s, m$ and can use them with $\text{pub}_{B}$ to perform the verify procedure, which only outputs $1$ if $s$ was created using $m, \text{priv}_{B}$.

Charlie does not have $\text{priv}_{Bob}$, and so he cannot create a value $s$ for any $m$ that will pass the verify procedure that Alice will perform. (At least, he cannot do so with non-negligible probability, assuming that the signature scheme is secure).

  So is there a point to digitally signing some message that isn't also encrypted?

Yes

  Or are all communications using digital signatures also encrypted?

No

  Wikipedia made it seem like there were two independent ideas

They are two independent ideas.

Digital signatures provide authenticity and integrity of the signed message - if the signature verifies correctly, then you know that the message came from Bob and was not tampered with.

Encryption provides confidentiality, which means that unauthorized parties cannot learn the contents of the message.

  but I can't see a use case for signing-without-encrypting, where I can for encrypting-without-signing and encrypting-and-signing.

There are plenty of use cases for signatures without encryption.

Exchanging public keys for public-key encryption or key agreement is one of the most important examples (e.g. Public key Infrastructure).


Symmetric algorithms are secure post-quantum, only with less bits of security (usually about half). That means you only need to care about the authentication and key exchange parts of the cipher suite. Suites that don't use public key authentication or key exchange, i.e. preshared key suites, are post-quantum secure, but not useful in most usecases.

There are post-quantum ways to do key exchange, but SSL/TLS does not currently support any.

(In practice, at least. There is an old draft for NTRU in TLS, and apparently even some implementation(s), but the usual SSL libraries do not support it.)


How to decrypt a '.enc' file that has been encrypted with RSA using a public key? While solving a CTF challenge online, I came across a situation where I needed to decrypt a '.enc' file that has been encrypted using someone's public key. The corresponding public key '.pem' file was provided to me. I solved almost all other CTF challenges except this one and it has been bugging me since. I solved the first part: I have been able to decode a hint that says: "The file file.enc could be decrypted with a private key. Using raw algorithm, every 64 bits chunk of data was encrypted at a time. You can do the same thing to decrypt using RSA."

Here's what I have tried:

Read many posts like this one online and tried to decrypt the '.enc' file: http://www.czeskis.com/random/openssl-encrypt-file.html

I tried the following command for decryption: openssl rsautl -decrypt -in public_key.pem -out key.bin. I got the this error:

 no keyfile specified
 unable to load Private Key

Yes, but that's because private key is not provided to me. If I try to use the public_key.pem as infile, I get this error:

unable to load Private Key
139914348455592:error:0906D06C:PEM routines:PEM_read_bio:no start line:pem_lib.c:703:Expecting: ANY PRIVATE KEY

Tried the tool 'openssl' in Linux in several ways to try to decrypt the file.

Here is the 3 files zipped in tarball, if anyone wants to analyse them: http://www.filedropper.com/chaltar

Could someone please advise me on how to decrypt the '.enc' file before I give up on this challenge? I have worked long and broken the first part of the challenge, now I feel I'm so close.

Facts:

I know the tool 'openssl' will be used to solve this challenge.
Encryption: RSA
Files: Only three files, public_key.pem, file.enc,
and a random file that I decrypted that provided the hint I wrote
above.

openssl rsa -pubin -inform PEM -text -noout < public_key.pem
Public-Key: (64 bit)
Modulus: 16513720463601767803 (0xe52c8544a915157b)
Exponent: 65537 (0x10001)

The modulus is small enough that you can easily factor it

After finding the prime factors, you can calculate the private exponent

After you have the private exponent, you raise each 64-bit block of ciphertext to the private exponent mod the modulus.


How to find the decryption algorithm for this encryption scheme? $\mathrm{KGen}(\kappa)$: Let $(\mathcal G, g, q) \gets \mathrm{GenG}(\kappa)$ be a cyclic group of prime order $q$. Choose random generators $g_0, g_1 \gets_R \mathcal G$, random exponent $x \in_R \mathbb Z_q \setminus\{0\}$, compute $h = g^x$, return public key $pk = (\mathcal G, g, q, g_0, g_1, h)$ and private key $sk = x$.

$\mathrm{Enc}(pk, m)$: Parse the 2-bit $m$ into its bits $m_0m_1$. Choose random $r \in_R \mathbb Z_q$ and return $c = (c_1, c_2) = (g^r, g_0^{m_0}\cdot g_1^{m_1}\cdot h^r )$.

Given this key generation scheme and this encryption algorithm, how can I find the decryption algorithm $\mathrm{Dec}(sk,c)$?

How do decrypt?  Lets do the easy part first:

Given the ciphertext $(a, b) = (g^r, g_0^{m_0} \cdot g_1^{m_1} \cdot h^r)$, with the private key, we can compute $a^{-x} b = g^{-rx} g_0^{m_0} g_1^{m_1} h^r = g_0^{m_0} g_1^{m_1}$

Now comes the tricky part, now that we know $g_0^{m_0} g_1^{m_1}$, how do we solve the discrete log problem to recover $m_0, m_1$?

Without making additional assumptions on the group $\mathcal G$, the best we can do (assuming that $m_0, m_1$ are known to be at most $k$ bits long) is a generic log algorithm that takes $O(2^k)$ time.

One way is to do this is to have precomputed the values $g_0^{-0}, g_0^{-1}, g_0^{-2}, ..., g_0^{-2^k+1}$ and $g_1^{0}, g_1^{1}, g_1^{2}, ..., g_1^{2^k-1}$, and for each $0 \le i < 2^k$, compute $g_0^{m_0} g_1^{m_1} \cdot g_0^{-i}$ and see if it matches any of the $g_1^j$ values; if so, then we have the decryption $m_0 = i$ and $m_1 = j$.

Of course, there is a possibility (given that $g_0, g_1$ was selected randomly) that the decryption might not be unique.  This possibility can be checked at key generation time, and a different $g_0, g_1$ pair be selected.


Why is the vector sampled from Gaussian or Subgaussian distribution in lattice-based cryptography? I have known that the vector is sampled from Gaussian distribution in lattice-based cryptography because the distribution of the vector $\mod{\mathcal{P}(\mathbf{B})}$ approximates to uniform distribution.

It is proved by below lemma.

  For any $s > 0$, $\mathbf{c} \in \mathbb{R}^n$, and lattice $\Lambda(\mathbf{B})$, the statistical distance between $\mathcal{D}_{s,\mathbf{c}} \mod{\mathcal{P}(\mathbf{B})}$ and the uniform distribution over $\mathcal{P}(\mathbf{B})$ is at most $\frac{1}{2} \rho_{1/s}(\Lambda(\mathbf{B})^*\backslash\{\mathbf{0}\})$. In particular, for any $\epsilon >0$ and any $s \geq \eta_{\epsilon}(\mathbf{B})$, the statistical distance is at most $\Delta(\mathcal{D}_{s,\mathbf{c}} \mod{\mathcal{P}(\mathbf{B})},\mathcal{U}(\mathcal{P}(\mathbf{B}))) \leq \epsilon/2$.

But if the vector is sampled from uniform distribution at first, the distribution of the vector $\mod{\mathcal{P}(\mathbf{B})}$ is uniform. So, I thought that Gaussian sampling is not needed for above reason, because Gaussian sampling requires large costs.

Another reason I think is that the smaller vector is preferred because almost lattice problem is about finding short vector and Gaussian variable has higher probability as closer to the center. Is it right?

If my thought is not correct, let me know the reason using Gaussian distribution in lattice-based cryptography.

You can't directly sample uniformly modulo a lattice unless you know what the lattice is. The Gaussian distribution can be sampled independently of knowledge of the lattice. This distinction is important in situations where the lattice is part of a cryptographic secret.


What is the "standard model" for block ciphers? In this paper and this the authors speak of a "standard model". What is the "standard model"? How does it differ from the "ideal model"? Why does the decision to use it or the "ideal model" impact the security bounds of their schemes?

In the standard model, the block cipher is modeled as a pseudorandom permutation (when using a random key). The adversary has oracle access to either the block cipher instantiated with a random key or a truly random permutation, and has to try to distinguish between them. In the ideal model, the block cipher is modeled as a family of truly random permutations; a different independent one for every different key. This is similar to the random oracle model, but even stronger (in some sense).

In what sense is it stronger? Well, it's stronger in the sense that there are functions that are random oracles but certainly not ideal ciphers. For one, a random oracle need not have the same domain and range. In addition, it can have collisions. In addition, they don't have two separate inputs (key and input). However, as an \emph{assumption} they are actually equivalent in that you can build an ideal cipher from a random oracle. This was proven (incorrectly initially, and then fixed). See the paper Equivalence of the Random Oracle Model and the Ideal Cipher Model, Revisited for this.


Are specially designed fonts sometimes used in cryptography? As a font designer, I was thinking that it would be very easy to design a special font that could either jumble characters of a language (or of a code) or simply (with the features offered by the OTF format) overlap into a complex design that only the other user (the reader) would be able to unscramble...
Is this something that exists and could be plausible?

EDIT: To better explain myself, I just created this image.
(A) represents a whole sentence. Each circle is a word.
(B) details two different kinds of "words" that could exist: wavy, straight lines... but always with 26 peaks (for example an alphabet with 26 letters). When one single letter from a font is typed, just one wave or peak would be drawn until the whole word is typed.
(C) is another detail of overlapping of two circles, each one is a word.
(D) explains how a word could be read: each circle having 26 peaks, the distance of the peaks from the center tells the reader what letter it is. I made the distance very visible in (D) but it could be extremely subtle / only visible when analysed by microscope/etc.

Such a code could exist on the front page of a newspaper and no one would notice. And it's all encodable in a "simple" OTF font...

Is this something that exists and could be plausible?

Yes, things like that already exist and have even been used by well-known serial killers!
(So much for creating a dramatic intro – lol)

Monoalphabetic Substitution Cipher

What you are referring to, could be categorized as a classical “pigpen cipher”; a monoalphabetic  substitution cipher where graphical symbols are used. You might change the symbols and maybe even the way you encode things, but replacing text with symbols will always boild down to a simple, monoalphabetic substitution cipher.

Nowadays, you won´t find too many examples of it in action, but things looked different hundreds of years ago when a simple substitution cipher was able to baffle the masses. Yet, those days have long gone and suchs ciphers can now mostly be found in children's books on ciphers or “secret writing” gimicks packed in breakfast cereal boxes.

The rare exceptions to this rule are limited to things like (for example) the notes from the “Zodiac Killer”. But – all in all – the enigmatic charisma of “danger” and “death” provided more mystery to those notes than the usage of symbols… something which can be broken/deciphered rather easily, assuming enough data or information is available.

Modern Cryptography and Kerckhoffs' Principles

For better understanding: in modern times (and on this site), we tend to handle cryptography according to well-vetted rules… among them some which go back to Kerckhoffs' principles, which defines that a cipher algorithm should be made public (aka: regarded to be known by “the enemy”).

One of the reasons why some notes by the Zodiac Killer haven´t been deciphered yet, lies exactly in that area: the algorithm was never published and the data provided by the Zodiac killer did not provide enough information to deduct the actual contents of the ciphertext with absolute confidence.

Now, please don´t get me wrong. As someone who has professionally designed some fonts for advertising and other purposes, I am always intrigued by the idea of putting some visuals in communication. But I can´t help to share my two cents to spare you from walking the wrong path unwillingly:

Would it make sense from a modern-day cryptographical point of view to create such fonts?

No. Not if you actually expect them to provide any kind of real cryptographic security.
Would it be a nice hobby and find some fans nevertheless?

Sure… as long as you keep in mind you´ll most probably be spending more time creating the fonts than others (cryptanalysts, as well as “ye average” puzzle freaks) will need to break the ciphertexts created with them.

Let´s take your font idea and put it on the front page of a newspaper as you implied. That might work once. But the more you publish, the more data will be available and since we´re practically talking about a monoalphabetic  substitution cipher, it won´t take too long for the first people to decipher your stuff by “guessing” the keys (with merely a sprinkle of Cryptanalysis).

Especially, since you´re even limiting the security down to…

  26 peaks

… instead of the 256 “peaks” (= 8 bits = 1 unsigned byte) we work with in modern crypto.

As a simple rule of thumb: The smaller the alphabet, the easier the cryptanalysis!

I surely agree with you that one can hide a secret in the open. But as soon as someone knows there´s a secret to look for, security starts to fade towards zero. That´s where you need a secure cipher, and – whether we like it or not – fonts can not replace cryptographically secure algorithms.

Nota Bene

If you want to take a look around at the different fonts and symbols, use your preferred search engine to check on “cryptography symbols“ and co.

You´ll also discover your idea is already used and published in newspapers as (cryptographic) puzzles. There are even a few pages diving into such graphical ciphers. One of many: http://www.phantomgallery.64g.ru/shiphen/cod6en.htm


Can SHA256 hash be considered as a secure key proof? I want to use PBKDF2 with 1,000,000 iterations (I don't know yet exactly how many I will choose) to derive a 256-bit symmetric key K from a password provided by a user (at least 40 bits of entropy). Then I would like to have a proof that the user has/knows the key K. The key will be hashed once with a SHA256 function and the result H will be stored in a database (SHA256(key)). So, whenever I will need to verify that the user has the key K, it will be hashed on frontend and only the H value will be sent to the server, so I can compare it with the value stored in DB. The key will never leave a user's computer.
Let's say a hacker wants to find out what the 256-bit key is. There are two ways:

Brute force password - since we are using slow hashing function (PBKDF2) and at least 40-bits of entropy passwords, it will take years.
Try to find out the key by attacking from "the other side". So, the hacker will need to find a preimage, thus key K of the hash H. As we know SHA256 is one-way function, so it is nearly impossible.

The question is: are there any possible vulnerabilities in this solution? I know that finding a 256-bit random preimage of SHA256 is not possible, but we are not dealing here with a "true" 256-bit value generated by a cryptographically secure random number generator. The 256-bit key K we are dealing with is in fact derived from a user password which entropy is much, much lower, let's say only 40 bits.
What I understand is that from the perspective of a second attack we can treat the key K as a true 256-bit value because we have to find out the exact 256-bit value. We don't need to worry that it was derived from a source with 40-bits entropy. We have to worry about this only in the first scenario, so that's why I want to use a slow hashing function.
Conclusion: it is more likely the key K will be found by following the first way of attack than the second one, thus this only one SHA256 hashing round is secure. If I want to make the entire solution more secure I should consider more PBKDF2 iterations or the PBKDF2 should be replaced with a better function (like Argon2). Am I right?

Then I would like to have a proof that the user has/knows the key K. The key will be hashed once with a SHA256 function and the result H will be stored in a database (SHA256(key)). So, whenever I will need to verify that the user has the key K, it will be hashed on frontend and only the H value will be sent to the server, so I can compare it with the value stored in DB.

How does that prove that client (who may be pretending to be the user) knows the key?  He obviously knows SHA256(key), but he might have gotten that from the real user.
Even if the negotiation between the client and the server was encrypted (which you do not specify), one obvious approach for an adversary to get that value is to pretend to be the real server, and have the client attempt to log in (and that client will send that SHA256(key) value as a part of the exchange).


Is there any asymmetric encryption algorithm for eliptic curve(secp256k1) without AES? I am looking for asymmetric encryption using SECP256K1. But all over the internet, I see that it also requires AES encryption. Instead of generating an AES secret key, is it possible to encrypt using the public key alone?

You can encrypt with secp256k1 (or any elliptic curve) by using ECIES (Elliptc Curve Integrated Encryption Scheme). However, inside ECIES a symmetric key is generated and the message is encrypted using it.

This is in contrast with RSA, which can encrypt data directly; though most of the time it is also used to encrypt a symmetric key and then encrypt data with that key.

If you really want to avoid AES, then you can use the secret derived inside ECIES and simply XOR with your message. Check the SEC 1 standard, section 5.1.3.


In which case number field sieve/index calculus is faster for solving discrete logarithm? Given the normal discrete logarithm problem:
$$a = b^c \mod{P}$$
with prime $P$ and numbers $a,b,c$
For which kind of $P,b$ the NFS/IC algorithm is faster than Baby-Step/Giant-Step+ Pollard's Rho ($\approx \mathcal{O}(\sqrt{q}) $)?
(with $q$ the biggest prime in factorization of $P-1$, with $P$ big prime)
Or in which cases NFS/IC it used?

Using its notation, the question is about the difficulty of the Discrete Logarithm Problem in a Schnorr Group modulo $P$, of prime order $q$. I'll assume $b^q\bmod P=1$ and $b\bmod P\ne1$.
That DLP problem is finding $c$ chosen at random in $[0,q)$ given $P$, $q$, $b$, and $a$ obtained as $b^c\bmod P$. Depending on parameters, the best known algorithms fall into two complexity classes:

somewhere between $\mathcal O(\sqrt{q}\,\ln P\,\ln\ln P)$ [in theory] and $\mathcal O(\sqrt{q}\,\ln^2 P)$ for Baby-Step/Giant-Step and it's practical improvement: Pollard's Rho with distinguished points (which can be efficiently distributed and requires little memory; see Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999). The cost is often stated as $\mathcal O(\sqrt{q})$ multiplications of integers of size $P$, and this has been recently shown to cost $\mathcal O(\ln P\,\ln\ln P)$, see this.

something like $\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln P)^{\frac{1}{3}}(\ln \ln P)^{\frac{2}{3}}\right)$, for the Number Field Sieve applied to the Discrete Logarithm (see this).

in which cases is NFS/Index Calculus used?

For a given size of $q$, the first class of algorithms (Pollard's Rho..) is best for large $P$. The second (NFS) is faster for relatively small $P$, including $q$ a Sophie Germain prime (equivalently, $P$ a safe prime).
For 256‑bit $q$, the first class of algorithm is better for 8192-bit $P$, the second for 512‑bit $P$. I prefer not digging where exactly the crossover is, or what's the exact difference between NFS and IC.


Is there a block cipher mode that doesn't use the key input of the block cipher? Is there a block cipher mode that does encryption and decryption without using the "key" input of the block cipher?

I ask this because rekeying a block cipher can be an expensive process, and I intend to encrypt many blocks with many different keys.

Is there some mode or construction that has the security of the underlying cipher, while not using it's key input?

This is the difference between block-encryption (with a mode) and permutation-based encryption.

I. Block encryption

Split your message in blocks of the width of the block-cipher, apply a transformation (XOR of the previous ciphertext, XOR of an IV you name it...) and then apply the block cipher.

On a high level, it can be summarized as the following Figure where $K$ is your key, $P_1 \ldots P_n$ are the plaintext blocks, $randomize$ correspond to an operation trying to remove similarity between blocks (remove ECB...) and $C_1 \ldots C_n$ are your ciphertext blocks.

           P_1                 P_2                     P_n

            |                   |                       |
         randomize           randomize               randomize
            |                   |                       |
       +----v----+         +----v----+             +----v----+
       |         |         |         |             |         |
   K ->|    B    |     K ->|    B    |  ...   K  ->|    B    |
       |         |         |         |             |         |
       +---------+         +---------+             +---------+
            |                   |                       |
            |                   |                       |
            v                   v                       v

           C_1                 C_2                     C_n

Of course one could argue that CTR does not work that way, but the principle is the same, you encrypt the counter and XOR the result to the plaintext.
In the end, the process is very similar.

Note: If you are using a different key for each block, you are doing it wrong...

II. Stream encryption

This mode does not requires you to split your plaintext in blocs. You just generate a keystream and Xor it. Nothing fancy, simple, fast and efficient.

                   K

                   |
            +------v-------+
            |              |
       IV -->   Stream     +----+  Keystream
            |              |    |
            +--------------+    |
                                v
Plaintext ----------------------+---> Ciphertext

Examples of this construction are Chacha20, Salsa20...

III. permutation-based encryption

Permutation-based encryption works in a similar fashion as the stream and the block encryption. The key is set at the beginning of the encryption and not used after. The message is split into chunks. This mode is based on a sponge construction

The key stream is then XORed with the message, resulting in the Cipher text.
Examples of this construction are Keyak, Ketje, NORX...

IV. Going further

From that permutation based mode, you can use it in a session style, removing the need to have a key once the session has been initialized.

More readings:

- FSE 2017 - Innovations in permutation-based encryption and/or authenticationInvited Talk by Joan Daemen


How much faster in symmetric cryptography compared to asymmetric cryptography? I know that symmetric cryptography is faster than asymmetric, but on average how much faster would it be if you were encrypting and decrypting a 2MB file?

The page https://www.cryptopp.com/benchmarks.html has a comparison of the speeds of a number of different algorithms.  You will have to do a little math to covert to the time necessary to encrypt a 2MB file, but this should give you the base information necessary.


usefulness of a collision attack that's not also a 2nd pre-image attack So my understanding is that if we've got some hash function $H$ then a 2nd pre-image attack is one where given a message-hash pair $(m, H(m))$ we can find some $m' \neq m : H(m') = H(m)$, while a collision attack is to find any old $m, m'$ such that $H(m) = H(m')$.

Everywhere I see people talking about collision attacks it really seems that they mean 2nd preimage. What would be the usefulness of a pure collision attack where you have no control over $m$ or $m'$? There are all those results about how SHA-1 is broken w.r.t. collision attacks, but it seems that people really mean 2nd pre-image. Is this just a convention that people are not strict about, or am I missing something?

For example, in this SE question the author of the accepted answer gives an example of where a collision attack could be used to swap out malware for a valid Windows update. But to me that seems to be a 2nd pre-image attack, not a pure collision attack, because the attacker needs to ensure that the hash of the malware matches a particular hash, i.e. that of the Windows update.

What would be the usefulness of a pure collision attack where you have no control over $m$ or $m'$?

One example is when $m$ and $m'$ are or contain randomly selected material.  If they're using cryptography correctly, the honest parties generally choose keys, random IVs or similar material randomly, and thus have no control over what their values are either.  This affords many opportunities for attacks that require finding some collision but don't care about what the colliding values are.

One example is secure coin tossing.  If Alice is calling the toss and Bob is throwing it, they execute this protocol:

Alice secretly picks her call (Heads or Tails) for the toss, and a sufficiently large random salt;
Alice computes commitment = hash(salt || call);
Alice sends commitment to Bob.
Bob tosses a coin, gets outcome;
Bob sends outcome to Alice;
Alice sends call and salt to Bob;
Bob verifies that commitment = hash(salt || call).  If it checks out, Bob knows Alice didn't cheat.
If outcome = call then Alice won the coin toss, otherwise she lost.

If Alice can find any pair of salts such that hash(salt1 || Heads) = hash(salt2 || Tails), then she can break the protocol.  It doesn't matter what the values of salt1 and salt2 are as long as they lead to a collision in this context.
 So collision resistance implies Alice can't cheat this protocol.

To address Ross Snider's answer you linked from another SE site.  I'll boldface one really important bit:

    Bob can use a collision attack to his advantage in many ways. Here is one of the simpliest: Bob finds a collision between two binaries $b$ and $b′$ ($H(b)=H(b′)$) such that $b$ is a valid Microsoft Windows security patch and $b′$ is malware. (Bob works for Windows). Bob sends his security patch up the chain of command, where behind a vault they sign the code and ship the binary to Windows users around the world to fix a flaw. Bob can now contact and infect all Windows computers around the world with $b′$ and the signature that Microsoft computed for $b$.

  But to me that seems to be a 2nd pre-image attack, not a pure collision attack, because the attacker needs to ensure that the hash of the malware matches a particular hash, i.e. that of the Windows update.

It is a collision attack indeed, not a second preimage attack, and it hinges on these points:

"Bob works for Windows."  This may be a parenthetical in the quote, but it is a critical assumption.  The scenario assumes (perhaps less than explicitly) that Bob is the author of both the legitimate patch and the malware, and gets to craft them together as a colliding pair.  That's the assumption that you're missing; if instead Bob was trying to construct a malware patch that matched a legitimate one that somebody else constructed, then you would be right and it would indeed be a second preimage attack.
Executable file formats allow for arbitrary data to be embedded into a file without affecting the program's runtime behavior.  This means that Bob gets a lot of latitude to embed random data into both the legitimate patch and the malware.

Those two factors taken together are what allows Bob the opportunity to try a much cheaper collision attack instead of a second preimage attack.


Which hash function to be used with DSA 2048 I'm preparing for an examination of an Information Security course at university, but I'm not sure about an explanation I created for a specific exercise. The question is:

  There are now DSA versions using a 2048 bit prime number. Which hash function would you choose?

My answer:

The goal of the hash function is to provide enough security, while not being overkill for it's application. DSA works by choosing a prime number p (of length 2048 bits in this case), and a prime number q (160 bits for the 1024 bits case of p, so more than 160 bits for the 2048 bit case). Then the value s is generated by calculating s = [k^-1 * (H(M) + x * r)] mod q (with x being the private key and r being a value that was generated earlier in the process). Now because the generated value is calculated mod q, the result is no longer than q itself.

It is thus pointless (or overkill) to use a hash function that produces values with more than |q| bits. We know that |q| > 160 bits (and it will presumably be no longer than 256 bits). This allows us to choose for SHA-256 as an appropriate hash function, as it is not yet known to be broken, and produces the smallest hash values not known to lower the degree of security of our DSA algorithm.

Is this a correct explanation for this problem? I can't seem to find the rational behind some hash function choices for DSA elsewhere.

This is reasonable and gets at most of it.

One critical limit of DSA with a 160-bit prime group is that you can't get better than 80-bit collision resistance by the birthday bound.  You really want a uniform random function from whatever is your finite message space to $\mathbb Z/q\mathbb Z$, but that's a pain to achieve, so you might choose a $\lceil\lg q\rceil$-bit hash function like SHA-1—but SHA-1 is known not to be collision-resistant at the maximum possible 80-bit security level in the circumstances.

You might be concerned about the small modulo bias of reducing a uniform random integer in $\mathbb Z/\lceil\lg q\rceil\mathbb Z$ modulo $q$.  You might be concerned about security against multi-target attacks.  If you are concerned about that, then you might choose a double- or 1.6-size hash like SHA-256 or BLAKE2s, and attain collision resistance up to the maximum possible 80-bit security level.

For a loose comparison, a double-size hash, SHA-512, was chosen for Ed25519's ~256-bit group, for several conservative reasons.  Now, the comparison is not precise, because Ed25519 is a qualitatively different signature scheme—and superior in pretty much every respect, except compliance with US government standards, to DSA: it uses the hash in a different way so it doesn't even rely on collision resistance, it doesn't break catastrophically and barf out your private key if you use it on a machine with a broken RNG, it's faster and smaller, etc.


Why isn't CTR mode (counter mode) used more often? For the CTR mode, the design is good for parallelization, yes, it seems the benchmark of the program downloaded from crypto++ proves that on an Intel I7 CPU.

My question is that as most of CPU on the computers today are multicore and designed good for multithread calculation, why not all people use the CTR mode as it is much faster than the CFB mode (about 4 times faster on Intel I7-4770K, 3.5GHz CPU)?

There are probably quite a few good reasons for this, although I don't expect that a scientific answer can be composed (as you would need to use a survey, and I've never heard of such a thing for modes of operation).

Let me list a few possible reasons:

Developers don't know about CTR mode of operation; most questions on StackOverflow are about ECB and CBC (I really hope that SO doesn't reflect corporate practices everywhere);
Even today it is possible that CTR mode is not available for some runtimes (only ECB and CBC mode are practically guaranteed on most lower level libraries);
(Older) protocols may simply specify other modes of operation.

With regards to the parallelism provided:

AES is already pretty fast, doubly so if AES instructions are present within the chip - for instance AES-NI within Intel/AMD CPU's - so the parallelism provided by CTR mode are not often required;
Many problems that require fast crypto are embarrassingly parallelizable by themselves (e.g. multiple file encryption and TLS sessions to a server);
Multi-threading is hard to get right, and may be hard to use (for instance, you may not want all your cores to be just encrypting data);

You think in CPU terms. Loads of people however don't use C/C++ but use higher level languages. These may have a totally different level of operation and may not have good support for modes of operation, let alone multi-threading support for these modes of operation.

If you want to create a protocol that is supported on lots of devices you may need to standardize on CBC as highest common denominator. C/C++ may be fast, but software created in those languages is also notoriously hard to secure, leaving you exposed to all kinds of attack. Speed is nice, but it is useless if you lose your data because of a buffer overflow.

In the cryptographic community CTR is probably the hottest mode in town. It is for instance used in GCM, CCM and EAX (authenticated modes of operation) as underlying mode to provide confidentiality. It has one particular cryptographic property that is not nice: nonce (IV) reuse is catastrophic to the confidentiality of messages send with CTR. The IV in CBC mode is harder to get right, but it doesn't fail as badly if you don't.

In the end, CTR mode is often simply not required. But with the advance of AEAD modes that use it for encryption / message confidentiality, it may be that it makes a stealthy comeback; many developers will be using it without even knowing that it is there.


Meet-in-the-middle probability of success In page 358 of Bruce Schneier's Apllied Crypto, when explaining the meet-in-the-middle attack, he states that the success probability is «1 in $2^{2m - 2n}$» with two plaintext/ciphertext pairs, and «1 in $2^{3m - 2n}$» if one uses one additional pt/ct pair. $n$ is the key length, and $m$ the block length.

My question is: shouldn't $m$ and $n$ be reversed? I.e. «1 in $2^{2n - 2m}$» and «1 in $2^{2n - 3m}$»? As stated in the book, we would get a lower success probability when using 3 pairs, as «1 in $2^{2m - 2n}$» is a bigger probability than «1 in $2^{3m - 2n}$» (because $2^{3m - 2n}$ > $2^{2m - 2n}$).

Or is there something obvious that I am not seeing?

In the sentence, the "probability of success" of «1 in $2^{2m - 2n}$» or «1 in $2^{3m - 2n}$» really is an approximation of the probability of concluding that the key was found, when in fact another key that happens to give the same result as the true key for 2 or 3 blocks was found.

It should be read "probability of wrongly concluding success" instead; or "probability of false positive".


Determining the encryption method I am trying to reverse engineer a program that encrypts a file with a password.

So far i figured out that the start of the file is always the string "DecryptOK" encrypted with the password of course.

With a password of "one" an "empty" file turns into

ED5BDE97BB90DE1377948A31B0EECB4B4D8B

which i assume would be

ED5B DE97 BB90 DE13 7794 8A31 B0EE CB4B 4D8B

aka "DecryptOK".

So my question is how do i continue from here? How do i figure out what encryption method is being used?

Here are some texts i encrypted with the password "one":

123 to 3366 7FAD CAF5
abc to 3336 7FFD CAA5
cookies to 3334 7FF0 CAA9 33F7 D2D2 60AB 86EB

So my question is how do I continue from here? How do I figure out what encryption method is being used?

It sounds like you, in essence, have black box access to something that allows you to give it a key and a file, and it returns an encryption of that file (after adding some file format around it) using the supplied key.

Your goal is to figure out how the encryption works. There may be legal issues you want to consider before actually doing this, but legal issues aside, you have many options.

Your best option would be to reverse engineer the code that is doing the encryption. Is this software running on your computer or some sort of hardware device? In either case, you should be able to get the code and reverse engineer it by putting it in a disassembler and doing static analysis, or putting it in a debugger and doing dynamic analysis.

Let's pretend, however, that you do not have access in any way to the code. Maybe this black box is running on a remote server that you do not have access to. Your goal then is to figure out what cipher are they using (e.g., AES, DES, 3DES, RC4, etc) and what mode of encryption is being used.

You can start to do this by asking a few questions and using your black box access to start answering the questions.

Is the encryption deterministic? Or in other words, given the same plaintext (or file) and key, does it always return the same result?
If I flip a single bit in the plaintext, how does the resulting ciphertext change?
What happens if you feed a ciphertext in as the plaintext, do you get the original plaintext back? In other words, is the encryption mode the inverse of itself?
By flipping bits at different places, can you figure out the block size? Depending on the mode used, where you flip bits can change what blocks actually change?
Something else to investigate is why does the ciphertext appear to always be double the size of the plaintext? When you pass in 123, which as ASCII would have 3 bytes, why do you get 6 bytes back? Is there some sort of encoding going on?

This is how I would suggest continuing from where you are.