Reversing N CRC steps Starting from a known CRC result(let's call it CRC1), could I undo the CRC operations for last N bits, so I could obtain the CRC (let's call it CRC2) of the message sequence without the last N bits.
$$
M(x) - message \\ M = \{M1,LastBits\} \\CRC_1=CRC\{M\}\\CRC_2=CRC\{M_1\}
$$
Does a function F() exist for which:
$$F(CRC_1,LastBits) = CRC_2$$

My hunch would be that such a function which would unrewind the last N CRC steps, would have 2N possible solutions.

This is easiest to understand if we use polynomial arithmetic.

The CRC of a message $m(x)$ is the remainder $r(x)$ of $m(x) x^k$ when divided by the CRC polynomial $f(x)$. Or more conveniently, the CRC is congruent to the message multiplied by $x^k$ modulo the CRC polynomial, $r(x) \equiv m(x) x^k \pmod{f(x)}$.

If the message consists of a prefix $m_1$ and a suffix $m_2$ of length $n$, we can express that as $m(x) = m_1(x) x^n + m_2(x)$. If the CRC of $m_1$ is $r_1(x)$ and the CRC of $m_2(x)$ is $r_2(x)$, then the CRC of $m(x)$ is $$r(x) \equiv (m_1(x) x^n + m_2(x)) x^k \equiv r_1(x) x^n + r_2(x) \pmod{f(x)}.$$

If $f(x)$ is not a multiple of $x$ (which it won't be), there is a polynomial $g(x)$ such that $x g(x) \equiv 1 \pmod{f(x)}$, and then $$r_1(x) \equiv r_1(x) (x g(x))^n \equiv (r(x) - r_2(x)) g(x)^n \equiv (r(x) - m_2(x) x^k) g(x)^n \pmod{f(x)}.$$

In other words, you find what you ask for by first finding $g(x)$, then computing a difference, multiplying by a suitable power of $g(x)$, then taking the remainder when dividing by $f(x)$.


Is there any reduction from Short Integer Solution to $\textrm{SIVP}_\gamma$ Short Integer Solution(SIS) is proved to be hard by reducing $\textrm{SIVP}_\gamma$ to SIS i.e., if we solve SIS, then we can solve $\textrm{SIVP}_\gamma$. Is ther any way to reduce an instance SIS to an instance of $\textrm{SIVP}_\gamma$?

If $A\in\mathbb{Z}_p^{n \times m}$, then you can define $$\mathcal{L}=\{y\in\mathbb{Z}^m~:~Ay=0\,\bmod\,p\}.$$

$\mathcal{L}$ is an $m$-dimensional lattice, and if you solve (search) $SIVP_\gamma$ in this lattice, it implies that you found a vector $v$ (actually many such vectors) such that $Av=0\bmod\,p$ and $||v||\leq \gamma\cdot\lambda_m(\mathcal{L}).$  So that's a solution to SIS.  When $m>n$ (say $m>2n$) and  $A$ is uniformly random, you can actually tightly bound the value $\lambda_m(\mathcal{L})$ to be around (ignoring some constants) $$\lambda_m(\mathcal{L})\approx \sqrt{m}\cdot \det(\mathcal{L})^{1/m}=\sqrt{m}\cdot p^{n/m}.$$
So, in short, if you can solve $SIVP_\gamma$ for random lattices of the above form, then you can find short vectors $v$ such that $Av=0\bmod\,p$ with $||v||<\gamma\cdot\sqrt{m}\cdot p^{n/m}$.


Is ECDH(E) Key Exchange FIPS 140-2 compliant? We have read dozens of documents now - some that contradict each other - and cannot find a solid source of truth. Does FIPS 140-2 compliance allow for the use of elliptic curve cryptography as a key exchange for TLS communication? ECDH and ECDHE - if so, which P-xxx key sizes?

If you look at the FIPS Implementation Guidelines for FIPS-140-2 here
https://csrc.nist.gov/csrc/media/projects/cryptographic-module-validation-program/documents/fips140-2/fips1402ig.pdf
In section D.8 Key Agreements, you will find the recommendations.
This recommendation points to NIST SP-800-56A, where in Appendix D, there is a table of  "Approved ECC Curves and FFC Safe-prime Groups."
SP-800-56A has references to FIPS186-4 and RFC4492 (for TLS) and RFC 5903 (for IKE).
These references should be enough to justify use of ECDH in a FIPS140-2 approved device.


Can a device prove the identity of its own code? Say you have a computing system that has some functionality that is not in itself cryptographically secure, but you want to make sure is executed as specified, and, e.g. an adversary hasn't re-flashed the software when you weren't looking. An example might be a voting machine for a non-crypto scheme, or verifying that a motherboard is running the factory's firmware.

Is there any sort of data or verification protocol that can be used to prove which version of the software is being run, that doesn't require physically disassembling the hardware, and is resilient against even an attacker who knows about it and who specifically designs their variant software to try to spoof it?

If nothing about the hardware (and its capacity) is known ahead of time, then AFAIK this is impossible because the attacker can just virtualise the entire "correct" software and return whatever it produces. (Although please correct me if this isn't true) Since that's not a very interesting scenario, instead assume

Both the verifier and the attacker have complete access to the "correct" software in machine code form.
The machine's memory capacity is fixed and known ahead of time by both verifier and attacker. (Or more generally, the machine's hardware configuration is known, and the attacker has not modified it except via software reprogramming)
If a handshake is involved, the verifier can be a trusted computer of arbitary capacity, not necessarily a human. (And so any computations the verifier has to do can be complicated so long as they're efficient.)
If the system's "correct" software has to be prepared in some unusual but efficiently doable way beforehand for the scheme to work, assume that has happened by the verification step.
Solutions that can be implemented in pure software are prefered, but solutions involving "small" hardware changes would also be acceptable. (Assume that simply replacing the program memory with ROM wasn't an option for whatever reason)

(As an example of what I'm looking for, one possible solution for this problem that occured to me was to construct the software image as normal, then pad it with random data up to the capacity of the machine's program memory. To verify, the verifier then provides the system a random number, the machine then computes the hash of that number prepended to the entire contents of its program memory (which it can't spoof because there's nowhere to store the "correct" copy to reproduce for this step) and gives that to the verifier. The verifier can then verify the hash the machine has given it against its own calculation. I haven't thought very hard about the implications of this scheme though, or how to attack it, so I think I'm missing some flaw in it. I'd also like to see if it's possible to achieve the same outcome without relying on there being a reasonably small capacity to fill.)

No, a device can't "prove the identity of its own code" assuming no hardware modification, if we want this secure and achieved automatically from arbitrary software image made available in machine form representing what's supposed to be the executable code, at least when said image is in part adversarially built (and arguably neither if it is built per common practice).

Whatever remotely gives demonstration of what code is running must be inherently trusted; it can not attest of its own integrity, as thought in the question.

The question's "As an example.." method has a weakness: some of the data hashed can be selectively rebuilt during the hash, rather than really present. The code for the modified hashing part would hash content of actual memory for the bulk of the software image, but synthesized data in the two zones (A) where itself is and (B) where some of the genuine hashing code was supposed to be (actually modified, e.g. by at least a JMP to modified hashing code in A). At runtime, A and B are never actually hashed/checked. A contains the modified hash code and data necessary to reconstruct what's synthesized when apparently hashing A or B; that data includes a copy of the original B, and a compressed form of what A contains in the arbitrary software image made available in machine form (it is impossible to automatically detect that it is not actually functional code/data).

The above argument assumes that the arbitrary software image made available in machine form was prepared specially to make the insertion of the modified hash code easy, using zone A of software that has no real functional value and instead is a placeholder for something adversarially prepared. However, the attack might often be possible assuming only that the software image contains a zone of sufficiently compressible data or code. I'm willing to accept that the attack could not be carried if the entire software image was initially crafted by a non-attacker taking care to code densely; but that goes against modern software construction practice.

The OP is explicitly targeting integrity of the software of voting machines. An example is this one, which (with different software) is still used in France in several cities (Le Havre, Brest..). The entire software is in a socketted EPROM. The integrity of the software is "demonstrated" by the software computing and displaying a CRC of itself on the display. That's of course a complete joke against an adversarial attack (and using a hash would not help much, for the code displaying the hash can be replaced by code displaying the appropriate constant).

The method proposed by the question (where the value displayed depends on a manual entry) would seem, on the face of it, to mitigate the attack where a modified software displays the hard-coded CRC or hash of the software it mimics. However, for the reasons I explain, that's not cryptographically strong against a skilled adversary. And worse, the challenges fed for remote attestation could be used as a side channel to control the rigging of the votes.

That interesting "yes" answer achieves its goal by adding a Trusted Platform Module (a secure CPU with a private key capable of signing, a certificate, and trusted code), and most importantly assuming integrity of trusted boot code of the main CPU, the CRTM. My reasoning above assumed non-integrity of all software, only integrity of hardware.

Integrity of trusted boot code makes a qualitative difference. That boot code can verify the integrity of the rest of the code by verifying a digital signature, with the public key (or the root of a chain of certificates) in the trusted boot code. That's in wide use (e.g. in Point of Sales terminals since the 1990s) and is a reasonably effective measure against unauthorized code modification. This alone is however not achieving what the question asks: that method can't remotely attest that any software is running; it only insures that  only authorized software could run. And it remains quite vulnerable to modification/tampering, by debug mechanism allowing code injection (JTAG port, extra memory dynamically brought into the addressable space by a paging mechanism), and exploitation of software vulnerability bringing hostile code e.g. by buffer overflow (mitigation to the later are possible with Harvard architecture separating code and data, security rings, virtual machines, code proofs..).

To add attestation, the standard and working method is adding a capability to sign with a private key. A simple conceptual model is that the trusted boot code includes a Virtual Machine (e.g. JavaCard), verifies (by checking code signature as above) what code can run in that VM, and remotely attests of what it launched there together with a challenge to prevent replay (preferably by cryptographically signing or MACing, which requires a secret somewhere); it may even dynamically peek at what's in the VM and attest about it. Interpretation in a VM is not essential; principles for hardware equivalents running at native speed  are known since 1960's mainframes. The TPM-locked PC can be viewed as a refinement of that, allowing remote attestation of what is running, under hypothesis reasonable on a consumer PC, including that some code responsible of the attestation is not altered.


What encryption mode should I use to protect a packet but the integrity of the entire packet, including its header, is protected? What encryption mode should I use to protect a packet, such that the payload of the packet is encrypted, but the integrity of the entire packet, including its header, is protected?

What encryption mode should I use to protect a packet, such that the payload of the packet is encrypted, but the integrity of the entire packet, including its header, is protected?

If the context is to be ignored, this functionality is usually called Authenticated Encryption with Associated Data (AEAD) in cryptography. It has usually four inputs (and is deterministic in those):

A key - which must be uniformly random and unknown to any adversary
A nonce - which must be unique for a given key, you don't need to keep this secret
A plaintext message - which will be encrypted and integrity protected
Some associated data - which will only be integrity protected

Upon decryption, the key, the nonce, the ciphertext, and the associated data is given and is guaranteed that decryption only succeeds (yielding the plaintext) - assuming the adversary doesn't know the key - if this nonce and associated data have been used to produce this ciphertext.
Good schemes that satisfy this notion include AES-GCM, AES-EAX, and ChaCha-Poly1305.
However, there's a good chance that you actually want a higher-level primitive: A Secure Channel. Which given a key gives you a randomized / stateful / nonce-based encryption algorithm and a stateful decryption algorithm. These guarantee you that not only have no new messages been added without the knowledge of the key, they also guarantee you to detect whenever messages have been re-ordered or dropped.
Standard constructions for this include (pre-shared key) TLS and an appropriate selection from the Noise Framework.


What is the chance of a collision when using SHA-3? I currently am writing a web app and am using two random hashes that are before and after the string and are both 50 char long (alphabet, numbers, and special chars).

strlen($hash1) = 50;
strlen($hash2) = 50;
$sha3pw = sha3($hash1+$password+$hash2);

What are the chances that someone will be able to find a collision from only the hashes? Is there any chance or is it a theoretical chance?

Generally, SHA-3 is build to offer $2^{n/2}$ collision resistance (and $2^n$ preimage resistance).

You haven’t specified which SHA-3 you are talking about (SHA3-224/256/384/512), but even when looking at the smallest of them (SHA3-224) and assuming correct implementation, the chance of a collision is more of a theoretical nature.

Talking about implementation: what I don’t really grasp is why you would inject a 50-byte hash before, and another 50-byte hash after the password. Those might just be two individual hashes of some web app related information you’re pulling together there… but in case that’s an attempt to add some kind of security, I would like to advise you to look at HMAC-SHA3 constructions. Yet, even better would be to use solutions that were specifically designed for this kind of task, like bcrypt, scrypt or pbkdf-2.

For further reading:

The new SHA-3 secure hash algorithm has been published in FIPS 202 (PDF).
The HMAC algorithm is described in RFC 2104 (TXT).

It may be helpful to know that the block lengths $B$ to be used in the HMAC algorithm (meaning: the byte-length of the digest input block) is given in Table 3 of FIPS 202… that’s 144 bytes for SHA3-224, 136 bytes for SHA3-256, 104 bytes for SHA3-384, and 72 bytes for SHA3-512.


What does AES round reduce in attacks mean? I am reading about some cryptanalysis attacks on AES. Most of the attacks reduces AES to 4. 5 or 6 rounds. What does that mean?

The proper statement is usually something like "we demonstrate an attack on 6 rounds of AES of such and such complexity".

Standard 128 bit key length AES is an iteration of 10 rounds, each round uses a round key derived from the randomly chosen AES key and is made up of AddRoundKey, SubBytes, ShiftRows, MixColumns operations.

If AES is run for less than 10, say 6 rounds, it is obviously weaker. So this means the demonstrated attack would fail (typically would require more computational effort than a brute force search for the key) if more rounds were added, and thus the given attack can't break the full cipher.

Such reduced round attacks are still of interest on strong ciphers like the AES since they tell us that some partial cryptanalytic progress has been made.

Edit: There is an attack on the full 10 round 128 bit key length AES with complexity $2^{126.1}$ by Bogdanov et al, where the authors state "In contrast to most shortcut attacks on AES variants, we do not need to assume any related-keys. Most of our attacks only need a very small part of the codebook and have small memory requirements, and are practically verified to a large extent. As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way."


Is the "New Hope" Lattice Key Exchange vulnerable to a lattice analog of the Bernstein BADA55 Attack? In the paper, "Post Quantum Key Exhange - A New Hope," the authors present a lattice-based key exchange based on the work of Chris Peikert.  In this "New Hope" key exchange the authors try to gain security by having the basepoint for the key exchange (a polynomial with coefficients in a finite field) randomly generated by the key exchange initiator for every key exchange.

My question is whether this basepoint generation scheme is vulnerable to a lattice analog of Bernstein's attack on the NIST elliptic curves in his paper, "How to Manipulate Standards:  A White Paper for a Black Hat."  In that paper a single party is allowed to randomly generate a sensitive cryptographic parameter that was to be used by others.

Yes the Bernstein attack is applicable but the impact of the attack is reduced because the party generating the parameter is also going to be a legitimate participant of the key exchange.

Here is why the attack does indeed apply.  Consider a case where Bob and Alice wish to conduct a key exchange using the New Hope Lattice-Based Key Exchange.  Bob will be the key exchange initiator and Alice will be the key exchange responder.  Bob wants to help the internet surveillance authorities run by Bernstein's "heroic" eavesdropper "Eve."  However, Bob does not want to be seen cooperating with Eve by turning over the key for the key exchange or the plaintext information to Eve.  Bob asks Eve for a more subtle way to help her "heroic" cause.

In Bernstein's "White Paper for a Black Hat" he and his co-authors assume that Eve knows a class of weak elliptic curves unknown to the rest of the world.  Eve knows that one would randomly select one of these weak elliptic curves with probability p. To carry this attack over to the New Hope Lattice domain we must assume that Eve knows a class of weak New Hope basepoints that are unknown to the rest of the world.  Let us assume that Eve knows of such a class of weak basepoints and that these weak basepoints occur with probability p.

The New Hope basepoint generation scheme would have Bob generate a random seed and use the SHAKE-128 algorithm and some other processing to produce a random basepoint (polynomial) for the key exchange.  Bob is supposed to do this only once.  Hence the probability that Bob randomly hits a weak basepoint is p.  However, Eve tells Bob not to generate just one basepoint but gives Bob a long list of seeds that will generate weak basepoints.  Instead of generating RANDOM seeds Bob uses a seed from the list that Eve gave him.

Bob and Alice complete the New Hope key exchange as described by its authors.  Eve collects the key exchange and uses her knowledge of the weakness in the basepoints to break the key exchange and recover the traffic.  While it is true that Bob could have compromised the key exchange to Eve in many other ways.  The method pointed to in your question is a protocol weakness that could be corrected.

Fortunately, there is a very easy fix to the New Hope protocol that eliminates this attack.  If the initiator and the responder both generate random seeds, exchange them and a concatenation of these seeds is used in the generation of a random basepoint then the attack only works if BOTH Bob and Alice are colluding with Eve.  The right thing to do in New Hope is to have both initiator and responder contribute to the basepoint generation process.  In protocols like TLS that already have exchanges of random information (the "Hello" messages) this protocol change seems entirely fitting.

Ironically Bernstein has been questioning the underlying security of the cryptography on which the New Hope scheme is based and has referenced a number of large classes of lattice parameter sets that are weak


What is the maximum number of messages that can be encrypted using the same key for CTR mode? In the counter mode of encryption, the nonce cannot be used again unless a new block cipher key is chosen. What is the maximum number of messages that can be encrypted using the same key?

The maximum length of messages that can be encrypted using the same key under the counter mode is $2^{39} - 256$ bits.
I want to make sure am I correct?

You should generally keep the total volume of data encrypted well below $2^{64}$ blocks per key with AES-CTR (or any use of AES)—for example, a petabyte ($2^{50}$) per key is a reasonable limit.  This is because AES is slightly defective as a pseudorandom function, which is what ‘CTR mode’ is designed for—it is really a pseudorandom permutation masquerading as a pseudorandom function, with a corresponding minor loss in security proportional to $q^2\!/2^{128}$ after $q$ messages.

AES-CTR specifically entails using $\operatorname{AES}_k(n \mathbin\| c)$ as a block of a one-time pad, where $n$ is a per-message nonce and $c$ is a block counter within the message, so that the concatenation $n \mathbin\| c$ is 128 bits long.  Just like the security of a one-time pad goes up in smoke if it's a two-time pad, the security of AES-CTR goes up in smoke if you repeat $n \mathbin\| c$.  The size of the nonce $n$ determines a hard limit on the number of messages, and the size of the counter $c$ determines a hard limit on the length of any individual messages.

Different systems use different sizes for $n$ and $c$, but a common reasonable choice, as used in, e.g., AES-GCM, is 96-bit $n$ and 32-bit $c$, which limits messages to $2^{32} - 2$ blocks, or $2^{36} - 32$ bytes, or $2^{39} - 256$ bits.  (The extra two blocks are used inside AES-GCM to choose the GHASH key for authentication.)  It is generally a bad idea to use very large messages anyway—the largest message size you accept is the largest amount of memory an adversary can waste in a denial of service attack before you can reject a forgery.

(There are also CTR variants that involve the sum $n + c$, where $n$ is chosen pseudorandomly rather than sequentially, instead of the concatenation $n \mathbin\| c$; for example, AES-GCM-SIV does this.  But the security story for that is a little more complicated and getting a bit afield from the question.)


Is AES still secure considering all this NSA/Snowden scandal? Im trying to understand if nowadays using AES is secure or not, after reading some arguments on Schneier’s blog (to be more exact, a comment to “The NSA Is Breaking Most Encryption on the Internet”) it seems like it is not secure:

Now as the NSA GCHQ et al know very well the more efficient you make the implementation of crypto code the more side channels it has unless extreme caution is observed. One thing we do know is that optimized for speed and minimized number of gates is an almost certain guarantee of side channels no matter how clever you are. Also the NSA knew that developers would not write their own code they would simply download and use the competition candidate code.
As was pointed out and demonstration code exploited implementations of AES were subject to timing attacks that could fully leak the key across a network connection due to "cache hits" on the Intel x86 platform from base level pentiums upwards within weeks of the winning candidate being announced. Even today there are very side channel suseptable AES implementations in use in fact the majority of those implementations on the likes of routers and switches are timing channel cursed as are most application level software implementations that are more than a year or so old...

…at least not if the computer used is connected to external network.
Is this true or just based on assumptions?

Let's clear some bullshit first:

  Now as the NSA GCHQ et al know very well the more efficient you make the implementaiton of crypto code the more side channels it has unless extream caution is observed. One thing we do know is that optomised for speed and minimized number of gates is an almost certain guarentee of side channels no matter how clever you are.

The horrendous spelling issues aside, this is absolute bullshit. On almost any CPU there are only three things in symmetric crypto that introduce side-channels:

Branches dependent on secret data.
Table lookups with an index dependent on secret data.
CPU instructions that take non-constant time/power.

AES suffers from potential side-channel attacks because the obvious implementation of the S-box violates #2, and the obvious implementation of polynomial multiplication violates #1. Both issues can be avoided using trickery, though.

But in general you can optimize all you want as long as you don't branch on secret data, don't do table lookups with secret data and make sure that the CPU instructions you use always take the same amount of power and time (notable violaters of this are multiplication instructions in many lesser-known CPUs).

As to the question in the title, AFAIK Snowden has not published any documents that show cryptanalysis against AES, so AES is still as secure as before. I do not know whether Snowden published documents of the NSA abusing side-channels, however I wouldn't be surprised (or worried) at all if he did. Side-channels were long overlooked and many old implementations suffer from them. Modern day implementations are much more aware and as such don't suffer from them.


Why is the BSI not using powers of two? In their Technical Guideline TR-02102-2 Cryptographic Mechanisms: Recommendations and Key Lengths the BSI is giving minimal key lengths for - e.g. the TLS handshake protocol. All of these are not integers that are a power of two. I always thought, that it was the norm to give key lengths as powers of two. Is it not?

My guess is that it is stated a round decimal number (e.g. 2000) of bits in order not to disqualify solutions using keys that can be up to the next round binary number (e.g. 2048) of bits, but are occasionally slightly less.

In particular, in RSA, when we make the product of two 1024-bit primes, the result is 2047 or 2048-bit. This scenario happens with some versions of PGP/GPG, and some SSH software. Contrast with FIPS 186-4, which wants 2048-bit moduli to be exactly 2048-bit, and towards that goal generates 1024-bit primes at least $2^{1023.5}$. TR-02102-2 is slightly more lenient, in a way that does not practically compromise security.


Cryptographically secure hash function vulnerable to length extension attacks both to front and to back? Is there any hash function where both $\text{hash}(m\|k)$ and $\text{hash}(k\|m)$ are vulnerable to length extension, but $\text{hash}(m)$ is itself secure?

I think here it helps to examine the nature of length extension attacks, which have to do with the fact that practical hash functions are iterative.  They break up their input into a sequence of fixed-size blocks, and process each block successively, using the state produced by processing the previous block as an input into the processing of its successor.

Length extensions weaknesses exist because some hash functions are (mis?)designed so that their output reveals their state after processing the final block, and that allows the attacker to shortcut the computation of the hash result for messages whose block sequence extends that of the original.

One straightforward observation is that there while the most practical way to build such a hash function would be to process blocks in the same order they occur in the input message, there is no theoretical requirement to do so.  You could write a hash function that works exactly like SHA-256 but processes messages in reverse order.  It would be impractical because you would need to buffer whole messages in memory or in disk before you can hash them.

The fact that hash functions are vulnerable to length extensions at the end of a message but not at the beginning is just an artifact of that practical decision to process messages from start to end.


Private RSA key for HMAC key I am creating software tokens for future request authentication, and I want to use an HMAC for the token to make them tamper-resistant. To ensure I can check the HMAC later I need a secret, persistent key. Is there a security concern in using a private RSA key as the HMAC key? If not, what would the best values be from the key? This link says:

  The security of RSA derives from the fact that, given the public key { e, n }, it is computationally infeasible to calculate d, either directly or by factoring n into p and q. Therefore, any part of the key related to d, p, or q must be kept secret.

I would expect it to be the private exponent (D) then, but I am not sure if some other combination of values would offer strong security (like P,Q, and D concatenated).

Edit: clarification

The reason I am asking about the RSA private key is the HMAC key needs to be stored so that the HMAC can be validated by the server on future requests. An RSA private key is an easy to manage, persistent value. I am not using the public key, or performing any aspect of public key crypto. I need a way to securely manage the HMAC key, and I am wondering if there are any good reasons not to use an RSA Private Key for this purpose.

The reason I am asking about the RSA private key is the HMAC key needs to be stored so that the HMAC can be validated by the server on future requests. An RSA private key is an easy to manage, persistent value.

You seem to be under the misguided and mistaken belief that an RSA key is somehow easier to manage and persist than a symmetric key.

  I am wondering if there are any good reasons not to use an RSA Private Key for this purpose.

RSA private keys were not designed or intended for this purpose, and there seems to be no legitimate reason why you would actually want to do it. Use primitives for the purposes they were designed. Don't try to be clever. And don't invent your own crypto.


Is SHA-256 bijective on a certain domain? Following the discussion on bijectivity and given that function inverse is studied on domain/codomain, I would like to ask whether we can find subsets where this function can be bijective.
Let's say the subset of all alphanumeric strings of exactly 5 characters. The cardinal of this subset should be Arangements of 62 characters in a line of 5 characters = 62! / 57! ~ 776 mln . This is definetely lower than 2^256 . Is this enough to say the function is injective on this domain or do I need to calculate every single value to make this conclusion? What happens to surjectivity in this case?
OBS: I might make confusion with continuous functions so do let me know if I have mistaken something.

Of course it is. If you tightly restrict the input domain, then the problem is simple. The function is deterministic, so just inject clusters of random bits within the input domain of interest (domain $A$).  You then select unique hashes (co-domain $O$) and discard the colliding input/output pairs to create input sub-domain $B \in A$. You will have nullified collisions and will have a bijection as $B \to O$.
Note: We haven't seen collisions on SHA-256 output domains yet, but the above theory holds. And using this brute force approach, the co-domains become more biased towards a bijection as the input domain deceases in cardinality, as $p(\text{bijection}) \propto \frac{1}{|A|}$ through simple computability.
But I'm having a hard time understanding a cryptographic use for such strange domains. I'm unconvinced that sha256inv would actually exist at all as restricting inputs is kinda cheating. And they still only analytically compute one way as $\text{sha256}:B \to O$ which is due to fundamental pre-image resistance. $\text{sha256inv}: O \to B$ remains elusive. And general $\text{sha256inv}: O \to A$ must remain impossible as you've deliberately eliminated collisions which we know mathematically exist.

P.S. $|A|= 916 \times 10^6$, if you consider 5 no. 62 alphanumeric values chosen by total randomness. That's easily computable on an enthusiast's machine.
P.P.S. My last para refers to your comments.


Can I simulate iterated AES-ECB with other block cipher modes? I am trying to write some code using the Web Crypto API (http://www.w3.org/TR/WebCryptoAPI/#algorithm-overview) which provides only some of the block cipher modes for AES, intentionally excluding AES-ECB (presumably because it is not normally a good choice for anything).

My need is to use AES-ECB-nopadding as part of a key strengthening step, i.e. iterate 6000+ times to introduce some constant extra time into the decryption, resulting in a strengthened key that I can use to decrypt the rest of the data.  My code is providing compatibility with an existing password system that does this (Keepass) so I don't have any choice as to what steps or algorithms to use.

Given lack of native support, can I simulate this with one of the other block ciphers, or will I have to load a third party library that includes the ECB block cipher?

I tried so far using CTR with a zero counter and never incrementing the counter.  This failed due to some technical limitations (it did not support those parameters).

I think it may work to use CBC with a zero IV and just doing a single block at a time.  Will that work (theoretically)?

First lets acknowledge this is a horrible hack - you really should find a way to do what you want more directly or risk code maintenance issues and likely bugs in the future.

Second, while the question isn't about your key strengthening step it seems like you should ask about the security.  There are lots of good key derivation methods out there and I don't consider iterating encryption to be a good one.

One Block CBC

Lets look at the algebraic structure of CBC on one block:

$
    \text{cbc}(v, p) = E(v \oplus p)
$

Thus if $v = 0$ $\text{cbc}(0,p) = E(0 \oplus p) = E(p)$ which is the same as ECB.

CTR

The CTR idea fail because plaintext is never part of the block encrypted by the cipher:

$
    \text{ctr}(v, p) = E(v) \oplus p
$

$
    \text{let } v = 0
$

$
    \text{ctr}(0,p) = E(0) \oplus p
$


Can I use Shamir's secret sharing scheme for multiplicative homomorphism for secure multiparty computation? I would like to perform a dot product operation among $m$ parties using Shamir's $(m,m)$ secret sharing that is used for Secure Multiparty Computation.

I am aware that Shamir's $(m,m)$ scheme is additively homomorphic, but can someone please provide an example of how I can use it for multiplicative homomorphism for SMC?

As far as I know, you can not do multiplication with (m,m) shamir secret sharing. The typical method to do multiplication on shamir secret shares increases the degree of the sharing polynomial, which is why the parties run an additional protocol to reduce the degree. That is why the degree of the sharing polynomial must be less than $m/2$ if there are $m$ parties.

If you indeed need (m,m) (or $m$ out of $m$ parties must be present to do reconstruction and multiplication), and the only operation you need to compute is multiplication (which I'm not sure about since your comments state you want to do multiplication, but your question mentions dot product), then I'd suggest using multiplicative secret sharing.

If instead you need $m$ out of $m$ computation/reconstruction, but need to do both addition and multiplication operations, you'll have to go with some of the newer MPC constructions which achieve full-threshold security (SPDZ and some of it's references or subsequent works which cite it).


Byte location of plaintext vs ciphertext when using a block cipher or stream cipher I know that when you use a stream cipher you are just XOR'ing the plain text with the PRNG stream,  such that you know if a specific byte is in position 3 of the plain text it will still be in position 3 of the cipher text.  I know that this is not true for block ciphers in ECB/CBC/other modes except OFB.   But why?  What is happening behind the scenes?

But why?

It is because the cipher is designed with the avalanche effect property. Namely, changing a single bit in the plaintext (or key) should result in a significant change in the ciphertext. So really, it happens because ciphers are designed with that property.

  What is happening behind the scenes?

Really it is the entire cipher. If you look at a cipher generically as substitutions and permutations, it is the substitutions which really cause the effect, but even then, the permutations contribute to it when multiple rounds are used.


The weak link is the password? Consider a secure modern block cipher like AES/Serpent/Twofish.

I hear everyone say that the complexity is $2^{128}$ for a 128 block cipher. But isn't the weak link the actual hashed and salted password? Any brute force should be targeted at it?

By my rough calculations $2^{128}$ = $84^{20}$, so any proper password composed of all available keyboard characters shorter in length than 20 is a weakness?

The problem seems to only grow with 256 ciphers: $2^{256}$ = $84^{40}$.

So does this mean there is no point using AES256 if you don't plan to have a password 40 characters long or use keyfiles? Could someone please clarify?

Most protocols use a randomly generated key (TLS, for example) that spans the full keyspace of the cipher, so 128-bits in the case of AES-128.

For other uses where the cipher key is directly obtained from a plaintext password a propper key derivation procedure should be used. One standard for this is PKBDF2 which, in simple terms, computes the cipher key by repeated application (tens or hundreds of thousands of iterations) of a hash function to slow down the calculation in order to make brute force attacks impractical.

Imagine a key derivation function that consisted of just two applications of a hash function and compare this to deriving a key from a single hash function application. In this case it is twice as computationaly expensive to mount a bruteforce attack on the password, and this corresponds to an extra bit of the password key. In this way it is possible to "trade" time for key bits.


Can I build a secure tweakable block cipher from a normal one by adding key and tweak? Let (E,D) be a secure block cipher.

Consider the following tweakable block cipher:

E'(k,t,x) = E( (k+t) mod |K|, x)
D'(k,t,c) = D( (k+t) mod |K|, c)

Is (E',D') secure?

Well, whether it is a secure tweakable block cipher depends on how resistant (E,D) are to related key attacks; that's not a standard assumption for block ciphers.

For example, this would not be a secure tweakable block cipher with 3DES; because every 8th bit is ignored, the attacker can effectively test the value of the 7 adjacent bits (except for the 7 MSBits) by a choosen tweak attack.  For example, if he can find a value t with (for an arbitrary block x):

E'(k,t,x) = E'(k,t+256,x)
E'(k,t+2,x) != E'(k,t+258,x)

then he can deduce that the addition of k and t+258 was just enough to propagate a carry past bit 8 (which doesn't affect the operation of 3DES) into bit 9 (which does).  This allows him to immediate deduce the lowest 7 used bits of the key.

Repeating this observation for the rest of the key bits allows us to recover all but 7 bits of the key with about 400 adaptively chosen tweaks; the last 7 is easy to brute force.


Are Fujisaki commitments binding if the factorization of the group is known? If I understand correctly, a Fujisaki commitment is as follows:  $g^m \cdot h^r $ mod $n$, where $m$ is a message, $r$ is a random number, there exists $a$ such that $h^a = g$, and $n$ is an RSA modulus.

Usually, when I read discussions about this scheme, the holder of the commitment does not know the prime factorization of $n$.

Is it a requirement that the order of the group be unknown to the creator of the commitment?  (Note added assumption below.)

EDIT:  Note that the message can be replaced with $m+k\cdot \lambda(n)$, where $\lambda(n)$ is the order of $n$. Though this is a threat to the commitment, I am more concerned with commitments of small values ($m << \lambda(n)$), so opening the commitment like this would be rejected.  So I will rephrase:

Assuming $m << \lambda(n)$, is a Fujisaki Commitment binding if the prime factorization of $n$ is known?

Yes! Note that in the original scheme there are two secrets the committer does not know:

The factorization of the modulus: $N=pq$
The value $a$ such that $h^a=g$.

Therefore, the commitment scheme is still binding, even if the factorization is known. Let's assume committer wants to open the commitment $c=g^m h^r \mod N$ to a different $(m^{*},r^{*})$. It means that she needs to find values $(m^{*},r^{*})$ such that:

$$g^m h^r=g^{m^{*}}h^{r^{*}} \mod N $$

$$\iff g^{m-m^{*}}h^{r-r^{*}}=(h^a)^{m-m^{*}}h^{r-r^{*}}=1 \mod N $$
Which equivalently gives the following equality in the exponents:
$$\iff a(m-m^{*})+(r-r^{*})=0 \mod \phi(N) $$

Even if committer knows $\phi(N)$, she does not know $a$, therefore she cannot break the binding property, unless she additionally breaks the Discrete-Log in $\mathbb{Z}^{*}_p$ or $\mathbb{Z}^{*}_q$.

In most definitions of the Fujisaki commitment scheme, $N$ is chosen to be a product of safe primes, so commiter cannot even use Pohlig–Hellman algorithm efficiently, to calculate discrete logs modulo primes.

Trivially, if also $a$ is known to committer, then she can decommit to any $m^{*}$ by choosing an appropriate $r^{*}$ through solving the last equation in the exponents.


Basic question on hash-based signature scheme If a hash-based signature schemes such as W-OTS is used, do we still need public key based certificates to prove ownership of a public key? I understand that hash-based signatures are one of the candidates for post-quantum signatures. However, if quantum vulnerable schemes such as RSA is used for certificates, it makes such system still vulnerable to quantum computing.

However, if quantum vulnerable schemes such as RSA is used for certificates, it makes such system still vulnerable to quantum computing.

Well, yes, if one used conventional crypto in your certificates, things would be vulnerable.  You'd need to use a certificate that used postquantum signatures.

BTW: generating a certificate for a one-time signature public key, such as W-OTS, would appear to be somewhat pointless, as you'd need to request a new certificate everytime you used your private key.  What you'd want to do (assuming tracking state is not an issue) is to use a scheme that can sign multiple messages, such as XMSS or LMS.


MySQL/MariaDB AES_ENCRYPT() - ECB mode, IV, Padding Oracle Attack Question Multipart question all related to AES encryption with MariaDB.  Strangely enough, it looks like even today MariaDB only has AES with ECB mode.  MySQL allows CBC and more I believe.  Anyway I'm stuck with MariaDB and luckily in this situation, the highest level of security is only a nicety and not a requirement.  I'm asking more for academic reasons.

My usage requirements: Store encrypted data in mariadb in an environment I consider to be secure in the first place (no unauthorized user could ever even see the encrypted data).  Be able to decrypt directly through a query (for sql ORDER BY and search operations).  I've create my own SQL function as a wrapper around AES_ENCRYPT() so I can add whatever additional encrypt/decrypt logic I need.  The most likely scenario is someone remotely gains access to the database, so they can see the encrypted data and function used to encrypt/decrypt.

ECB mode - I understand why this isn't considered secure.  So does salting the passphrase (16 random Bytes) adequately fix the ECB issue for my situation, since in theory the same input and passphrase should never create the same output?
Is salting a passphrase randomly have the same security benefit as an unsalted password and an IV assuming the salt and IV have the same amount of entropy?  I realize ECB doesn't use IVs, I'm just asking in general.
Padding Oracles - For both ECB and CBC (when mariadb implements it).  This is the one I least understand.  So assuming someone has stolen the database contents, how likely is it that the hacker could create their own padding oracle for an sql database?  Seems like they should be able to.
Supposing a hacker could create a padding oracle for a stolen sql database, they should be able to crack the encryption fairly easily.  Can anything be done to mitigate this?  For example, could the padding be added to the beginning of the message?  From what I gather, the hack works by testing decryption on blocks in reverse order.  So maybe if the padding wasn't at the end of the message, they would have to fully decrypt the message to check the padding at the beginning.

No
No
If the attacker doesn't steal the key, they can't create their own padding oracle.
As long as the key is not stolen, no mitigation is required.

Your threat model for "someone [having] stolen the database contents" seems very weak: if you make a query containing the decryption key, the key bytes themselves will likely persist in memory long after the query has been executed. See this recent paper for a discussion of realistic threat models for database compromise. (Full disclosure: I am a co-author of the paper.)


Where can I find a description of the SHA-0 hash algorithm? Where can I find the description and or pseudocode for the SHA-0 hash algorithm? I am looking for something on these lines: HMAC RIPEMD.

I have been implementing a few of those (HMAC, HOTP, TOTP and MD4, MD5, RIPEMD-128,160)

The reference on SHA(-0) is FIPS 180 (archived scan) of 1993 May 11. The standard itself is referenced on the NIST website, but that links to another scan lacking page 1 and the one before, thus foreword, abstract, explanation... There's also this text draft of 1992 January 22 (also here with less indication on origin).

The Proposal for Change of that into SHA-1 was published on 1994 July 11 and is online at the Federal Register with partially garbled text, including for the security-critical change:

  In Section 7 of [1] (page 9), the line which reads
      (b) For t=16 to 79 let Wt = Wt-3 XOR Wt-8 XOR Wt-14 XOR Wt-16.
  is to be replaced by
      (b) For t=16 to 79 let Wt = S1(Wt-3 XOR Wt-8 XOR Wt-14 XOR Wt-16).
  where S1 is a left circular shift by one bit as defined in Section
  3 of [1] (page 6), namely S1(X) = (X << 1) v (X >> 31).

Note: What's kept of the original PfC has messed-up sub/superscripts (a modern web artifact), and misses the closing parenthesis on the modified expression for Wt (possibly an omission in the original).
This is was a technical change in the design, critical for improved security, rather than a correction of a typographical error as could be understood by casual reading of the PfC. This change was introduced without rationale, and initially without ensuing changes in the test vectors. It is thus reasonable to suspect that it was intentionally sneaked quietly, with knowledge that the original was not as secure as intended against educated collision attacks.

The revised document is FIPS 180-1 of 1995 April 17, referenced on the NIST website (with a link to an external scan of the actual document).

Changing source code for SHA-1 into one for SHA(-0) is easy: just remove the one-bit rotations of a 32-bit word of the 512-bit message block. For example, in the reference implementation of RFC 6234, change

W[t] = SHA1_ROTL(1, W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]);

to

W[t] =          (   W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]);


Why isn't ElGamal a symmetric-key scheme? I was asked about this question by a friend.
He considers that Alice and Bob share a secret key s=g^(xy).
So why isn't it considered a symmentric-key scheme?
According to Wikipedia:

  Symmetric-key algorithms[1] are algorithms for cryptography that use the same cryptographic keys for both encryption of plaintext and decryption of ciphertext. The keys may be identical or there may be a simple transformation to go between the two keys.

I observe that the shared s is quite easy to compute by Alice and Bob.

I know there's misunderstanding, but I can't convince myself now.

g^x is the public key of Alice and x her private key, while g^y is the public key of Bob and y his private key.

s=g^(xy) is the shared secret between Alice and bob, that can only be computed by them.

Thus, ElGamal is an asymmetric algorithm computing a shared secret that can be used as a symmetric key.


How to handle a lost key in Diffie-Hellman Key Exchange I implemented the Diffie-Hellman Key Exchange algorithm but, I was wondering how to handle if one of the parties lost his key.

Let's take a chat app as an example, Bob and Alice they used to have a shared key, but sadly Alice changed his device, and what if Bob sent a message to her encrypted with the shared key while she was offline. How can this be handled?

Not Sure about this solution:
Can I once Alice logs in with the new mobile device it requests from her room users to re-authenticate? and how about that message that Bob sent pre-re-authentication?

Thanks in advance. :)

EDIT ONE

As @kelalaka said, I can send an excuse to bob by re-auth and resending the message from his device.

You have to send the previously generated key securely and this is complicated and needs an additional protocol that you may not want.

Otherwise, the key-exchange algorithm is randomized, and re-run will not produce the same key. Better is send a key-lost event, re-execute Diffie-Hellman and re-send the message.


How to find the base point given public and private key and EC parameters except the base point I'm working on the curve secp256k1 and I've private key $k$ and public key $P = [k]G$. I look for solutions to the following problems;

What is the inverse of a scalar $k$ in ECC?

If I'm only missing $G$ but know all parameters of the curve can I find $G$ from $k$ and $P$?

Most standardized curves has a base point $G$ of prime order $q$ so computing the inverse of $k$ (the private key) modulo $q$ can be easily done as
$$
k_{\text{inv}} = k^{p-2} \bmod q,
$$
thanks to Fermat's Little Theorem since
$$
k_{\text{inv}}\times k \equiv k^{p-1} \equiv 1 \pmod{q}
$$
In the case the order is a composite integer $n$, then Euclid Extended algorithm is a good way to find it.
In your problem you have a public point $P_{\text{pub}}$ such that
$$
P_{\text{pub}} = [k]G,
$$
and you only know $k$ and $P_{\text{pub}}$. To find $G$, use of the above algorithm (if the order of $G$ is known) to find $k_{\text{inv}}$ and we have
$$
G = [k_{\text{inv}}] P_{\text{pub}}.
$$


What is the advantage of an attacker over breaking a 4 digits PIN? When a hardware system is protected by a 4 digits password, what is the advantage of the attacker into breaking that system?

Isn't it $10*10*10*10=10^{4}$? If $\frac{1}{10^{4}}$ is the cost of such an attack then is this reasonable computation for the attacker? In my eyes this seems like a simple brute force attack for 4 numbers. I mean is super easy. Isn't it?

Something went wrong with you calculations there :) A single digit has $10$ possible values, not $2^{10}$. What you were probably trying to calculate was $\frac{1}{10^4}=\frac{1}{10000}$.

It is a bit unclear what you mean by advantage. In cryptography, the advantage $\mathsf{Adv}_\mathcal{A}$ of an adversary $\mathcal{A}$ is the probability that $\mathcal{A}$ is successful ($\mathsf{Succ}_\mathcal{A}$) in attacking something minus the success probability for some trivial attack that cannot be prevented.

For example, for a decision problem, such as CPA security, the advantage is $\mathsf{Adv}_\mathcal{A}=\mathsf{Succ}_\mathcal{A}-\frac{1}{2}$. This is because you acannot prevent $\mathcal{A}$ from guessing the bit.

The advantage of guessing a four digit PIN with one random guess is $1/10^4$.
For at most $t$ random (but distinct) guesses, we get $\frac{t}{10^4}$.
The advantage for an adversary attacking some authentication service using four digit PINs would therefore usually be $\mathsf{Adv}_\mathcal{A}=\mathsf{Succ}_\mathcal{A}-\frac{t}{10^4}$.

EDIT: In the first version of this answer I assumed that PINs would be chosen uniformly for each try. Of course that's not true. They would indeed be chosen to be distinct from each other. (This makes the probabilities quite a bit easier.)


Provable data possession (PDP) VS Merkle tree In the paper Provable Data Possession at Untrusted Stores, there is a mechanism that allows a client to efficiently check if the server still has the client's data. They define two constraints for their system: server-side data access and communication complexity.

Also, they state that a scheme based on just Merkle tree cannot be secure (so they don't talk about the complexity here). They have cited a paper but cannot find any explanation for that.

Question: Why cannot we design a PDP using just a Merkle tree?

I'd say that like with the naive variant of simply asking for the hash of the data, the server can just throw away the data and store the hashes and still answer queries. It is important for such schemes that a query requires the server to use sufficient randomness together with the data in the computation of the answers. Then precomputing the potential answers will require too much storage and it is then actually less costly to keep the data itself.


scrypt and bcrypt for benefits of both? I've been reading about bcrypt and scrypt, and it seems that the general consensus is that bcrypt is more "tried and true", but scrypt is better in theory.

Couldn't you just hash something with bcrypt, then with scrypt? If it has a layer of scrypt to use resources, and a layer of bcrypt, shouldn't that give you the benefits of both with the drawbacks of neither?

I would advise against this.  When implementing slow-hashing (such as bcrypt or scrypt), it's usually recommended to select as high a work-factor as is tolerable (in relation to how much time the user is willing to wait, and/or how much strain you're willing to put on your server).  Assuming you're working within this constraint, using two distinct slow hashes would force you to halve the work-factor of each, potentially making one or both more susceptible to attack.

Of course, depending on the context, if time and resources are not limited, then your proposal is at best a buffer to dampen paranoia, but honestly I think scrypt is mature enough to be used exclusively.


BGN encryption scheme with unbounded message space In Evaluating 2-DNF Formulas on Ciphertexts stated that

  decryption in this system takes polynomial time in the size of the message space T. Therefore, the system as described above can only be used to encrypt short messages

Is there any other extension with the same properties of (any number of addition and one multiplication operation on the ciphertext) but also allows bigger message space?

In my search, I encounter only in Converting Pairing-Based Cryptosystems from
Composite-Order Groups to Prime-Order Groups, but it does not solve that limitation.

There is a scheme whose purpose is exactly that, the LWE-based BGN-like encryption scheme. In general, we do not know how to achieve large message space for homomorphic encryption using discrete-log-style crypto; all known current solutions require lattice-based cryptography.

EDIT: reading the comments on your question, it seems you want to leak only whether the output is zero or not, by masking with a large random $r$ multiplicatively. But the standard BGN cryptosystem already allows that: the parties can always decrypt $g_t^{\mathsf{DFN(x)}}$ with BGN ($g_t$ is a generator of the target group), only the discrete logarithm at the end requires the message space to be small. However, seeing $g_t^{r\cdot\mathsf{DFN(x)}}$ for a large random $r$ already allows to see efficiently whether $\mathsf{DFN(x)} = 0$ or not: if it is equal to zero, then $g_t^{r\cdot\mathsf{DFN(x)}} = 1$; otherwise, $g_t^{r\cdot\mathsf{DFN(x)}}$ is just a random group element since $r$ is random.


Is pairing based cryptography ready for productive use? I'm currently testing one among those many interesting cryptographic protocols based on bilinear maps.
It's quite hard to understand the underlying fundamentals, especially since there are several types of pairing and different underlying algorithms like Weil, Tate and Ate (again with subtypes?). Although I understand the properties

So I started with Ben Lynn's "On The Implementation of pairing based cryptosystems", which is relatively old. There he distinguishes between Type A-G curves and notes that Type3 curves are "susceptible to certain discrete log attacks". On the other hand, Steven Galbraith talks about "the death of Type 1 pairings" in his quite new blog entry and states that "Type 3 pairings are usally the most efficient" and Type 4 is rarly used. (Ben Lynn however seemed to have a little preference for the Type 4 pairing)  Are those the same pairings as mentioned by Ben Lynn?

Can some of them been seen als secure enough for productive use? Are some of them seen to be more secure than others? What about the Ate-pairing which seems to be surprisingly fast?

Type-1 (symmetric pairings) are dead for curves over fields of small characteristic. Over prime fields of large prime characteristic they are not really dead, but as they only offer small embedding degrees ($k=2$), they are not really attractive from a performance point of view. You have to choose very large curves (which makes the curve arithmetic slow) such that you have a reasonable security in the multiplicative target group.

Type-3 pairings are most attractive (from the perspective of a performance and security tradeoff) as when they are used with Barreto-Naehrig (BN) curves, they have nice embedding degree of 12 (meaning that for 256 bit curve $G_1$ will give you 3072 bit in $G_T$ and this choice is ideal at the 128bit security level w.r.t. the comparable strengths proposed by NIST at the moment). Furthermore, most Type-2 protocols can be ported to the Type-3 setting by non-crucial modifications.

Type-4 are rarely used as they only are required if one requires secure hashing (in the sense that one does not know the discrete logarithm of the result to some fixed point) to $G_2$ (and that is only required rarely by protocols). As it turned out, they are also quite dangerous to use.

The different types of pairing functions $e$ (ate, optimal-ate, etc.) are basically all instantiations of the miller algorithm (aka miller loop) with different optimizations (use of distortion maps, use of Forbenius, etc. in the algorithm) and are typically restricted by the type of paring you are using.

Benn Lynn actually provides Type-3 pairings (dn - MNT curves, f - BN curves) and I have no idea why it seems that he has a preference towards Type-4 (maybe because he required them in his proposed protocols?).

I think whether they are ready for productive use is opinion-based, but AFAIK Voltage sells pairing-based crypto for years, and there are also draft standards for IEEE P1363 and I guess they will propose the use of BN curves. Also there is a draft RFC on the Optimal Ate pairing over BN curves.

Udate:
Since there has been a recent progress in the discrete logarithm problem in extensions of fields of large prime characteristic (see here for a nice overview), it is not really clear at the moment how exactly this would influence BN curve choices to adjust the BN curve parameters for a given security parameter. It is thus possible that for instance KSS curves (with an embedding degree of $k=18$) get more attractive than BN curvres. So this will not really push standardization at the moment till this is clear.


How is a digital certificate generated? I understand that the role of a Certificate Authority is to SIGN (not encrypt) a certificate. The signed certificate will theoretically contain:

Plain text of data, including the server's public key
Signature of hashed version of plain text of data in (1) so that a user can verify (using CA public key) that the certificate has not been tampered with.

Knowing these two key points, I tried to play around with an example cert

-----BEGIN CERTIFICATE-----
MIIF7zCCBNegAwIBAgIRANdVj9r18RBbshMoK3B3KaMwDQYJKoZIhvcNAQEFBQAw
gZcxCzAJBgNVBAYTAlVTMQswCQYDVQQIEwJVVDEXMBUGA1UEBxMOU2FsdCBMYWtl
IENpdHkxHjAcBgNVBAoTFVRoZSBVU0VSVFJVU1QgTmV0d29yazEhMB8GA1UECxMY
aHR0cDovL3d3dy51c2VydHJ1c3QuY29tMR8wHQYDVQQDExZVVE4tVVNFUkZpcnN0
LUhhcmR3YXJlMB4XDTExMDMxNTAwMDAwMFoXDTE0MDMxNDIzNTk1OVowgd8xCzAJ
BgNVBAYTAlVTMQ4wDAYDVQQREwUzODQ3NzEQMA4GA1UECBMHRmxvcmlkYTEQMA4G
A1UEBxMHRW5nbGlzaDEXMBUGA1UECRMOU2VhIFZpbGxhZ2UgMTAxFDASBgNVBAoT
C0dvb2dsZSBMdGQuMRMwEQYDVQQLEwpUZWNoIERlcHQuMSgwJgYDVQQLEx9Ib3N0
...
-----END CERTIFICATE-----

I tried decoding using Base64 decoder, and the result is gibberish. I tried googling for answers but I'm not getting anywhere.

What encoding scheme is this and does this offer extra layer of security?
Shouldn't the main ideas (point 1 and 2) be secure enough?
Is there a way I can break this blob down to visually show that data part and the signature part?

Plain text of data, including server's public key

Yes, and many other public information, including something identifying the holder of the public key (perhaps in the Common Name field).

  Signature of hashed version of plain text

Yes, except that the correct semantic is: Signature of the plain text. Building and verifying the signature includes hashing plain text.

  What encoding scheme is this?

See RFC 7468 section 5 and what it references, including RFC 1421 section 4.3.2.4 for the translation of binary to text (which in a nutshell is per Base64).

  Does this offer extra layer of security?

From a cryptographic standpoint, no. That's merely a binary-to-text encoding, see this for rationale.

  Shouldn't the main ideas (point 1 and 2) be secure enough?

Yes, they are.

  Is there a way I can break this blob down to visually show that data part and the signature part?

When there's any non-confidential piece of standard text-encoded stuff to decode, it can be thrown at the marvelous https://lapo.it/asn1js/ (with or without the delimiters) and the results are usually pretty good. When in doubt about the confidentiality, use a local copy in an isolated VM.


Constructing scheme for indistinguishability test with variable length messages Say $\Pi=[Gen,Enc,Dec]$ private key encryption scheme, such that for $k \in \text{{0,1}}^n$, $Enc_k$ is only defined for message of length at most $p(n)$. (for some polynomial)
I need to construct a scheme for eavesdrop indistinguishability test where the eavesdrop isn't restricted to output equal-length message.
I saw a paper (last question) where given plaintext $m$ of length at most $p(n)$, they first padded $m$ from the left side with $0^{p(n)-|m|-1}1$ to get a message of length $p(n)$, and then applied $Enc_k(.)$ on the result. For decryption, they first used $Dec_k(.)$ on the ciphertext, and then parsed $0^t1$ to leave only $m$.
But what if for example, I want to encrypt the messages $0^t10^{p(n)-t-1}$ and $0^{p(n)-t-1}$ for some $1 \leq t \lt p(n)-1$, won't they be encrypted to the same cipher text?

That homework assignment is not entirely precise: If you allow $|m| = p(n)$, the padding doesn't make sense: $0^{-1}1$. Therefore, you would have to limit $|m| \leq p(n)-1$ to avoid that case.

For your example and question: You're right, if you consider that a prefix $0^{-1}1$ actually is the empty string (no padding). Then your strings are equal. However, that case is actually undefined and should be fixed with reducing the message length by $1$.

From an information theoretic point of view:
There are $2^{n}$ messages of length (exactly) $n$. And there are $\sum_{k=0}^{n}2^k = 2^{n+1} - 1$ messages of length $n$ or less. So if you consider the set of all messages of length $n$ or less, and consider those shorter messages as different messages, then you actually have $n+1$ bits of entropy (rounded to the next integer) and need at least a message of $n+1$ bits length to encode that information.


Can I use the secret part of a asymmetric encryption keypair as a symmetric encryption key? Background

I'm working on a framework for crypto-based authentication and authorization that is largely inspired by the way Keybase's Teams product works.

Keybase uses the same process to generate per-user keys and per-team keys. Quoting their docs:

  A user generates a 32-byte random seed s.
  She computes e = HMAC(s, "Keybase-Derived-Team-NaCl-EdDSA-1") and uses this value as the secret key for an EdDSA signing key. She then computes the public half, yielding keypair (E, e).
  She computes d = HMAC(s, "Keybase-Derived-Team-NaCl-DH-1") and uses this value as a secret key for a Curve25519 DH encryption key. She then computes the public half, yielding keypair (D,d).
  Computes c = HMAC-SHA256(s, "Derived-User-NaCl-SecretBox-1") and uses this value as a symmetric secret key.

In brief:

Make a random seed, and use it to generate
A signature keypair
An asymmetric encryption keypair
A symmetric key

Question

I was thinking that to simplify things, I could skip step 4 and reuse the asymmetric encryption secret key d as the symmetric key, instead of deriving an additional key c. In practice, if you know one, you'll know the other. All else being equal, I'd prefer to have fewer moving parts.

Is there a reason not to do this?

(To be clear, my system doesn't need to interoperate with Keybase - I'm just
using their process as a model.)

The HMAC calculation is used as a KDF here. So 3 keys are derived.

Let's start with the statement "In practice, if you know one, you'll know the other.". This is incorrect. The KDF construction uses a one way function so that you cannot get to the input keying material (or seed) s. This means that if an adversary gets hold of the symmetric key c that you cannot calculate either s and therefore e or d.

There is another more theoretical problem in the sense that using d both for HMAC as for "symmetric secret key" then you're using the same value for multiple algorithms, breaking their security claim. It might be that there is some mathematical algorithm that makes the value of s vulnerable. From a practical perspective that's highly unlikely as a HMAC with a known string will not be a structure that can be abused for this kind of attack - but I think it is worth mentioning anyway. For instance, an auditor may ask nasty questions about it.

From a more practical point there may be an issue when it comes to side channel attacks. If these can be combined then there may be a practical issue when the keys are not separated (this is of course a blatant copy of the comment by fgrieu below).

And that's about it; the reason to separate the keys is key separation itself. If you want to break that rule then that's your decision, but it is certainly not considered good cryptographic practice. I'd only do such tricks if there is no other way.


Can cryptography help create tamper proof voting systems? After hearing about what happened with the election in Kenya and the related discussion about a “tamper proof voting system”, I was wondering how the use of cryptography could be used to make a tamper proof voting system?

I have had a basic look at zero knowledge proofs, but I do not know how these and other protocols could be used to achieve a tamper proof voting system – hence the question.

Cryptography allows voters to verify that their ballots are cast as intended, recorded as cast and counted as recorded. This is done via a combination of primitives with the most important ones being zero knowledge proofs. Moreover cryptography allows for voter anonymity by using primitives such as mixnets, blind signatures combined with homomorphic cryptosystems for vote secrecy.

The field of cryptographically verifiable elections has been researched for almost 35 years and the literature is huge. Many systems have been proposed with an emphasis on integrity achieved through end-to-end (E2E) verifiability. The theory is sound, but I guess implementation and security concerns among others do not allow for wide scale adoption.

I recommend this talk by Ben Adida to get you started.


Ephemeral key is held constant in ElGamal Is there a known algorithm to recover the sender's messages in ElGamal $\mathbb{F}_p^*$ if the ephemeral key is held constant in two or more transmissions, assuming the messages are always distinct?

Say Alice picks a prime $p$ between $2^{1000}$ and $2^{1001}$ and chooses a $g \in \mathbb{F}_p^*$ with large prime order. $L$ is her public key. Doug the doofus sends Alice two or more transmissions $(c_1, c_i), c_1 = g^k (mod\,p), c_i = m_{i}L^k (mod\,p) i = 1,2,...,n$ with $k$ held constant. Can Eve the eavesdropper recover Doug's messages?

IOW, why does the ephemeral key need to be ephemeral?

One thing Eve can do is compute the modular division of any two messages.

That is, she is given both $c_2 = mL^k$ and $c'_2 = m'L^k$; she can then compute the value $c_2\cdot c'^{-1}_2 = m\cdot m'^{-1}$.

Whether this, in itself, is sufficient to recover the messages depends rather on the distribution of Doug's messages.  However, what this means (independent of the distribution) is that if Eve has a guess for the plaintext for any of the messages, she can immediately deduce the plaintext for all the other messages.

Note that this similar system IES doesn't share this problem; if Doug repeats all the parameters, well, it will leak if he resends identical plaintexts; however it will still be secure otherwise.


Why exactly is a root hash used in relation to hash lists? Wikipedia has an rticle about hash lists, although I find it technically not very detailed. For example: We could solve same problem by sending (authenticated) hash of each data block, together with each data block.

So, why the need for a root hash? Is it because this way you could send single authenticated root hash, and no need to authenticate each hash for each data block?

Yes, the transfer of just the root hash can be a good reason for using a hash list. Then you can still hash the leaf hashes in a parallel fashion.

However, generally the root hash is simply needed so that the hashes aren't reordered / removed. Of course this won't protect against deliberate attack; you would have to use the root hash in a signature scheme for that.

Sending hashes together with data blocks only makes sense if you expect accidental damage. In that case you might want to use a non-secure hash or another error detecting / correcting code (such as PAR2). In general the transfer of hash lists or trees takes part separately.

In the end, a hash list is a very generic concept. How it is used depends a lot on the protocol and/or use case. Possibly that's why you don't find that much practical information on it.

Note that the Wikipedia page correctly specifies that often a root hash is used. What is probably more common is that the hashes are aggregated in a separate data structure, and that that particular data structure is signed. This data structure can include additional (meta-) information in the signature.

You can see this in e.g. XML digital signatures, the cryptographic message syntax (PKCS#7 or CMS) but also ePassports where the separate data groups containing the personal info / fingerprints are hashed separately and the result is put in a structure and signed. This way you can verify components separately, while using only a single signature.


All the affine points on the curve I have calculated the affine points on the curve $x^2 + y^2 = 1 − 3x^2y^2$
over the field ${\mathbb{Z}}_{11}.$

Using $y^2 = \frac{1-x^2}{1+3x^2}$ I got the following points:

$(0,1),(0,10),(1,0),(2,2),(2,9),(9,2),(9,9),(10,0)$

Total comes to be 8 points. But what I know is that total points should come 11-1 = 10.

So I am not getting other 2 points.

Well, this curve has 8 affine points and I would like to share the way to find them all.
First of all, we make a square table till 10 as we have  field ${\mathbb{Z}}_{11}.$  (so 11-1=10)
Below is the table(also calculate its mod 11 values) :
  ┌───────┬─────┬────┬────┬────┬────┬────┬────┬────┬─────┬─────┬────┬
  │   #   │  0  │  1 │  2 │  3 │ 4  │ 5  │ 6  │  7 │  8  │  9  │ 10 │
  └───────┴─────┴────┴────┴────┴────┴────┴────┴────┴─────┴─────┴────┴
  │Square │  0  │  1 │  4 │  9 │ 16 │ 25 │ 36 │ 49 │  64 │  81 │ 100│
  └───────┴─────┴────┴────┴────┴────┴────┴────┴────┴─────┴─────┴────┴
  │Mod 11 │  0  │  1 │  4 │  9 │ 5  │ 3  │ 3  │  5 │  9  │  4  │  1 │
  └───────┴─────┴────┴────┴────┴────┴────┴────┴────┴─────┴─────┴────┴

Re-arranging the equation so that we have $y$ on the left-hand side
$y^2 = \frac{1-x^2}{1+3x^2}$
Now we start putting form $x = 0$  until $x = 10$  in the above equation and get the value of $y$ each time. If the value of $y$ is one of the complete squares mod 11 i.e row 3rd of the table then the corresponding value in row 1 is the $y$-coordinate.
$y$ is calculated as mod 11. Even if the value of $y$ is in fractions.
For $x=0$ we get $y^=1$ which exists in row 3rd i.e it is a complete square. Now value 1 in 3rd row corresponds to value $1$ and $10$ in row 1. So we get 2 points here i.e. $(0,1)$ and $(0,10)$
For $x=1$ we get $y^2=0$  this also exists in 3rd row. So corresponding values in 1st row are 0. So here we have only 1 point $(1,0)$
For $x=2$ we get $y^2=4$ this also exists in the 3rd row. So corresponding values in 1st row are 2 and 9. So here we have 2 points i.e. $(2,2)$ and $(2,9)$
For $x=3$ we get $y^2=6$  which does not exist in the 3rd row of the table. So no corresponding value of $y$ will be there, hence no point will exist at $x=3$
For $x=4$ we get $y^2=8$   Not in the table (not a complete square) hence no points here.
For $x=5$ we get $y^2=2$   Not in the table (not a complete square) hence no points here.
For $x=6$ we get $y^2=2$   Not in the table (not a complete square) hence no points here.
For $x=7$ we get $y^2=8$   Not in the table (not a complete square) hence no points here.
For $x=8$ we get $y^2=6$   Not in the table (not a complete square) hence no points here.
For $x=9$ we get $y^2=4$   Exists in table (hence it is a complete square) So corresponding points are: $(9,2)$ and $(9,9)$
For $x=10$ we get $y^2=0$   Exists in table (hence it is a complete square) So corresponding point is: $(10,0)$
So all the affine points are
$(0,1)$ $(0,10)$
$(1,0)$
$(2,2)$$(2,9)$
$(9,2)$ $(9,9)$
$(10,0)$
Note that we can calculate solutions for $x = 0, 1, ... , \frac{11-1}{2}$ and use symmetry in $x$ in $\mod 11$ ($10 \equiv -1 \mod 11$, $9 \equiv -2 \mod 11$, etc.) as well to obtain all points, namely $(x,y) => (x, -y) \wedge (-x, y) \wedge (-x, -y)$.
In the example above you get all points calculating all solutions until $x=5$. The solution for $x=9 \equiv -2 \mod 11$ is obtained using symmetry for $x=2$ ($(2,2) => (2, -2) = (2, 9) \wedge (-2, 2) = (9, 2) \wedge (-2, -2) = (9, 9)$) and the solution for $x = 10 \equiv -1 \mod 11$ is obtained using symmetry for $x=1$.


Diffie Helman obtaining $g^y \bmod p$ from $g^{xy} \bmod p$ and $g^x \bmod p$ This may seem like a strange question. Lets say I have $g^x \bmod p$ and $g^{xy} \bmod p$. How can I efficiently obtain $g^y \bmod p$? I assume I must use modular inverse but I don't know where.

Lets say I have $g^x \bmod p$ and $g^{xy} \bmod p$. How can I efficiently obtain $g^y \bmod p$?

We hope that there is no efficient method (without using knowledge of $x$ or $y$)
Here's why: if you can solve that problem, you can solve the (computational) Diffie-Hellman problem; here's how:

Suppose that you did have an Oracle that, given $g, g^x, g^{xy}$, returned $g^y$

Then, you can use that to create an Oracle that, given $h, h^x$, returned $h^{x^{-1}}$
Here's how, you'd call your Oracle with $g=h, g^x=h^x$ and $g^{xy} = h$.  These conditions hold only if $x^{-1} = y$, and so when your Oracle returns $g^y$, that's also $h^{x^{-1}}$

With that Oracle, you can generate a squaring Oracle (given $h, h^x$, return $h^{x^2}$, and with that, computing DH is straight-forward.


SHA256 hash malleability Can an SHA-256 plaintext be malleable? For example:

Given $y = hash(x)$ , can an attacker find $z$ so that $z = hash(f(x))$. Here $f()$ might be the addition of a suffix to the message, an XOR operation, or any other mathematical transformation.

I know there is one known malleability weakness shared in Merkle-Damgard constructions:

Given $hash(x)=y$, it is trivial to find $hash(x\mathbin\| s)=y'$ in which $\mathbin\|$ denotes concatenation. The attacker does not need to know what $x$ is. This is also known as a length extension attack.

Are there any other known examples of SHA256 hash malleability aside from the length extension attack? For instance, given $hash(x)=y$, can I find the output of hash($x \oplus s$) without knowing what $x$ is?

EDIT:
A fellow contributor provided me with this link: What type of hash functions provides non-malleability of hash digests?
But I don't think this answers my question in detail......

I believe that, if you make a plausible-sounding assumption on the SHA256 hash compression operation, you can show that the only malleability SHA256 has are length extension attacks.

This plausible assumption is that, for a fixed input state, then the mapping between message block and output state acts like a random oracle [1]

With this assumption, suppose we a message $M_0$ which, after SHA-256 padding, is the sequence $N_0$, and a message $M_1 = f(M_0)$, which, after SHA-256 padding, is the sequence $N_1$, and we assume that $M_1$ does not have $M_0$ as a prefix (if it is, then this is a length extension attack).

If $M_0$ does not have $M_1$ as a prefix, then we can show that, after some integral number of SHA-256 blocks, $N_0$ and $N_1$ differ; at this point, the SHA-256 hash compression operation will map their states to random values, and after that point, the latter SHA-256 hash compression operations will continue to map the states to random values, and so the outputs will be effectively random (and hence you cannot compute one from the other).

And, if $M_0$ does have $M_1$ as a prefix (the attempted attack is a "length shortening attack"), then $N_0$ may have $N_1$ as a prefix; if it does, then the intermediate state of $M_0$ processing cannot be determined by the final $M_0$ output value (as it is effectively random), and $N_0$ doesn't have $N_1$ as a prefix, then the previous reasoning applies.

This argument is a bit hand-wavy; I believe that it's essence is valid.

[1]: Note that we cannot make the assumption that the entire hash compression operation acts as a random oracle, because we know how, given a message block $M$ and a delta $\delta$, we can find input and output states $S_0$ and $S_1$ with $S_1 = \text{Compress}( S_0, M )$ and $S_1 = S_0 + \delta$; this shows that the hash compression operation itself is distinguishable from a random oracle.


Is using slow password hashing on the client side easier attackable than on the server side? As we know, one should use a slow password hashing algorithm instead of a fast one for storing passwords, to hinder brute force attacks when the database is compromised. The problem with this is that for every login we also need to run this slow password hashing algorithm, which for remote logins could be a considerate CPU load on the login server if many people try this at the same time.

This night, I had an idea on how to solve this (in a new protocol for password authentication):

The user types in his username
The client sends the username to the server.
The server sends a salt (and maybe other parameters) to the client
The user types in its password
The client calculates a slow hash (bcrypt-like) from this password, using the salt (and maybe the security parameter, e.g. iteration count) provided by the server
The client sends this hash value to the server
The server calculates another cheap salted hash (SHA-2-like) of the sent hash value, and compares it with the value stored in the database.
(Optional, to avoid remote brute-forcing and DOS: wait a small time before sending back the answer, and limit the number of parallel connections for each user/IP.)

The communication should be encrypted, of course (as the sent hash value is the effective password).

(Add the obvious way of generating and storing the passwords.)

I'm assuming this:

The output of the first hash is not really recognizable as such, e.g. there is
no cheap way to iterate only the possible outputs of the first hash instead of
all strings of this size. If I understand right, bcrypt has this property (if
we only look on the actual ctext part of the output, having length of 192 bits).

(A comment from ZoFreX seems to indicate that this is not the case.
Any details on this?)
The second hash is preimage-resistant, e.g. there is no significantly better
way of finding a preimage fitting to a given hash than brute-forcing the input space.

Then we have:

The first (slow) hash avoids (or rather slows down) brute-force/dictionary
attacks over the password space. (It is salted to avoid rainbow tables.)
The second (fast) hash avoids that an attacker which gets somehow read access to the
database can immediately use the data to login into the system: The attacker will
need to brute-force the (in the bcrypt example 192 bit large) output space of the
first hash to find a preimage (which then would be usable as a password).

If we think it is needed to slow this down even more, we could use a second (low-factor)
bcrypt here instead of a really fast hash.
Since the slow hash is done on the client-side, the server load is not as high
as for server-side slow hashing. (I'm assuming a quite high work factor for bcrypt.)

Here are my questions:

Is there already a protocol which works similar to this? (From the comments, this seems off-topic here. Feel free to mention it anyway if you happen to know one, but concentrate on the next question.)
Are there any weaknesses of this protocol idea compared to a usual server-side slow password hashing?

There exists something which is one step further than your idea. Look up SRP: this is a Password-Authenticated Key Exchange protocol; the two parties (client and server) who run the protocol end up with a newly generated shared key (which can be used to derive encryption and integrity-check keys), with mutual authentication with regards to a shared statically known secret which can be of relatively low entropy (say, a password).

In your system, this would mean that the password is first derived into the shared secret with something slow (bcrypt), and then use the result as the "password" in SRP. SRP has been designed so that the server stores only what amounts to a hash of the "password", not the password itself, so obtaining a copy of the server database does not allow an attacker to log in; it only makes him able to run an offline dictionary attack on the password, at which point the initial bcrypt hits him hard.

The beauty of PAKE protocols is that they are inherently immune to offline dictionary attacks from eavesdroppers: the protocol can be run "in the clear" and this still does not give a passive or even active attacker any way to learn enough to "try" passwords at his leisure. Only an attacker who hacks into the server may get such data, and even then he does not have the password (the password-derived-value-through-bcrypt, in the setup we envision here), just a hash thereof. So there is no need to establish a SSL/TLS tunnel beforehand. Even better, it is possible to use SRP as the initial handshake for a SSL/TLS tunnel; this is standard, and GnuTLS is an opensource implementation of that. A particular appeal of TLS-with-SRP is that client-server authentication is then mutual with regards to the password, which implies that there is no certificate whatsoever.

A possibly troublesome issue is that the number of iterations in bcrypt must be set so that it is slow (for the attacker) but still tolerable (on whatever machine bcrypt is to be executed). If you want bcrypt to run on the client, and also accommodate a variety of clients, some of which being possibly quite anemic (e.g. a 3 years old netbook, like mine: old mono-core Atom clocked at 800 MHz; also think about smartphones), then you have to tune the bcrypt iteration count accordingly. The patience of the average user being, let's say, somewhat limited, this prevents you from setting a bcrypt iteration count as high as you would like. On the other hand, you can muster 100% of the client CPU resources for that (client might be multitasking, but the user is unitask), which probably compensates much of that effect.

Summary: use bcrypt on the client, then use the result as "password" in TLS-with-SRP.


Computational indistinguishability and example of non polynomial algorithm The wikipedia page on computational indistinguishability says that two ensembles are not distinguishable if "any non-uniform probabilistic polynomial time algorithm A" cannot tell them apart. To help me better understand the definition, I searched for an example of an algorithm that did not fit the above restriction---in particular a non polynomial time algorithm---that could differentiate between two computational indistinguishable ensembles. Rather to my surprise, I found none, so I ask, could anyone provide me with an example of one?

I am not a complexity theorist, but I believe this fits the requirements.

The best known algorithms for factoring are superpolynomial time algorithm so they are not polynomial time. An example of something th superpolynomial time algorithm could distinguish are outputs from the Blum-Blum-Shub PRNG.


Do hash collisions persist if a file is modified? Suppose I use a relatively insecure hash algorithm to digitally sign a contract. Suppose also that creating a fraudulent contract with the same hash, a collision, is practical. As I understand, in order to take advantage of a hash collision, the black hat is required to introduce some contrived information into the data first to counter the hash affects of their anticipated alterations.

For example, the original contract and hash are:

I will pay you $1.00 -> 12345

and a fraudulent colliding contract:

I will pay you $1,000,000.00 (contrived info) -> 12345

Can I protect myself by including some of my own text before signing?

For example:

I will pay you $1.00 have a nice day -> 67890

Can the attacker simply add the same text to their contrived file and get the same new hash?

I will pay you $1,000,000.00 (contrived info) have a nice day -> 67890

or will the additional text alter the hash such that the files no longer collide?

I will pay you $1,000,000.00 (contrived info) have a nice day -> 37294

I.e. Will my added information counteract the contrived information of the attacker?

In reality, as with SHA1 or MD5 where a practical method for finding collisions has been found, using this algorithm is faster than more secure ones. Could it make sense to use a very fast insecure algorithm coupled with both parties, a third party, or a random automated system, adding some novel, benign information prior to the hash? Does this add sufficient complexity?

I.e. In the case of SHA1 and git, could an attacker add some obscure contrived information in advance (that gets committed and signed or whatever) and then introduce the malicious code later when the timing was right? Or would subsequent commits thwart this plan? I.e. Are code repos with lots of contributors and commits coming from all over somewhat more secure than repos with little change?

TL;DR: when using SHA-1 or similarly weak hash, include unpredictable data at the beginning of the message.

Simplifying, there are three kinds of attacks to fear on practical (iterated) hashes that result in a collision, that is where the attacker ends with two different messages (of the same length) having the same hash. From easiest to hardest:

Collision attacks: the attacker can choose per operational constraints one meaningful prefix and one meaningful suffix. Messages are of the form
I will pay you $1,000,000.00 (Qn47y2NXu49ssmexutgno5!QsmtxG) have a nice day
I will pay you $1,000,000.00 (eCW3Y!=jLJK;q&vM+;gdPZma7JAP4) have a nice day
An example of such attack against SHA-1 is shattered.
Chosen-prefixes¹ collision attacks: the attacker can choose per operational constraints two meaningful prefixes (of equal length) and one meaningful suffix. Messages are of the form
I will pay you $1.00 (G&RyUbpwgnn6dYbkLLnkx2WqMu5RVZ!QsmxyG) have a nice day
I will pay you $1,000,000.00 (KE2nFdwUizu;uo!BKgSB$c&ULEQ!R) have a nice day
An example of such attack against SHA-1 is this recent paper.
Second-preimage attacks. The attacker can choose per operational constraints one of the two messages in full, the prefix of the other message, and have the two messages share a suffix. Messages are of the form
I will pay you $1.00 on presentation of this signed message, have a nice day
I will pay you $1,000,000.00 (48CMWaAb5gt9RopNsgw!W2&o9x54e) have a nice day
There is no example of such attack against SHA-1, nor even against MD5.

Note: the arbitrary portion typically has a minimum length of a few blocks (32 or 64 bytes for common hashes).

Note: depending on how the messages are interpreted, collision attacks (1) can still result in two messages  with appearance entirely under the adversary's control. In particular, it may be possible to have a prefix that selects between two arbitrarily different appearances both encoded in the suffix, with the one displayed according to one bit in the arbitrary portion. The prefix of the shattered attack was chosen to allows that for PDF documents. This trick can be played with images, executable code..

Attacks 1 and 2 can be useful to an adversary only when sh/e can chose part of the signed message, e.g. for messages like
I will pay you $1.00 per invoice PkictdyAxvaokEeTtEkVYEG24UYtK4GLiTqCWHtw, have a nice day

  Can I protect myself by including some of my own text before signing?

Yes, but not quite per the method illustrated in the question. You can protect against collision attacks and chosen-prefixes collision attacks (1 and 2) by including some unpredictable data at the beginning (in the first block) of the signed message. E.g.
My Ref BzCP3dFT. I will pay you $1.00 per invoice PkictdyAxvaokEeTtEkVYEG24UYtK4GLiTqCWHtw

This technique is used by savvy certification authorities when generating digital certificates with unpredictable Certificate Serial Number. This guards against chosen-prefixes collision attacks where the prefixes include a predictable CSN and two different domain names (one the attacker's target and the other under control of the attacker), and some of the arbitrary data belongs to public keys.

  Can the attacker simply add the same text to their contrived file and get the same new hash?

Yes, the attacker can easily add or alter a suffix of two colliding messages. That's why the unpredictable data must be at start.

  Will my added information counteract the contrived information of the attacker?

Only if the addition is early enough in the message (e.g. first block), and if the adversary can not perform attack 3 (second-preimage). Critically, the unpredictable data must be at the start of the hashed message. It is pointless to add unpredictable data in the appearance of a PDF document or other structured message.

  Could an attacker add some obscure contrived information in advance (that gets committed and signed or whatever) and then introduce the malicious code later when the timing was right?

Yes, but only if the attacker (able to perform attack 1 or 2) can predict what's before the portion s/he has under control. This is avoidable when preparing a zip file, then hashed (and e.g. signed or referenced by hash): the zip creation process can add a random header, making attacks 1 and 2 infeasible. This is not avoidable when an adversary can post a whole file and the integrity of that file is insured per the hash of that file (attack 1 is enough for many file formats including most executables).

¹ Often written just chosen-prefix (collision).


Generate 2 independent keys from a master key The scenario is like this: I need 2 keys for different purposes (encryption + encryption, encryption + mac, or whatever). Because it is not good practice to reuse the same key, I'd like the 2 keys to be independent. But remembering 2 different keys are cumbersome (don't question this please), so I think there should be some way to generate these keys from one common master key.

The closest crypto tool for this job I can find is a KDF. However, the KDF usually takes as an additional input: the salt. Should I randomly generate and remember a salt, or simply use a hash function such as SHA512 and divide its output into 2 keys?

I think in this scenario, there's no need to worry about the possible recovery of the master key from the derived keys, because the derived keys are no less important than the master key. The compromise of the derived keys is just as bad as that of the master key. The importance is instead focused on the independence between the 2 derived keys, since at least there are some encryption and mac schemes such that, when used together, would become totally broken if keys are not independent.

The purpose of the salt is to limit the cost that an adversary can share between multiple targets.  The salt need not be random.  It need only be unique per user.

If two users share a salt (possibly an empty salt), then the work to find at least one of their keys can be shared with Oechslin's rainbow tables on a parallel machine so that the expected cost to find at least one of their keys in a batch multi-target attack is about half the expected cost of a single-target attack, and the expected time to find at least one of their keys is at most one eighth the expected time of a single-target attack.

In general, if there are $n$ possible keys, and $t$ targets, and you parallelize the computation about $p \geq t^2$, then the expected cost to find at least one is $n/t$ and the expected time to find the first one is $n/pt$, at most about $n/t^3$.

If you use 256-bit keys, then the number of users necessary to make this significant is impossibly high, so you can safely use an empty salt in that case.  The salt is important only for ≤128-bit keys.  (This is why AES-128 should already be considered to have a <128-bit security level, and why you should use AES-256 anyway.)

If you have a notion of a user id unique to a key, you could just concatenate it with the name of your application as the salt, with no need for storage.  If you don't have a notion of a unique user id, using a random salt reduces the probability that the adversary can share work between two attack targets.  The longer the salt, the lower the probability of a collision enabling the adversary can share work.  Use a 256-bit salt, and there will never be a collision unless your implementation is broken.
A secondary purpose of a KDF is to map a high-entropy but possibly nonuniform secret into a uniform secret.  If your master key came from a Diffie–Hellman key agreement and is the bit string encoding of some unique representative of a residue class modulo a large safe prime, or is the byte string encoding of a point on an elliptic curve, then the master key is not uniformly distributed among bit strings, but does have high entropy.  A KDF smooths out the distribution on bit strings so it is effectively uniform.
The purpose of a password hash (scrypt, argon2, etc.) is to use all your available resources to drive up the cost of a single evaluation of the hash, which a brute force attack must do repeatedly.  Willing to spend 1sec on hashing?  Force the adversary to compute two million (say) HMAC-SHA256 computations instead of one for each guess.  Willing to spend 1 GB RAM on hashing?  Force the adversary to commit the area of 1 GB RAM in each parallel hashing circuit—which otherwise could have been dedicated to many more parallel hashing circuits if it were not memory-hard, like PBKDF2—or spend double the time hashing if they can only fit 512 MB RAM, etc.  If you can't raise the number of possibilities for the secret, e.g. if your secret was chosen by a human, you can at least raise the cost of testing each possibility in a brute force attack.

These considerations apply independently:

Have a human-chosen password?  Probably has ≪128 bits entropy.  Use a password hash like argon2id with a salt to (a) drive up the cost of each guess, (b) map a nonuniform bit string into a uniform bit string, and (b) prevent the adversary from sharing work between multiple targets.  Make sure if the user ever changes the password, the salt changes too, so if it's deterministically chosen, it can't just be an application name and user id—it must also include, say, a revision number.
Have a machine-generated memorable diceware password chosen from ${\sim}2^{128}$ possibilities?  Use a KDF like HKDF with a salt to (a) turn a nonuniform bit string of 128 bits entropy into a uniform bit string, and (b) prevent the adversary from sharing work between multiple targets.  Using a password hash to drive up the cost of each guess doesn't hurt if this is only ever used in an interactive application, but it's not necessary.
Have a shared secret encoding of an $x$ coordinate on Curve25519 from an X25519 key agreement, so that $x^3 + 486662 x^2 + x$ is a quadratic residue modulo $2^{255} - 19$?  Use a KDF like HKDF to turn it into a uniform random bit string.  Salting doesn't hurt in this case, but it's not necessary.