Are there any secure commutative ciphers? This answer lists two commutative cipher algorithms - Pohlig-Hellman and SRA. However, they don't appear to be too secure.

My question is, here there any commutative ciphers out there that are secure enough for sensitive data encryption / decryption (money is involved) and at the same time not burdening enough on the computer to be run in real time on less powerful devices (say, a smartphone)?

For a set of $B$ elements (e.g. $B = 2^n$ for all the "blocks of $n$ bits"), there are $B!$ possible permutations. An ideal block cipher is such that an instance with an unknown key is indistinguishable from a permutation chosen at random, uniformly, in these $B!$ permutations.

Since permutations don't commute in general, a "perfect" commutative block cipher must work over a subset of these $B!$ permutations, where all elements of the subset actually commute with each other, and this makes a commutative block cipher highly distinguishable from a randomly chosen permutation. Namely, suppose that there is a black box which implements either the block cipher $E_K$ (for some unknown key $K$), or a randomly chosen permutation. The attacker can submit plaintexts to encrypt (that's a chosen-plaintext attack scenario), and observe the result; his goal is to determine whether the box really implements $E_K$ for some $K$, or not. He then does the following:

He selects a key $K'$ randomly, as well as a plaintext block $x$.
He sends $x$ and $y = E_{K'}(x)$ as plaintexts to encrypt with the box.
The box returns, respectively, $u$ and $v$.
The attacker checks whether $E_{K'}(u) = v$. That equation will hold with probability $1$ if the box implements $E_K$, but only $1/B$ (i.e. almost zero) if the box implements a randomly chosen permutation.

In that sense, a commutative block cipher cannot be secure "as a block cipher". Commutative encryption can be secure only as part of a protocol in which the commutative encryption primitive is not used in the same way as, say, AES. What the scenario explained above means is that a deterministic commutative cipher cannot be "IND-CPA secure" (indistinguishable from a random permutation in a chosen-plaintext attack setup). So you need some randomness injected "somewhere", which may be some padding or an other feature of the overall protocol (e.g. encryption is only applied on values chosen randomly and uniformly in a given set, which are then used to derive a "normal" symmetric key, aka hybrid encryption).


Purpose of signing the signed prekey in X3DH? I'm trying to understand the X3DH protocol used in Signal and many other end to end encrypted messaging apps. There are other questions on this site asking about why the signed prekey exists. I'm asking why the prekey need to be signed.
In section 3.3 of the specification, 4 (3 if the one-time prekey is missing) Diffie-Hellman exchanges are done. DH1 involves the identity key of one user, and DH2 involves the identity key of the other user. The SK is derived from these exchanges in addition to the other exchanges that do not involve identity keys. Notably, DH4 is computed without involving any identity key or signed key.
How does any security property of X3DH change if the signature on the signed prekey is not validated?

section 4.5 of the spec:

It might be tempting to observe that mutual authentication and forward secrecy are achieved by the DH calculations, and omit the prekey signature. However, this would allow a "weak forward secrecy" attack: A malicious server could provide Alice a prekey bundle with forged prekeys, and later compromise Bob's IKB to calculate SK.

in other words:

you want to talk to Bob for the first time
you ask me (the server) what are Bob's keys
I give you:

his real identity key
an unsigned prekey of my own
no one-time prekey

you do the X3DH with this information, and send Bob messages (making use of the output of X3DH)
unfortunately, Bob won't be able to decrypt any of these because the X3DH is not using an unsigned prekey he knows.
later on, I manage to compromise Bob's identity key, I get to decrypt the messages you had sent him at the time. Thus, there is no forward secrecy for these messages that Bob couldn't decrypt (thus, "weak forward secrecy").


Worst case one way function the worst-case one way function is defined as follows
$$\forall A \exists x : pr(A(f(x))\in f^{-1}(f(x)))\neq 1$$
can you give any example of such function?

Worst-case one-way functions exist if and only if P ≠ NP, therefore, if I were you, I would not expect to get a definitive answer to your question any time soon :).

On the other hand, if you are willing to assume that P ≠ NP, then it is not hard to construct such a function (that is actually exactly a half of the proof of the theorem I stated in the previous paragraph).


What's the safest TrueCrypt algorithm and hash? I have an encrypted file container inside my NTFS pendrive. The root folder Write permission is blocked for everyone. A folder inside it has all permissions unblocked. The dummy file of TrueCrypt is inside the "full access" folder. It has a 64 characters password, containing… you know… everything and I made a backup to create another file container.

Now, what would be regarded to the potentially "best" (in terms of security) algorithm and hash? Any algorithm and/or hash that I should definitely be avoiding? Or is the choice of algorithm and hash more a matter of personal opinion/preference because there aren’t any real differences between the available choices from a security point of view?

EDIT

In the end, I used the algorithm AES(Twofish(Serpent)) with as hash Whirpool. To me, SHA-512 is a 2nd place loser. I didn’t choose RIPEMD160 as it’s a DOS-days cipher and – if I’m not mistaken – someone might have found a way to break it? I just didn’t want to take a risk.

All ciphers offered by TrueCrypt (e.g. AES, Serpent, Twofish) are "impossible to break" to the best of current public knowledge. Which one of them will be successfully attacked first (if at all) is obviously unknown at this time, hence a matter of personal belief. The same applies to hash functions (SHA512, Whirlpool, RIPEMD160) — there are no relevant weaknesses known in any of them. The standard choice would be AES combined with SHA512.


Weaker Notion of Target Collision Resistance I'm reading the paper “Collision-Resistant Hashing? Towards Making UOWHFs Practical” which states:

  While it might be easy to find a collision $M,M'$ in $F_K$ by making both
  $M,M'$ depend on $K$ (Any Collision Resistance), the adversary may be unable to find collisions if she
  is forced to commit to one point of the collision before seeing $K$.
  We call this weakened notion of security target collision resistance
  TCR

nb: $K$ is a key used to a hash function $F$.

My question is: Why then TCR is a weakened notion if the article says that it is easier to find a collision $M,M'$ than TCR?

My other questions related to the same paper:
Dependence on Keyed Hash Function • No Birthday Attack to TCR • Weaker Notion of Target Collision Resistance

We often rank cryptographic problems according to how hard they are. One problem is not harder than another problem if an algorithm that solves the second problem can easily be turned into an algorithm that solves the first problem.

Your question considers two issues: how hard the adversary's job is, and the strength of our assumption. If one problem is not harder than another problem, then if we assume that the first problem is hard, we must also assume that the second problem is hard. However, if we assume that the second problem is hard, the first problem may still be easy.

Since assuming that the first problem is hard has more implications than assuming the second problem is hard, we say that the first assumption is stronger than the second assumption, and correspondingly that the second assumption is weaker.

Any adversary against TCR is trivially an adversary against collision resistance, so TCR is not harder than collision resistance. Therefore, we say that TCR is a weaker notion than collision resistance.


ElGamal encryption with private key Does the encryption with a private key and decryption with a public key works in ElGamal likewise what is done when we use RSA for sender authentication?

No, that does not work for ElGamal. If you look at ElGamal encryption and signatures you will see that they are fairly different.

That works for RSA because RSA is commutative, i.e., $f_{d,n}(f_{e,n}(m))=f_{e,n}(f_{d,n}(m))$ for all $m\in Z_n$ holds, where $f_{e,n}(m):=m^e \mod n$ is the enryption function and $f_{d,n}(m):=m^d \mod n$ the decryption function. You can easily convince yourself that this holds.

That is the reason for why there exists the bad practice oft teaching signatures as "encrypting with the private key" for signing and "decrypting with the public key" for verification, since the above holds for RSA and people tend to generalize that. But thats not the general case, and, as said,  is a bad practice.


How to select a 'tweak' used in FE1 mode format preserving encryption? I'm experimenting with this library Botan
which includes a module for format preserving encryption based on FE1 mode.

The parameters for the Encrypt method are as follows

        /// <summary>
    /// Generic Z_n FPE encryption, FE1 scheme
    /// </summary>
    /// <param name="modulus">Use to determine the range of the numbers. Example, if the
    /// numbers range from 0 to 999, use "1000" here.</param>
    /// <param name="plaintext">The number to encrypt.</param>
    /// <param name="key">Secret key</param>
    /// <param name="tweak">Non-secret parameter, think of it as an IV</param>
    /// <returns>The encrypted number.</returns>
    public static BigInteger Encrypt(BigInteger modulus, BigInteger plaintext,
                       byte[] key,
                       byte[] tweak)

Modulus, plaintext and key I understand, but not clear on the tweak.
How do you decide what it is and can you use the same value for all plaintext input.  Can it be any number?

The tweak is a service that the encryption method provides for you.  What it allows you to do is provide context separation for various encryptions using the same key.

Here's the problem that it is trying to help with: suppose you use the same key to encrypt a number of items; for example, suppose you're encrypting all the items in one column of a database with this key.

This leads to an issue: if the data record corresponding to Alice has a 5 in this field, and the one corresponding to Bob also has a 5 in this field, then both records would have the same encrypted value.  Someone looking at the encrypted records won't be able to tell what that common value is, however they know they're the same.  And, if Bob knows what his value is, then he knows what Alice's value is.

One obvious way to handle it is to just use a different key for each record.  That'd work, but that's a lot of keys to handle and store.

The tweak provides an alternative way to handle it; it changes the mapping between plaintext and ciphertext; however (unlike the key) we don't assume that the attacker doesn't know what it is.  In our database example, we might make the tweak the user's name ("Alice" and "Bob"); then, even if Alice's and Bob's encrypted record happen to have the same encrypted value, no one can deduce anything from that (because the mappings from the ciphertext to the plaintext is independent; they might map to the same value, and they might not).

What does this mean for you?  Well, that depends on what you're using FE1 for.  If you are literally encrypting one value with the key, well, you really don't need it - you can set it to a fixed value (say, the empty string).  However, if you are encrypting multiple values with the same key, you might be able to take advantage of it.

One final note: why is this tweak especially important for Format Preserving Encryption?  Well, with standard encryption modes, we add a randomization factor (IVs) during encryption (so that, even if you encrypt the same value twice, we'll pick different IVs), and so the encrypted text would look different.  However, this randomization necessarily makes the ciphertext larger than the plaintext.  With Format Preserving Encryption, we don't have that option; hence we need another way to address this.


Generating a secure random number in javascript What I am trying to do is generate a large (4096bit) random number in JavaScript that is cryptographically safe to use.

My approach is the following:

I am creating a Uint8Array with the desired length.
I am using Math.random() to prefill it.
I am showing a a 256x256pixel box, and show a message asking for moving the mouse around in it. For every onmousemove event, I am selecting a random byte in the array (using Math.random again), and doing a bitwise XOR with the relative X position of the mouse cursor, and doing the same to another random byte, with the Y position.
I keep processing onmousemove events until N events have been processed. (N >= a lot)

So what I have in the end is an array that was prefilled by an insecure random number generator, but whose output was mixed around with a lot of user-generated entropy.

My question is: Would the resulting number be safe to use? Or am I missing some glaring insecurity in this approach?

I would take a look at https://github.com/mdp/gibberish-aes/ From that you can see well implemented ECMAscript, (javascript) and AES can be used to generate random numbers. It might be slightly over-kill for your needs, but should not let you down in the medium-term.


If its possible to derive the public key from a private key, why can't we go in reverse? I'm looking at source code for BitcoinJ that derives a public key from the private key.

  /**
     * Create the public key from the private key
     *
     * @param       privKey             Private key
     * @param       compressed          TRUE to generate a compressed public key
     * @return                          Public key
     */
    private byte[] pubKeyFromPrivKey(BigInteger privKey, boolean compressed) {
        ECPoint point = ecParams.getG().multiply(privKey);
        return point.getEncoded(compressed);
    }

Since "G" is known, and published for each given curve, what prevents someone from dividing (or multiple consecutive subtractions) to determine the private key?

If possible, would you explain it in layman's terms, and also provide additional concepts I can research the relevant background.

Concerning your notation problem, yes that is kind of an issue. First, elliptic curves in cryptography are usually noted in additive notation. That's why the function call is called "multiply" and is not just a "simple multiplication" but in practice it uses the same principle as exponentiation for "normal numbers" (implemented mostly as "square and multiply", or in additive notation "double and add").

In the basic finite fields, however, people use mostly multiplicative notation to imply, that the DLOG problem is hard, because the equivalent problem based on the addition of numbers is quite easy (given numbers $a$ and $b$, everyone can calculate $a\cdot b$).

To answer your problem with the understanding: In elliptic curves, the "division" operation is not possible (well, computationally hard). This is based on the fact, that in elliptic curves we have only one group structure and we have to work with only this. Finite fields, however, offer us two group structures and they are linked by the distributive property, which in return makes the Diffie-Hellman problem easy for the additive group structure.


How are ECC keys stored? I am trying to figure out what typical formats and sizes, etc. are, for storing ECC public and private keys.
Some quick research turned up X9.62 (to which I don't have access) and SEC1. But then there is also X.690 which includes DER and of course ASN.1. And let's not forget PEM.
If somebody could shed some light onto the relations of these things and what is commonly used I think it would be useful.
Broadly, the question that I am trying to get answered is: What do I need to implement to decently support ECC. That would include ECDH and transferring public keys over the wire to maybe a TLS or SSH implementation but also importing and exporting of keys generated using other tools.
Somewhat related: Public-key format for ECDSA as in FIPS 186-4?

For the private key, it's common to use PKCS#8, which is a container format - a header specifying the type of the key (RSA? ECC? Which ECC curve?) and the key itself. The key itself is specified in section C.4 of SEC 1. Everything here is encoded in ASN.1 DER (DER is a concrete encoding of the abstract ASN.1 encoding), which can be saved in raw binary format to disk, or in an ASCII format called PEM which has the DER encoded in Base64 and a header/footer. Which one to use (DER/PEM) is up to the application.
You can generate a key in this format by using the openssl genpkey command, e.g. openssl genpkey -algorithm EC -out eckey.pem -pkeyopt ec_paramgen_curve:P-256 -pkeyopt ec_param_enc:named_curve. The PEM header will be "PRIVATE KEY".
Other possible formats are:

"The key itself" mentioned above directly, without the PKCS#8 header. There is no official name for this format. You can generate a key in this format with the openssl ecparam command. The PEM header will be "EC PRIVATE KEY".
PKCS#12/PFX which is a container format like PKCS#8, but allows bundling the matching certificate.

The public key usually follows the "Subject Public Key Info" structure (which is a ASN.1 structured used in certificates to include the subject's public key). This is also specified in SEC 1, and you will have the same choice between DER and PEM. It's worth nothing that it's not very usual to store the public key by itself, it's either included with the private key or inside a certificate.
For Edwards and Montgomery curves everything is similar, but the "key itself" is encoded per RFC 8410.


Deniability properties of the X3DH Key Agreement Protocol Signal's X3DH Key Agreement Protocol specification states in section 4.5.:

  Alternatively, it might be tempting to replace the DH-based mutual authentication (i.e. DH1 and DH2) with signatures from the identity keys. However, this reduces deniability, [...]

How exactly does replacing DH1 and DH2 with signatures reduce deniability?

I think, using of signatures means something like STS protocol (https://en.wikipedia.org/wiki/Station-to-Station_protocol).
In STS, for the purpose of mutual authentication,
each party must send a signature of ephemeral keys.
So, in terms used in https://signal.org/docs/specifications/x3dh ,
Alice should sign EK_a || SPK_b, and Bob should sign the same.

In X3DH, authentication provided by signatures is substituted by
the fact that for getting the key (SK) each party should execute DH exchange using his identity key (say, ID_a) and counter-party's ephemeral key (say, SPK_b). So, in fact, signing of SPK_b with private key of ID_a (in STS) is substituted with just running of DH for ID_a and SPK_b (in X3DH).

So, what's the difference for deniability? Very simple: signature is evidence of communication and knowing of ephemeral keys, and hence knowing of SK. While running of DH is not an evidence, because it's even impossible to know wether Bob (or Alice) run DH and get SK or not.
If Alice will want to prove to some judge that Bob communicated with her,
and Bob knows some SK (and hence - he could create or at least decrypt some cypher-texts provided by Alice to judge), she can't prove it:
it's obvious that Alice could simulate DH with any EK_a key she wants. There's no evidence that Bob was running DH with EK_a and even know about existence of such EK_a.


Given $P=xG$, prove in zero knowledge that I know $sqrt(x)$ Assuming that x has a sqrt.

Given $P=xG$ is it possible to prove that I know the $sqrt(x)$ in zero knowledge?

My answer simply extends the comment by SEJPM.

Since the group has prime order (as you said in the comment), and since you assume that it is known that $x$ has a square root, you can simply prove knowledge of $x$ such that $xG = P$, using the standard Schnorr protocol for demonstrating knowledge of a discrete logarithm (see e.g. the wikipedia page, or my description here for a simplified security analysis of this protocol).

Now, since knowing $x$ is equivalent to knowing $\sqrt{x}$ in a group of prime order (each can be computed from the other in polynomial time), convincing the verifier that you know $x$ does also convince him that you know $\sqrt{x}$. Since the proof leaks nothing about $x$, it leaks nothing about $\sqrt{x}$.


What is the recommended x length in the Diffie-Hellman algorithm? According to RFC 3526 & RFC 2412, the prime and the generator are defined, but there is no recommended length for the parameters of random number $x$. What is the recommended length of random number $x$?

In my case, I set the length of $x$ at 160 bits with a 1024- & 2048-bit prime.

Is it safe?

Actually, RFC3526 does have recommendations for the random number size; see section 8, and the table listing "exponent size".

Now, it gives two different recommendations (which sounds rather less useful than giving one); the summary is that if the size of the random number you pick is $x$ bits, then an attacker can recover the shared secret with no more than $2^{x/2}$ work.  If you're happy with 80 bit security, then selecting a 160 bit random $x$ is sufficient.  If you want significantly more than 80 bit security, well, you might want to rethink the 1024 bit group.


Encryption that could have multiple decryption key The title looks strange but it is to deal with this situation.

The data we have should only be accessible by our end user and data administrators, not anyone else. Ideally, each user should have different encryption key.

Even with administrators, I wish only when two of them agrees, then they could access the data by join two pieces of the key. I could think of doing this by breaking up the key into two half, and each one of them holds half the key.

Is there such a cryptography can achieve this? So the file could be decrypted by more than one key. Or any other recommendations?

What you ask is very well possible.

Let's assume you have a document DATA you want to encrypt. You first randomly generate a symmetric key K and authenticate and encrypt DATA using this one.

In the next step you asymmetrically encrypt K with the end user's public key and store the resulting cipher text along with the encrypted data.
For allowing your administrators to access the file only when at least two collaborate you have two options:

Secretely share a private key among the administrators using a threshold of $k=2$ and encrypt K using the corresponding public key. The drawback of this one is, that the admins actually learn the private key and nothing can stop them from decrypting all files without per-file collaboration of two admins.
Give each administrator a private key and secretely share a symmetric key (with a threshold $k=2$) that can recover K (on a per-file basis). Encrypt the shares using the admins' keys and store them with the encrypted DATA and when they need to access a file, they first have to recover the symmetric key using secret sharing and then they recover K. The advantage here is that for each file two administrators have to collaborate but the drawback is that you now need to store $n$ ($n$ being the number of admins) asymmetrically encrypted cipher texts instead of $1$.


Are basic replacement ciphers always bad for structured data encryption? I have read that basic replacement ciphers, such as replacing one byte with another specific byte at each location, are far less effective with non-randomized data. My question is, can this problem be mitigated to the point where basic ciphers can be effective on structured data by encrypting the data with other methods before passing it through the basic cipher?
For encrypting exclusively highly structured data, are basic substitution ciphers useful from early on in the encryption process, such as directly after something simple like a single XOR, or only after heavy encryption or should such basic replacements be avoided for this purpose all together?

A good encryption should produce data that are indistinguishable from a random stream. If you simply replace bytes with other bytes, and each byte has always the same replacement, many statistical characteristics of the original message remain. For instance, if the original message is text, then the frequency of each letter will remain also after applying byte-by-byte replacement.

by encrypting the data with other methods before passing it through
the basic cipher

If you encrypt the data with other methods, for instance with AES, there is no need to do any further encryption of the encrypted message. AES is unbreakable.
The question about multiple encryption was answered on SE many times. See for instance this.


implications of SSH server key compromission when authenticating users against a public key Friday we had a disagreement with a colleague of mine about the implications of SSH server key compromission

The question was stated as this :

  What could a hacker do while provided with the SSH server private key
  and a MitM position specifically when the client is authenticated with a
  public key (server configuration disallow password-based authentification)

after 20 minutes we could agree on the following facts :

Stream decryption (eg. Is SSH using temporary keys encrypted with both public keys ?)
Stream tampering (same question with HMAC keys)

Identity theft : (being able to tamper a root connexion and replace users public keys with the hacker's in the server ; user's private key is safe in his computer ... is it ?)
Identity substitution : being able to hijack the auth dialog to the compromised server and replay it in real time with an other non-compromised server auth dialog (==> hacking server A, hijaking client C connection to server A and connecting the pirate as C to the non-compromised server B)

(placeholder for any other ideas :) )

Can anyone help us to sort these out ?

Answer see @PauloEbermann answer below or this article http://www.gremwell.com/ssh-mitm-public-key-authentication

In the common configuration of SSH, the session keys (and a session ID) will be negotiated using the Diffie-Hellman key exchange, and then authenticated by the server, using its private key to sign all the exchanged data (which is then checked by the client).

The public key authentication of the client happens after that, when the actual connection is already running, and does not influence the encryption (and MAC). But the public-key authentication is a signature over multiple values, including the session identifier.

So, in effect, if the attacker has the server's key she can pretend being the server (to the client). She would have to accept the public key login, and show the client some shell or similar.

What does not work for the attacker is to connect at the same time (as a client) to the server and use the client's public key authentication to authenticate itself to the server, as the signature includes the session ID, and the session ID will be different for different Diffie-Hellman key exchanges.

Also, it seems not possible to manipulate the Diffie-Hellman key exhange in a way that one still knows the created keys, and they (as well as the session ID) are the same for both connections.

With RSA key exchange (where the client simply RSA-encrypts the some random data with a transient server key and sends it to the server, and both sides derive everything from this then shared secret (and the other stuff that was exchanged, like the public key, the offered key exchange methods and so on), a MiTM-attack (knowing the server's transient private key) is feasible - simply decrypt this message, then you know the keys used both for encryption and authentication (and the message-ID), and can read and modify all further messages.

If she only knows the server's long-term private key, this is not so simple: While she can replace the transient server key with her own one, this results in a different session ID (and session keys), and as such the public-key authentication of the client will not work anymore for her.


Is md5(x)&md5(y&x) secure? I was wondering if the following hash function

f(x) := md5(x) & md5('abc'&x)

(with & as concatenation operator) is secure.

This schema can be even extended like this:

g(x) := md5(x) & md5('abc'&x) & md5('def'&x)

To find a collission in f(x), following requirements would be met:

f(x)=f(x'), x!=x' <==> md5(x)=md5(x') ^ md5('abc'&x)=md5('abc'&x')

or

g(x)=g(x'), x!=x' <==> md5(x)=md5(x') ^ md5('abc'&x)=md5('abc'&x') ^ md5('def'&x)=md5('def'&x')

Is this realistic that such a condition can be found? I can't imagine that.

[I would be happy to learn more about the math behind it]

Secure against what and for what purpose?

MD5 remains too fast for most human typed passwords.  You should use something like bcrypt or PBKDF or sha256crypt where there are a tunable amount of thousands to millions (or more) rounds of hashing to generate each hash.  You really don't want to allow users to try several billion hashes per second per GPU.

f(x) := md5(x) ++ md5('abc' ++ x) will be just as vulnerable to preimage attacks as md5 -- that is given some hash f(x) = 5d41402abc4b2a76b9719d911017c592d76051e1dae76d1f309598102df58d84 find x.  You simply truncate look at the first 128-bits of the 256-bit hash and it reduces to the problem of md5(x)=5d41402abc4b2a76b9719d911017c592, which you can type into several online md5 reverse lookups (the second half reversed too without me adding it).  So you can see this method will not be secure for user chosen passwords (at least for typical users).

Luckily, last I checked (and according to wikipedia), there are no practical publicly known preimage attacks on MD5 for high-entropy strings.  There is a MD5 preimage attack that takes 2123.4 instead of the full expected complexity of 2128 for a 128-bit hash, but it will not be practical (about 24 times faster than brute force).

Now md5 is not collision resistant.  It is possible to construct pairs of text such that m1 != m2, while md5(m1) == md5(m2).  Granted if you found a collision in md5, this collision would not work immediately for f(x) as in general md5('abc' ++ m1) != md5('abc' ++ m2) when md5(m1) == md5(m2).  However, the underlying flaws of md5 is that is built on the Merkle-Damgård construction will still be present and probably could still be exploited (things like how md5(m1++x) == md5(m2++x) will always be true if md5(m1) == md5(m2)) and could probably still be exploited (even if its not immediately obvious and would be more complicated than simply combining existing attacks).


Is a hash function used to expand the key after ECC shared secret is complete? I have designed an ECC engine in silicon that handles any curve in the form of $$y^2 = [ax^3 + bx^2 +cx + d] \mod(P)$$

The shared secret is then passed to symmetric encryption engine, which happens to be Simon.  The system is asynchronous and simulates great, but there's an occasion situation where I can have a key underflow.

As an example, the shared secret is 160-bits, but my Simon 128/256 has a 256-bit key.

If the solution to the curve is longer than what I need, I can just truncate the value to fit into my symmetric key requirement; however, in the case that it's shorter, it doesn't make sense to have all of those bits be zero.

This hardware doesn't check for a sane user, so if you want to tell it to do a 4-bit ECC, it'll do that.  For this reason (and because I'm doing the hardware), it seems like there'd be a hash that is used for the shared secret so it is expanded into the key bit width.

Is there a NIST standard or a paper that specifically describes how this situation should be handled?

First of all, you would probably want to put the shared secret into a KDF even if you have enough bits to use it in a symmetric encryption algorithm. Check these two related posts: Key Derivation Function (KDF): Can a key derived from KDF be considered as a secure key? and How to derive a symmetric key from ECDH shared secret?

  So, the question: Is there a NIST standard or a paper that
  specifically describes how this situation should be handled?

For a standard way to handle this situation you can check the IEEE Std 1363-2000 document, particularly section 9.2.2 which show the steps of key agreement operation. The algorithm given in that document uses the shared secret as an input to a KDF function which generates the agreed key (could be the symmetric encryption key in your case).


How much time would it take to crack time mnemonic phrases in these scenarios? How long time would it realistically take to crack each of following scenarios and how many combinations does each scenario consist of?

Mnemonic Phrase, it is not known if we are looking for a pass-phrase of 12, 13, 24 or 25 words

Scenario 1: There are total 90 words shown on a single sheet of paper.

Scenario 2: There are total 180 words shown on two sheets of paper (90 each). It is not known how many words (of pass-phrase) are on each sheet of paper (meaning one sheet could have 0 and the other all)

You can calculate the number of word combinations for each possible pass phrase length and then add them together. For mnemonic phrases any order is valid, so it is a question of calculating the exponentiation of the number of words on the sheet with the number of words in the phrase.

Finally, there are two scenarios, which should be considered separately. For the first scenario there is just a single sheet of 90 words. For the second there are two sheets, but as the words do not need to be distributed over the sheets you can simply think of it as one sheet of 180 words.

Finally, if you want to know the number of bits of security you can simply count the number of digits, divide by 3 and then multiply with 10 to get a rough estimate (or perform $\log(c) / \log(2)$ where $c$ it the total number of combinations).


Why do elliptic curves require fewer bits for the same security level? I'm studying the basics of cryptography and I didn't understand why elliptic curves use fewer bits.
For example, finite-field Diffie-Hellman needs at least 1024 bit and it's a DLP, but elliptic curves need at least 256 bit and it's also a DLP.
What is the actual difference? Can you show mathematically why (with some example)?

I know that they aren't the same DLP, but they are part of the class of DLP. Is this part of the explanation?

The DLP of EC is more difficult to solve for how the group laws are defined, but is this the explanation (or part of it) to why EC requires less bit?

The best algorithm for computing discrete logs in a well-chosen finite field $\mathbb Z/p\mathbb Z$, where the safe prime $p$ has no structure that can be exploited by the special number field sieve, is the general number field sieve, or GNFS for short.  The GNFS costs $L^{\sqrt[3]{64/9} + o(1)} \approx L^{1.92999 + o(1)}$ bit operations, where $L = e^{n^{1/3} (\log n)^{2/3}}$ and $n = \log p$.  If we treat the $o(1)$ term as zero, to raise this cost above $2^{128}$ we need to pick $n$ so that $$2^{128} \leq e^{1.92999 n^{1/3} (\log n)^{2/3}}.$$  Solving this in closed form is a pain involving the Lambert W product log function, but if we restrict our search to $1024 t$-bit primes $p$ so that $n \approx 1024 t \log 2$, we find the smallest bit size is $1024 t = 3072$.  If we allow merely raising the cost above $2^{112}$, we can make do with $1024 t = 2048$.

\begin{equation}
\begin{array}{cc}
\text{modulus bit size} & \text{GNFS cost: $L^{1.92999}$} \\
\hline
1024 & 2^{87} \\
2048 & 2^{117} \\
3072 & 2^{139} \\
4096 & 2^{157}
\end{array}
\end{equation}

Caveat: There may be batch optimizations like there are in the NFS for factoring[1].  So these may be optimistic overestimates when the adversary has a large number of targets to attack simultaneously.  There are also other reasons—performance, storage costs, and side channel security—to prefer elliptic curve groups over finite fields, but that's a topic for another question.

In contrast, the best algorithm for computing discrete logs in a well-chosen elliptic curve group of order $\ell$ is essentially a generic algorithm for finding discrete logs in an arbitrary group, namely Pollard's $\rho$ algorithm, with merely small constant factor speedups for elliptic curves, and costs $\sqrt{\ell \pi/4}$ curve additions, which will require hundreds of bit operations apiece.

The square root cost means that if we want the cost of an attack to be $2^\lambda$ then we need to choose a group of prime order $(2^\lambda)^2 = 2^{2\lambda}$.  By Hasse's theorem, the order of the curve group over a coordinate field of order $q$ can't differ from $q$ by more than about $\sqrt q$, so we need to choose a curve over a finite field with about twice as many bits as we want bits of security $\lambda$.  Some curves like NIST P-224 are chosen to have groups of prime order, while others like Curve25519 are chosen to have groups of composite order $h \ell$ for small cofactor $h = 8$ and large prime $\ell$ so $\ell \approx q/h$.

\begin{equation}
\begin{array}{cccc}
\text{group} & q & {\approx}\ell & \text{$\rho$ cost: $\sqrt{\ell \pi/4}$} \\
\hline
\text{NIST P-224} & 2^{224} - 2^{96} + 1 & 2^{224} & 2^{111} \\
\text{Curve25519} & 2^{255} - 19 & 2^{252} & 2^{125} \\
\text{edwards448} & 2^{448} - 2^{224} - 1 & 2^{445} & 2^{222}
\end{array}
\end{equation}

In brief, there are much cheaper algorithms for computing discrete logs in the finite field $\mathbb Z/p\mathbb Z$ than for computing discrete logs in the elliptic curve $E(\mathbb F_q)$, so we need to choose $p$ much higher than $q$ for the same security.


Why does BCRYPT_RNG_DUAL_EC_ALGORITHM get removed from CNG API on Windows 10? On article at => Microsoft Docs

  CNG Algorithm Identifiers

I notice that BCRYPT_RNG_DUAL_EC_ALGORITHM is now removed since Windows 10.

  Beginning with Windows 10, the dual elliptic curve random number generator algorithm has been removed. Existing uses of this algorithm will continue to work; however, the random number generator is based on the AES counter mode specified in the NIST SP 800-90 standard. New code should use BCRYPT_RNG_ALGORITHM, and it is recommended that existing code be changed to use BCRYPT_RNG_ALGORITHM.

Does this imply that Elliptic Curve PRNG is considered unsecure already?

The Government's elliptic curve backdoor is real, isn't it?

The Government's elliptic curve backdoor is real, isn't it?

We don't know for sure, but there are indicators into that direction. More importantly though,

yes, you can backdoor the RNG, as was pointed out shortly after its publication (PDF)
yes, the parameters have been replaced in-the-wild by attackers to break VPN appliances using this RNG.

  Does this imply that Elliptic Curve PRNG is considered unsecure
  already?

As you saw above, using Dual-EC can be a real exploitable risk. There are however additional reasons why Dual-EC isn't the greatest random number generator and why people wouldn't want to use it:

It's no longer in the list of NIST specified RNGs and was removed from SP 800-90A rev.1.
It's very slow compared to all the other "approved" RNGs (like three orders of magnitude slower).
It doesn't even have a security proof, which is the only reason why you would want to use such a slow RNG in the first place and more specifically...
It's output is actually distinguishable from random (which is like the bare minimum of a security guarantee no RNG should violate)!

So TL;DR: Yes, the Dual-EC is backdoorable and slow and not even properly random and was probably dropped because of that.

Additional reading: Matthew Green's blog post on the subject (which is also a source for this answer) as well as Bernstein's, Lange's and Niederhagen's "Dual EC: A Standardized Back Door".


Pohlig-Hellman Algorithm: Adding up the solution via CRT I have a question about the Pohlig-Hellman Algorithm for the discrete log problem. I understand the concept, but doing the exact calculations I get confused at one point; to illustrate, let's look at the equation $2^x=3$ in the group $(\mathbb{Z}/29\mathbb{Z})^*$.

If my calculations are correct, we get that $x \equiv 1$ in a subgroup of order 4 and $x \equiv 5$ in a subgroup of order 7. Using the isomorphism $((\mathbb{Z}/29\mathbb{Z})^*, \cdot) \cong (\mathbb{Z}/28\mathbb{Z}, +)$, we get the equations $$x \equiv 1 \mod 4 \\ x \equiv 5 \mod 7$$ which is then pasted together using the Chinese Remainder Theorem to get $x \equiv 5 \mod 28$.

Now here is where I am confused: The results x=1 and x=5 are derived using calculations in $((\mathbb{Z}/29\mathbb{Z})^*, \cdot)$. Why can we just 'transfer' the very same numbers to the respective subgroups of $(\mathbb{Z}/28\mathbb{Z}, +)$, when we do not know the image of these elements under the isomorphism? Is it just because we are technically already in the group $(\mathbb{Z}/28\mathbb{Z}, +)$ when we are dealing with the exponents? Or am I missing something more crucial here?

Thank you in advance for any kind of advice.

Because $x$ is defined modulo $28$ ($2^{28} = 2^0$ in $(\mathbf{Z}/29\mathbf{Z})^*$), you can view $x$ as an element of $\mathbf{Z}/28\mathbf{Z}$, while $2$ and $3$ are elements of $(\mathbf{Z}/29\mathbf{Z})^*$.


How can two keys have the same KCV? I have two keys and they have the same KCV. How is this possible?

I have encrypted data with both keys and I have the same result. Both keys are the result of the derivation of the same IMK, one was done by a software and the other one was done by manual process.

Key A: 04 A4 49 F2 DC 46 D3 2A 3E A7 C7 E3 D3 A1 AB BA
Key B: 05 A4 49 F2 DC 46 D2 2A 3E A6 C6 E3 D2 A1 AB BB

Data: FF FF FF FF FF FF FF FF 11 11 11 11 11 11 11 11

Encrypted with key A: 22 17 FE 9C BC 6E DC F1 F2 D1 13 CA 70 74 54 AA
Encrypted with key B: 22 17 FE 9C BC 6E DC F1 F2 D1 13 CA 70 74 54 AA

You're using 2-key 3DES, right?

DES and 3DES has the property that the least significant bits of the key don't actually contribute to the encryption process; hence any two keys that differ only in the least significant bits will be equivalent (and hence have the same KCV value)

Your KeyA and KeyB has exactly this property.

Aso, is there a specific reason you're not using a more modern cipher, such as AES?

As a side note: normally, when we encrypt data, we typically stir in some uniqueness (such as an IV); hence encrypting the same data twice with the same key generally results in different ciphertexts.  We do this for several reasons: to hide when we do encrypt the same thing twice, in order to disguise when we encrypt different but related plaintexts, and to foil some potential chosen plaintext attacks.  You obviously don't do this; you use using 'ECB mode'?  If so, well, that's rarely the correct option...

BTW: I suspect that KeyA was done by software, and KeyB was done manually.  Here's why: every byte in KeyA has odd parity.  The original DES documents suggest that the lsbit of each byte be set so that the byte has odd parity (both to catch some simple typo's (it was anticipated that humans would manually enter the keys), and also to justify the otherwise unused lsbits).  I suspect that the software actually attempts to conform to this, and automatically adjusts the lsbits appropriately.


Why does GPG ciphertext length differ with fixed plaintext length? Thank you for your reply.
Based on your inputs. I was investigated further, find details below

Step 1) Input string for encryption is UUID format
Input data = c0c6f311-a793-4d65-9374-1c0e45f5382c
Length  = 36 bytes
Step 2) encrypt UUID with gpg command
    gpg --encrypt -r  PublicKey c0c6f311-a793-4d65-9374-1c0e45f5382c
Step3) encrypt gpg output using base64 command
    /usr/bin/base64 -w 0  gpg-encrypted-data(step2 output)

I had been ran same 36 bytes input data (c0c6f311-a793-4d65-9374-1c0e45f5382c) continuously(90000 times)  using step2 and step3, observed below possible outputs

1)gpg encrypted 36 bytes input data to 389 bytes  and base64 encrypted 389 bytes input data to 520 bytes   --  89996 times out of 90000
2)gpg encrypted 36 bytes input data to 387 bytes  and base64 encrypted 387 bytes input data to 516 bytes   -- 4 times  out of 90000
3)Able to decrypt the 516 0r 520 bytes encrypted data with orginal Input text(c0c6f311-a793-4d65-9374-1c0e45f5382c)

Please find some of the base64 command outputs gathered from above execution.
    520 bytes output last few characters
1)  LG1bEwdUt3Sh6ea6cUrDk=
2)  Gwpr0kClWzllff6KgNo=
3)  FLyCFDlMDQD6GiKJITBIjg=
4)  NbJ6y3mayCiWN8yZ9HQsJV+KQ=

516 Bytes Output
1)  JpTKn/7yS/0JBhH9TVTRxRNwhmh
2)  Vzlo7c2zH2y3kB3PK+ihAyBfA
3)  ZlvAgKJQFe39+IT6giO1nQxZcwkX

I have few more questions above execution

Q1)  padding is happenings both encryption level(i.e  gpg, base64)
Q2) is there any way to handle fixed length encryption?
Q3) is there any way to remove padding encryption in both levels(i.e gpg, base64)?
Q4)Actually we are assuming that base64 encryption happening with 520 bytes, even above execution also 99% encrypted with 520 bytes. Is there any way to padding 516 bytes encrypt to 520 bytes encryption?

TL;DR: There are different possibilities: A timestamp is included before compression, and can result in slightly different compressed message lengths. The encrypted session key is stored as multi-precision integers, which are of dynamic length. Finally, ASCII-armoring adds a padding that might enlarge the size difference slightly.

Compression and Timestamps

When using OpenPGP, different operations are performed one ofter the other, you could compare them to multiple layers put around the original data. The message is wrapped with some meta information (the "literal data packet"), then compressed, finally encrypted. Often there are different alternatives in the individual steps, but in the end it mostly boils down to these operations. I especially ignore the fact OpenPGP is a hybrid cryptosystem, as this adds complexity but is not relevant to this question.

Using a kind of formula notation, you can simplify the operations as

encrypt(compress(literal(message, filename, timestamp)))

If you observe this, you will realize repeatedly encrypting the same message will always return another result: the timestamp is also contained as message metadata (there's also some randomness in choosing symmetric keys, but that's another story that leads to completely different crypto texts). As the timestamp is also subject to compression, different timestamps might compress worse or better, this can indeed lead to minor differences in the size of the encrypted message.

faketime

This might or might not be the only reason, but you should be able to easily evaluate using the handy faketime tool available for probably all unixoid systems. Most Linux distributions include it in their packet managers. It sets a fixed system time for the application executed. If the timestamp is the only reason for different message sizes, you should get messages of the same size now:

faketime 2015-12-02 gpg --encrypt ...

Multi Precision Integers and Session Key

The encrypted random session key used for encryption of the message is stored as multi precision integers, which do not have fixed length. Although these session keys are expected to be of similar size, the might be rare cases (one out of 256) that the encrypted key has all first 8 bits set to 0: as a result, the result can be stored with one byte less (and still being the same number). In very rare cases this might even lead to multi-byte differences.

ASCII armoring

Finally, ASCII armoring cannot be the reason for different sizes, but can enforce already existing differences because of padding the output to multiple of three bytes, adding up to two bytes if necessary (resulting in a message larger by only a single byte being padded by up two additional bytes).


How and why can a decryption program tell me that a key is incorrect? I have noticed that some programs used for file encryption will tell you if an entered key is wrong when you try to decrypt. It seems (to me at least) that this would mean that the key somehow is written into the encrypted file. And the algorithms that I know of will produce an output even if the key is wrong.

How does one built into an algorithm this type of validation of a key? Is it just a matter of encrypting the key with the original text?
Is this a security problem?

It's not a security problem but a necessary feature. It's not an exact science to distinguish a "good decryption" from a "bad decryption". What if the user had encrypted random data? you would not be able to figure out if the key is correct or not from that sole information, since in both cases the decrypted output would look completely random!

Similarly, what if the user typed his key wrong? You want to be able to inform him he made a typo ("invalid password") instead of blindly decrypting garbage and waiting for the user to realize he typed it wrong and try again.

What most programs do is store the hash of the key (or an HMAC of the encrypted file, using the encryption key) so that they can verify if the key is correct (or if the file is corrupt - you get free integrity/authentication with the HMAC method) without disclosing the key at all. An attacker would need to find an exact preimage to obtain the actual encryption key, which is designed to be infeasible.

In essence, you use a one-way function to store the key's image somewhere in the file, so that anyone without the key cannot invert the function and retrieve the key, but anyone who has the key can easily feed it into the one-way function and compare the result with the value that's in the file. If it matches, it's the correct key! (with very high probability)


What is the name of this method? Say I have a $26\times 26$ matrix $M$, each column$C_i$ of which contains the numbers from 1 to 26 in a random order. To encrypt a word, I take the first letter (e.g., b), convert it to its index $i$ (here, 2) and take the $i$th element of column $C_i$ for the first letter. Let's say that b becomes d. Then I take the fourth column $C_4$ (because $d$ is the fourth letter), convert the second letter to its index $j$ and encode it with the $j$th element of $C_4$, and so one.

Example with four letters $a,b,c,d$: take

$$ M=\begin{bmatrix} 2 & 2 & 4 & 3 \\ 3 & 3 & 1 & 4 \\ 1 & 4 & 3 & 2 \\ 4 & 1 & 2 & 1\end{bmatrix} $$

to encrypt $bacd$: the first letter, $b$, has index $2$, so it will be coded by ${C_{1}}(2)=3$, so $c$. For the second letter, we use $C_3$; $a$ has index 1 so it becomes $C_3(1)=4$, that is, $d$ and the next letter will be coded with $C_4$. $c$ has index $3$ so becomes $C_4(3)=2$, so $b$ and the next letter will be coded with $C_2$. $d$ has index $4$ so becomes $C_2(4)=1$, so $a$. Finally, $bacd$ becomes $cdba$.

My question is, is this method known (certainly!) and does it have a name? One advantage is that is avoids simple statistical analysis on the frequency of letters.

This is a form of polyalphabetic substitution cipher. I'm not aware of this particular method having a name.


Question on Tokenization and the need to maintain a value to token lookup I'm a newbie and an idiot to boot. I've a question in relation to tokenizing: is there a methodology out there that would allow you reidentify without using a token to value lookup?  I'd have thought no but have a developer claiming something different.  I contend that what he's talking about is an encryption process.

You could use for example an asymmetric keys pair, where the private key is stored on the user's device, and where the public key is saved in the server side.

At sign-in, the server send a challenge request (random bytes + current timestamp), the client need to sign the challenge and the server can verify the signature.


What is the size of a 1024-bit RSA cipher compared to its plaintext? Let's assume we encrypt a 50000 bit plaintext with 1024-bit RSA and public exponent $e$ = 3: How big will its cipher be?
When we increase the exponent to let's say $e$ = 216 + 1 = 65537, how big will its cipher be then?

RSA is almost always used in hybrid mode, where AES (or another symmetric cipher) is used to encrypt the data itself, and RSA is then used to encrypt the random data key. That way RSA has only a static overhead: the modulus size (which is also the key size) in bytes. So for RSA-1024 that would mean an overhead of 128 bytes + whatever overhead is required for the symmetric cipher (which can be zero bytes if a stream cipher or stream cipher mode such as counter mode is used). In that case you'd have $50000 / 8 + 1024 / 8 = 6250 + 128 = 6378$ bytes if I'm not mistaken.
Using unpadded / raw or textbook RSA (i.e. RSA using only modular exponentiation) is insecure. So you always need to pad the plaintext message within RSA. In that case you would for instance use RSA-OAEP as defined in the later PKCS#1 standards. This padding scheme adds quite a lot of overhead. Generally we don't care about that, because there is plenty left over to encrypt a symmetric key when using hybrid encryption. However, if you'd use multiple RSA encryptions in sequence then you would have an overhead of 42 bytes and a payload of only 86 bytes, assuming a SHA-1 hash within OAEP for minimum overhead. A single encrypted partial message would still be 128 bytes. So you would have $\big\lceil 6250 / 86
 \big\rceil \cdot 128 = 73 * 128 = 9344$ bytes taken, an increase of $2966$ bytes (!)
A few notes to these calculations:

RSA as specified in PKCS#1 always sets the output of encryption to be the modulus size in bytes, even if the actual number is smaller. That way the size is always static and doesn't need to be indicated (unless the key size is not known in advance). If you would allow alternating sizes then you would need to indicate the output size of each encryption, or you would not be able to separate the resulting RSA ciphertext blocks.
RSA-PKCS#1 v1.5 padding can also be used. PKCS#1 v1.5 padding is an older, less secure scheme. PKCS#1 v1.5 padding has somewhat less overhead in the non-hybrid scheme.
RSA-KEM is another scheme for hybrid encryption. It doesn't encrypt a symmetric key; it encrypts a master secret used to derive a symmetric key and is arguably more secure. It doesn't add any overhead to hybrid encryption. It cannot be used to encrypt the message directly or in parts.
Message integrity / authenticity is not taken into account in above. If that's required generally we use a sign-then encrypt scheme which increases the plaintext message before encryption.
Generally other overhead is also present. For instance, CMS based encryption also indicates certificates and algorithms used to the receiver. So you cannot generally expect the plaintext message to expand only with regard to the RSA key size.
RSA-1024 has already been deprecated by NIST (for medium and long term encryption) and is generally considered too small. Note that increasing the key size actually has positive effects on the relative amount of overhead required (when concatenating RSA encryption of partial messages); a larger RSA key size would actually be beneficial w.r.t. size. Unfortunately, that comes at a price of ever increasing CPU requirements, especially for RSA decryption and (one time) key generation.


How hard is Self-DLOG? This question while asking for something different brings up an intriguing problem: If you can find $x$ such that $x\equiv R^x\pmod p$ then you can break DSA. Now I thought that one might be able to relate this to the discrete logarithm problem somehow, but I failed to find the relation and so I'm asking this (somewhat more general) question.

Now my question is:
Let $p$ be an arbitrary prime, does there exist an algorithm faster than $\mathcal O(p)$ which, given $p$ and an arbitrary $R\in\mathbb Z$, finds an $x\in\{y\in\mathbb Z\mid 0\leq y<p\}$ such that $x\equiv R^x\pmod p$ if such an $x$ exists or $\perp$ otherwise?

The problem about fixed  points of discrete logarithms is  known the Brizolis problem. In particular for the average number of solutions
$$N(p)=\frac{1}{\varphi(p-1)}\sum_g\left|\{0\le x\le p-1:g^x=x\pmod p\}\right|$$ is known that (Grechnikov, 2012) $N(p)=1+S(p)$, where
$$-C(\varepsilon)p^{-1/4+\varepsilon}\le S(p)\le \exp(C'\mathrm{Li}((\log p)^{c\frac{\log\log\log\log p}{\log\log\log p}})).$$

It is also necessary to say that inversed problem is easier: for a given $x$ one can take $R=x^{x^{-1}\bmod (p-1)}.$


In what cases will RSA not work? I know that there are cases when RSA will not work like when the number to feed into the system is greater than the modulus. I was wondering if there were any other cases when RSA won't work

I looked all over and tried rephrasing the question in google many times

Edit: I am looking for what cases exist with a valid n, e and d used properly will not encrypt and decrypt correctly eg: message <= n

It should be proven in any presentation of RSA that, with a correct public modulus $N$, public exponent $e$ and private exponent $d$, all integers $m \in \{0,1,\dots,N-1\}$ satisfy
$$\left(m^e\bmod N\right)^d\bmod N = m.$$
So it is only possible for a number to "not encrypt or decrypt correctly" when it is not in $\{0,1,\dots,N-1\}$. Moreover, this necessary condition is obviously also sufficient, because the result of a $\bmod N$ operation will be in this set, so if $m$ is outside it, it can't possibly equal the result of the above computation.


Are there simpler FHE methods than Craig Gentry's original paper? Craig Gentry's 2010 paper on FHE is very cool, and I'm planning on implementing a basic proof of concept FHE.

I was wondering though, are there any simpler methods that have been discovered since then?

The bootstrapping and the multiplication pre shared table would be nice to get rid of if possible.  (I'm sure the whole world agrees, but is glad it can be done at all).

Anything simpler out there yet?

Here are the references I've found / have been using while trying to implement it.  Note that I have been looking to implement it myself after understanding the theory, so haven't been looking for existing implementations, although definitely would look at them if having problems implementing.

http://windowsontheory.org/2012/05/01/the-swiss-army-knife-of-cryptography/

http://outsourcedbits.org/2012/06/26/applying-fully-homomorphic-encryption-part-1/

http://crypto.stanford.edu/craig/craig-thesis.pdf

http://researcher.watson.ibm.com/researcher/files/us-shaih/fhe-implementation.pdf

And then of course the links provided by people as comments in response to this question!

As you point out, there is the DHGV 2010 scheme over the integers based on the approximate GCD problem but asymptotics are not great with this scheme, for eg. one of the parameters for DHGV is around $2^{\mathcal{O}(\theta^{5})}$ where $\theta$ is the security parameter.

Of the so called second generation schemes, I would say that BGV has been pretty well benchmarked from a performance standpoint (https://people.csail.mit.edu/vinodv/6892-Fall2013/BGV.pdf) - BGV is based on hardness of lattice SVP (Gentry's original scheme, on the other hand was based on two hardness assumptions - the ideal coset and the sparse subset sum problems - additionally, it required some machinations around "squashing" the scheme's decryption circuit in order to make it boostrappable).

BGV is both "leveled" and bootstrappable and there is variant that utilizes Ring-LWE encryption with an "aggregate" plaintext space that consists of integer subrings of cyclotomic number fields $\mathbb{Z}[X]/\langle \Phi_m(X),p \rangle$ where $m$ is a power of 2. The Ring-LWE BGV variant also utilizes Smart and Vercauteren's application of "double" Chinese Remaindering as a structure theorem for it's aggregate plaintext space, thereby allowing for SIMD operations on the data - what this means is that the scheme allows one to encode multiple messages within "slots" in the aggregate plaintext space, and then perform parallel homomorphic Add and Multiply operations on the messages (https://eprint.iacr.org/2011/133). Also, since we're talking about encoding messages as polynomials, FFT can be utilized for fast multiplcation of ciphertext polynomials. Last but not least, BGV leverages automorphisms associated with the plaintext's cyclotomic number field to "permute" slots or elements without having to unpack the ciphertext - so the upshot of all of this is that BGV allows for pretty efficient homomorphic evaluation - a fact that is evidenced by this study on homomorphic evaluation of the AES circuit - https://eprint.iacr.org/2012/099.pdf. In summary, this paper demonstrates amortized time of 2 seconds for homomorphic evaluation of AES encryption per block at lattice dimension 46080 on a commodity laptop - the implementation leverages the so called "Gentry Halevi Smart optimizations" that are outlined here - https://eprint.iacr.org/2011/566.
Halevi and Shoup's HElib provides a BGV backend with all of the features described above. Leo Ducas land Daniele Micciancio have another HE library available here https://github.com/lducas/FHEW, however I am not familiar with this scheme. I should also mention there is the multi key scheme by Lopez, Tromer and Vaikuntanathan based on the NTRU problem and a benchmark of homomorphic evaluation of AES based on this scheme over here - https://eprint.iacr.org/2014/039.pdf


What happens when i sign a public key with its private key pair? I am not a cryptologist, just a cryptography user, so not sure if this is safe.

I want to sign a public key with its private key pair. Is it dangerous to share this signature result along with public key? (For example can this be used to reverse engineer the private key) Or are there anything I should be concerned about?

Signing the public key is safe.

The general assumption is that the adversary is allowed to ask any message that he knows to be signed, and that operation must not leak information about the private key (or otherwise generate a signature for a message that was not signed by the legitimate signer).

In this model, the adversary knows the public key (it's assumed to be public, after all), and he can submit that as something to be signed.  Hence, if that signature leaks anything untoward, that shows that the signature algorithm is broken.

In practice, it can be seen not to matter; for any signature operation I've seen, you first hash the message to be signed (and perform the signature operation on the hash); this hashing operation would muck up any relation between the message and the public key, even if that were any issue.


Can someone randomly guess the key to AES 256 bit encryption? Is it possible that someone can randomly input a key to AES 256 bit encryption and it is correct? What are the chances of this happening? Is it even possible or not?

There are $2^{256}$ different AES keys, the chance that you hit the one right one on first try is thus $2^{-256}=\frac1{2^{256}}$.

To put this into perspective, here's a list of events that is roughly a billion times more likely to all happen (copied from Thomas Pornin's answer on Information Security SE):

  The computer spontaneously catches fire during the key generation process.
  Great Britain is wiped out by a falling asteroid during the very same second.
  A rogue gorilla escaped from a zoo enters your living room and mauls you.
  You win millions of dollars at the lottery three times in a row.

According to his answer, these events have roughly the chances of happening $2^{-45},2^{-50},2^{-60},2^{-71}$ each, which multiplies to $2^{-226}$ if you want all four to happen which is still roughly a billion times more likely than finding a 256-bit key on first try.

Note that this assumes that the key does indeed contain 256-bit of entropy, ie it can indeed take all the $2^{256}$ different values.


Proof of correctness of an ElGamal encryption given a specific public key Suppose Alice sends an ElGamal encryption of a value $v$ to Bob (using either the normal or exponential version of ElGamal). E.g. assuming publicly-known  $pk_{BOB} = h$ and a generator $g$, Alice sends $Enc(v,h) = (c_1,c_2) = (g^r, vh^r)$ to Bob. Or for the exponential version, she sends $Enc(v,h) = (c_1,c_2) = (g^r, g^vh^r)$.

Assuming Alice is honest, Bob will be able to correctly decrypt and recover $v$. However, Alice might not perform the encryption correctly (intentionally or not). For example she could use some other public key $h'$ to encrypt $v$, and then Bob would decrypt to some value $v'$. As an example, suppose that the values are supposed to be representing an ASCII character, then the decrypted value $v'$ would be "garbage".

Security model: There is a third-party authority, where Alice must show that she is encrypting legitimate values.

Is there a way to amend the scheme such that either Alice can prove in Zero Knowledge (without revealing $v$) that she encrypted using $h$, or alternatively, Bob to prove in ZK (without revealing his secret key $x$) that decryption failed?

As you suggested, the most natural approach would be to use a zero-knowledge proof - namely, we can let Alice prove to Bob that she knows the plaintext encrypted in the ciphertext she sent, with respect to the public key $h$. However, this has an immediate issue: what prevent Alice from honestly encrypting some garbage, unrelated to the actual (say) ASCII character she knows? She can intuitively always do that - she could even always encrypt another valid-looking ciphertext, like, another ASCII character.

So, what exactly is your security model? Who should Alice and Bob prove something to (clearly, Bob is not the one Alice wants to sent a proof to: he has the secret key, so he can check by himself whether he got garbage or a valid-looking plaintext)? Do you assume some kind of authority that Alice and Bob interact with, to whom we can either ask Alice to prove that she encrypted the right value (is this right value known to the authority?), or ask Bob to prove that he could decrypt the ciphertext to a valid-looking value?

In all situations, an appropriate zero-knowledge proof should do the trick. Which one exactly depends on the exact scenario and variant of ElGamal: for example, using exponential ElGamal, Alice should not only prove that the knows $(v,r)$ such that the ciphertext is of the form $(g^r, g^vh^r)$: to prove that this can be decrypted, she must further prove that $v$ is "small" (smaller than some bound $B$ which is a parameter of the system). But without knowing your exact scenario, it is not possible to give a more precise answer for now. As a general principle: do not ask "how can Alice and Bob to this" when you think that this is what they should do in your scenario - instead, explain exactly what your scenario is, and what security property you wish to achieve exactly. Then we can figure out a solution.


Sign MD5 hash with RSA I have to hash a message with MD5, digitally sign it, and then verify.

I have looked around, but I can't find a step-by-step example. I understand how RSA works when a message is given as number (not hashed).
But I am confused when I have to sign a hash.

For example: $n=33, d=7, e=3$.

I have a message: Hi
I compute the MD5 hash, $H(m)$, which is c1a5298f939e87e8f962a5edfc206918.
Now I have to sign it with $S = H(m)^d \bmod n.$

I get confused here: How can I perform this $H(m)^d$?  What will the result be after that?

Adjust the problem if at all possible.

The parameters envisioned in the question's

  For example: $n=33, d=7, e=3$

are terminally insecure, because $n$ is way too small: only 6-bit, when 512-bit is routinely broken my amateurs, 768-bit was experimentally broken in a public attack 8 years ago, 1024-bit is considered breakable by well-funded and capable adversaries, and 2048-bit the recommended baseline. See this. As an aside, publishing $d$ makes $n$ insecure.

As noted by Yehuda Lindell in comment, MD5 is very seriously broken, and using it is mostly unjustifiable.

For example, we know how to prepare different PDF files with the same MD5 but showing about any text desired (including chosen after the hash is frozen). With most common RSA signing schemes, this means a signature for a PDF chosen by the adversary (at least in its beginning) and telling something is also a signature for a PDF telling anything else, that the adversary can adjust as wanted (without practical limit for something decided before signature, subject to size limitation of the PDF for something decided after: the best current attacks require an additional 512 octets in the PDF per octet in the text displayed that must be chosen after signature, or a few times less with compression).

Use SHA-256 instead, if that's allowed.

When $n$ is at least 1-bit wider than the hash, we can hash then textbook-RSA-sign. That's considering the hash as an integer (per e.g. big-endian convention), computing the signature as $S=\big(H(M)\big)^d\bmod n$ , with verification by $S^e\bmod N\;\stackrel{?}{=}\;H(M)$. But even with large $n$ and an otherwise secure hash, this is vulnerable to the Desmedt-Odlyzko attack, if some messages legitimately signed can be chosen by the adversary. See this for the method and references.

The correct way is to use a much wider $n$; not publish either its factorization or $d$; use a better hash; and use proper RSA signature padding. A modern such scheme with a security argument, available from a library in most modern programming languages, is RSASSA-PSS of PKCS#1v2.

As noted here with references, coupled with MD5, RSASSA-PSS has been practically attacked in some contexts. But it can be modified to become quite secure in practice until a better break of MD5, or we consider somewhat brute-forcing MD5 for preimage (hard but not inconceivable). In RSASSA-PSS with MD5 we can replace $\operatorname{MD5}\big(\mathrm{padding_1}\|\operatorname{MD5}(M)\|\mathrm{salt}\big)$ with $\operatorname{MD5}(\mathrm{padding_1'}\|\mathrm{salt}\|M)$ or $\operatorname{MD5}\big(\mathrm{padding_1}\|\operatorname{MD5}(\mathrm{padding_1'}\|\mathrm{salt}\|M)\|\mathrm{salt}\big)$ (say, with $\mathrm{padding_1'}$ of 384-bit so that $M$ starts on a block boundary); the random unpredictable $\mathrm{salt}$ before the message $M$ mitigates the worst known weaknesses of MD5.

Addition: RSASSA-PKCS1-v1_5 suggested by this answer is slightly simpler, also easily available in libraries, and is secure as far as we know when used with a secure hash; but needs more transformation to be practically secure with MD5, and does not come with a security argument.


What is the difference between verifying the hash value (MAC) and security provided by authenticated encryption? I read this post Difference between MAC and Authenticated Encryption? but I'm still confusing the difference.

Seems like MAC can guarantee both integrity and authenticity (tbh I dont know the difference of integrity and authenticity).

What is the difference of MAC and AE?
Is AE using MAC?

Authenticated encryption also keeps the message secret.

Often, though not necessarily, authenticated encryption is built out of a composition of a cipher and a MAC—which, if you have to do yourself out of parts like AES-CTR and HMAC-SHA256, you should do as encrypt-then-MAC.

P.S.  There is no substantive difference between authenticity and integrity.  They both answer the question: Was this message sent by the party I expected to send it?


How can a stream cipher encrypt one bit at a time and still be secure? I was reading the differences between stream ciphers and block ciphers, noticing that block ciphers, encrypted blocks of 64 bits or so at a time. But, stream ciphers encrypt 1 bit at a time, and to me it seems it would be easily reverse-able? If the stream cipher's algorithm isn't changing then what stops the adversary from easily decrypting the ciphertext generated by the stream cipher?

TL;DR that bit relies on a large state and a lot of calculations that cannot be easily reversed, as you seem to believe.

A stream cipher creates a key stream that depends on the input key material (key seed). Although the stream cipher outputs one bit at a time (usually one byte at a time in implementations for obvious reasons) that doesn't mean that the internal state is of that size. The internal state will generally be larger than the security strength of the cipher.

Before even a single bit is output the state must be updated so that the output is indistinguishable from random to an adversary. Sometimes this is not entirely the case if the stream cipher is (partially) broken: the initial output stream of RC4 is distinguishable from random; it is required to first remove the head of the key stream to create a - relatively - secure cipher.

It should not be possible to calculate any significant part of the state or any part of the key by an adversary.

To use a stream cipher it is of high importance that the key / nonce combination for each encryption remains unique. If this isn't the case then a lot of information can be retrieved from the messages encrypted with the same combination.


Key derivation of public key without knowledge of private key I'm looking for a convenient way to share a set of public keys across multiple services, while preserving privacy by preventing these services from tying the identity of these public key sets together across services.

E.g. If I share my public key set with both Service 1 and Service 2, Service 1 and Service 2 should not be able to work together to discover that I have an account on both services.

Note that I don't want to simply generate a new set of key pairs for each service, as the private keys are distributed across multiple devices for security reasons (to avoid a single point of failure), and generating a new key pair on each of these devices every time I want to set up authentication for a new service would be inconvenient for the user.

While considering the best way to satisfy these requirements, I believe I've reduced the problem to the following:

  Given a public key Kpub and some other bit of information x, I want to derive a public key K'pub such that the holder of Kpriv, and only that keyholder, given x, can find K'priv, and such that it is hard to find Kpub given K'pub and x.

So basically, it seems I want a key derivation function that can derive a public key, but which can't derive the corresponding private key without knowing some additional, secret information.

Is this possible? Is there any existing solution which satisfies the above requirements? Or am I breaking new ground here?

For public key encryption, there's an easy solution using a variant of Elgamal. (If you want to do authentication, you can use standard algorithms. If you specifically want signature schemes, say so.)

Recall that the security of Elgamal is equivalent to DDH, which is talking about indistinguishability of certain subgroups, namely given a cyclic group $G$, a (arbitrary) generator $g$ and an element of the group $y$, decide if the pair $(x,z)$ lies in the subgroup of $G \times G$ generated by the pair $(g, y)$.

We can phrase Elgamal as follows: To encrypt using the public key $(g,y)$, choose a random number $r$, compute $x=g^r$, $z=y^r$ and $w = zm$. The ciphertext is the pair $(x,w)$.

Deciding if $(x,w)$ is an encryption of $m$ is equivalent to deciding if $(x,w/m)$ lies in the subgroup.

Now observe that if $(g,y)$ is a public key, then $(g',y') = (g^b,y^b)$ is just as good a key.

Finally, to decide if $(g',y')$ and $(g'', y'')$ represent the same public key is equivalent to deciding if one lies in the subgroup generated by the other.

Most tricks you would use to improve the security of Elgamal would work for this variant as well, even with randomized keys.

With a bit of thinking, I am sure you can come up with lots of variations of this general idea.


NTRU: Possible misunderstending of division and euclidean algorithm for polynomials Please consider this answer before reading

I am trying to find GCD of two polynomials, but I have some troubles understanding division and euclidean algorithms:

1) In description of division algorithm it is stated that polynomial b must be of degree N-1, but when finding the inverse of polynomial we must pass $x^N - 1$ as b

2) If previous condition is ignored, division algorithm still won't work properly because of the next condition:

deg r >= N

if N is taken from parameter set, it doesn't make sence, because NTRU operates with polynomials of degree less than N.

So, consider next scenario:

$N = 11$

$a = -1 + x + x^2 + -x^4 + x^6 + x^9 + -x^{10}$

$b = x^N - 1 = x^{11} - 1$

Division algorithm would return quontient = 0 and remainder = a, since degree of a is less than N.

And the result will be the same regardless of the value of a.

What am I missing? I doubt that such basic algorithm could be documented wrong, so please help me understand what did I get wrong.

I am trying to find GCD of two polynomials

If you are trying to find the GCD, it turns out that trying to perform divisions is the wrong way (the referenced question was talking about computing inverses - a rather different problem).

The first thing you need to ask is "what ring or field are the polynomials defined over?".  If it is, in fact, a field, then it is easy; you can follow this procedure:

GCD( Polynomial P, Polynomial Q ) {
    for (;;) {
        if (deg(P) < deg(Q))
            swap P, Q
        deg_p = deg(P);
        lead_p = P[deg_p];   /* The leading coefficient of P */
        deg_q = deg(Q)'
        lead_q = Q[deg_q];   /* The leading coefficient of Q */
        X := (x ** (deg_p - deg_q); /* A polynomial with the coefficient */
                             /* deg_p-deg_q set */
        (P, Q) := (Q, lead_q*P - lead_p*X*Q);
        if (Q == 0) {        /* If Q is the all-zero polynomial */
            return P;
        }
 }

This function decreases deg(P)+deg(Q) each iteration, and so it is guaranteed to terminate.  In addition, all the operations can be done fairly easily (the computation of X*Q can be done by shifting all the coefficients of Q leftward deg_p-deg_q places).

And, if the polynomial is defined over a field, it can be shown that this always returns a correct value.

On the other hand, sometimes NTRU works in polynomials over the field $\mathbb{Z}_3$, and sometimes in polynomials over the ring $\mathbb{Z}_q$, for $q = 2048$ or $4096$; this ring has noninvertible elements, with muck things up a bit.

Now, if you are working over $\mathbb{Z}_q[X]$, I believe that the above algorithm will return something related to the actual GCD (however, it's not guaranteed that $P$ and $Q$ will both be multiples of the result); depending on what you're doing with the GCD, it might be good enough...


Vigenère cipher with sha512 and a little foresight turns to one-time pad. How safe can be? I'm doing some exercises and of course I have read about the weaknesses of Vigenère cipher because it repeats the key. But what if I use a different hash every time? The hash of the "key + an increasing number".
In this example I encode a plaintext just with a sum of every single char (text[0] + pswhash[0] and so on). blocksize is 128 because I use sha512.

    f = open(filename)
    f2 = open(filename+'.encoded','w')
    x = 0
    while True:
        string = f.read(blocksize)
        if not string:
            break
        pswhash = sha512((psw+str(x)).encode('utf-8')).hexdigest()
        f2.write(encode(string, pswhash))
        x+=1
    f.close
    f2.close
    print("File encoded.")

how safe this could be?
Is this a real one-time pad?

Is this a real one-time pad?

No, it's not a one time pad; as the keystream is not generated from a truly random process, hence you don't get the informational security guarrantees that you'd get from a true OTP.

Instead, it's a stream cipher; in particular, counter mode (with SHA512 is the "block cipher"; in counter mode, the block cipher needn't be invertable).

It's actually decent at providing privacy (albeit not very fast at it); however, it still would need some integrity protection (unless you're absolutely positive that an attacker cannot alter the ciphertext)


What are the potential security impacts of using CRAM-MD5 for Emails, when not using an SSL connection? Background: My current server-provider tells me it's no problem to store the passwords in plain-text in the database, saying he has to do so because they use CRAM-MD5 for email authentication. But something tells me that storing password in a database in plain text might not be the only security issue that comes up here and I'm not even sure if CRAM-MD5 can still be considered as "safe" from a cryptographic point of view. After all, I sure don't want to use something insecure for email traffic.

Whatever feedback you can give me - from a cryptographic point of view - about "using CRAM-MD5 for authentication while talking to an email server without the use of an SSL connection" will be highly appreciated. Thanks in advance.

edit : For an InfoSec point of view, check https://security.stackexchange.com/questions/36117/how-secure-is-using-cram-md5-for-email-authentication-when-not-using-an-ssl-con

CRAM-MD5 is a protocol to demonstrate knowledge of a password. In the context of email, it is sometime used by an email client to authenticate to a POP, IMAP, or/and SMTP server. Basically, the password is used as the key of HMAC-MD5 in a challenge-response protocol.

Among positive things there are to say about CRAM-MD5:

The password is not exchanged in clear.
The protocol is not vulnerable to replay.
HMAC-MD5 stands strong (even though MD5 is broken as a collision-resistant hash); thus if the password was unguessable, CRAM-MD5 would provide strong protection against logging by an adversary using passive wiretapping.
The password can be long and contain arbitrary characters as far as the protocol is concerned, making the above if at least feasible.
It is conceivable to use an irreversible transformation of the password, rather than the password itself, to perform the protocol (by keeping the output of the first round of each of the two MD5 hashes in HMAC-MD5); thus a server using  CRAM-MD5 does not really need to keep the password in clear, nor any mean allowing direct derivation of the password (the excuse reportedly given for "storing password in a database in plain text" likely reflects practice, but is wrong from a strictly cryptographic standpoint).
MD5 Rainbow Tables can not help to crack the password from intercepts by passive wiretapping: the challenge defeats that.
Implementation is simple.

On the negative side:

CRAM-MD5 does not in practice meet its primary objective of keeping the password secret from a passive eavesdropper (e.g. using WireShark), because testing a particular password is fast (it requires a single HMAC-MD5, that is typically 4 MD5 rounds), and passwords chosen by anyone except a few paranoids security-conscious persons are guessable by a password cracker. For example this beast reportedly performs 180 billion MD5 per second, that's perhaps 235 passwords tested per second, translating to less than 5 minutes on average to crack the strong (44-bit) variant suggested by the obligatory XKCD reference; the weak (28-bit) variant, which is already very much above average password practice, is vulnerable to a script kiddie using John-the-Ripper.
CRAM-MD5 authenticates one party to the other, not the other way around; in email practice, the client does not ascertain to which server it connects to receive or send email.
Using CRAM-MD5 does not protect the confidentiality or integrity of the data exchanged after login: email can be read by a passive eavesdropper, an active adversary can insert commands in an existing session.

In summary: CRAM-MD5 provides strong protection against disclosure of an exceptionally strong password by way of wiretapping, symbolic protection for real-life passwords, and almost no other security functionality. In the context of email service provided by an ISP, some will consider the issue moot: email exchanged in this way (without end-to-end security as provided by e.g. GPG) is insecure in many other ways.


How does TLS generate the shared secret? From many readings, I got to know that TLS generates master shared secrets using pre-master keys and uses the DH algorithm to generate the shared secret/Master secret.

What values during the hello messages act as

1. P - Prime number

2. G - Generator

3. Secret primes owned by each parties
?

Why does it need a client-server random number along with the pre-master secret to generate the master secret as DH requires only p, q and (a,b) are generated on each side?

Selection of the Diffie-Hellman parameters

If you are asking about the TLS cipher suites that use a Diffie-Hellman exchange (basically the ones containing "DH" or "DHE"), it depends on whether static or ephemeral Diffie-Hellman certificates are used.

The ephemeral cipher suites (DHE_DSS, DHE_RSA, DHE_anon and the various elliptic counterparts) transmit the generator, the prime modulus and the public value in the server and client key exchange messages.
The static cipher suites using Diffie-Hellman (DH_DSS, DH_RSA) use the (fixed) parameters embedded in the server certificate. If a client certificate is used, the parameters have to match the server's.

Not all cipher suites use a Diffie-Hellman exchange, though; in the (widely used) RSA_* cipher suites, the client sipmly selects a random premaster secret and encrypts it using the server's public RSA key.

Purpose of the client/server random values

The client and server randomness serves to avoid ever using the same emaster secret twice; for example, when a static Diffie-Hellman ciphersuite is used with a client certificate, the server's and the client's Y value don't change between sessions. This is done by securely hashing the premaster secret (which might or might not be equal for different sessions) and the client and server random values (which are required to be different for different sessions).

Reusing the master secret could allow replay attacks or cause the symmetric cipher to reveal information about the payload data.


Making my steganography code more hard to detect and crack I'm doing a college project about digital image steganography on MATLAB. So far i've been able to get the help i needed from cool guys on stackoverflow but i now need to make my algorithm more hard to detect. This is what i have so far:

My main function reads 4 grayscale RGB 24-bit images and one RGB 24-bit image to encode the four images into. The first two are supposed to be blueprints and the other two are images containing only text (in large size). All the images are of the same size.
Before encoding, the pixel positions of each grayscale image are randomly shuffled by (eg: the 1st pixel becomes the 24th pixel, the second pixel becomes the 300th pixel) this is done by generating a random permutation of numbers that represent the new pixel positions using a seed. This is done to make the code harder to crack to an outsider and the seed will act as a password that would be needed at the receiving end to recover the images.
The first shuffled grayscale image is encoded into the R plane of the RGB image, and the second shuffled image is encoded into the G plane. This is done by testing each pixel in each image eg: pixel in position (x,y): if black-->make lsb of the pixel in position (x,y) in the chosen plane =0. if white-->make lsb of the pixel=1.
The other two shuffled grayscale images that contain text only are combined to form one grayscale image by choosing a chessboard-like patter of pixel positions of the first and the complement pattern of the second. And the resulting grayscale image is encoded into the B plane of the RGB image same as done to the first two. And this is done in that way because you don't need much details to be able to read a text but you do need details to be able to make out a blueprint, the recovered text grayscales will be a little distorted but they'll be readable. Now the process encoding is done and S/N ratio is calculated for the resulting encoded RGB image to measure the difference from the original RGB image and in result the difference is not noticeable to the untrained eye.
Recovering the grayscale images is done by reversing the operations done to the encoded RGB image in reverse order.

So there you go. I'm now looking for a way to make my code way more harder to detect and crack. Maybe using Wavelet Transform? I've been reading on that for a while but i don't now how that would work for my project.

Some general advice about steganography:

Much like in the physical world, the smaller what you want to hide, the easiest that goal is. Thus you may want to compress the payload(s), and treat the result as the new, smaller payload consisting of arbitrary bits. Because your payload consists of images, some lossy scheme such as JPEG or JPEG 2000 might be used to get excellent compression. Also, the bigger the apparent vector message is, the easier hiding into it is (all other things being equal, like the format of that vector message).
Shuffling bits (second bullet in the question) is a primitive technique to try to make data unintelligible. In order to protect the confidentiality of the payload, use encryption. If done correctly, that makes it demonstrably hopeless to recover the original payload from the message (as opposed to detecting the presence of the payload), for one not holding the decryption key. One simple form of encryption is generating a pseudo-random stream of data from a key, and exclusive-ORing that with the plaintext (possibly compressed as above), with the caveat that the same portion of the stream must never be reused (see e.g. AES-CTR). Using authenticated encryption (e.g. AES-GCM) can in addition make it hopeless for an adversary to induce an undetected alteration of the hidden message.
Now comes the hard part: hiding the modified payload into a vector message (here, passable as an image) in a way such that presence of the payload won't be discovered. Stenography schemes attempting that could be rated on three coarse levels:

Undetectability depends on the adversary (interceptor trying to prove there is a message hidden) not knowing the scheme itself. An example would be sending the payload in a portion of a vector file that most normal programs skip, like some comment field, or trailer. Such schemes fail as soon as known.
Undetectability  relies on the adversary not noticing some minute characteristics of the vector data. An example would be encoding the payload in the low bit of the bytes coding the RGB values in the vector, leaving all the rest untouched. Such schemes often fail (for example if the pristine vector is an uncompressed computer screen capture at a moment when a GUI is displaying areas of exactly uniform color, there will be extreme redundancy in the low-oder bits, and the scheme described will remove that, enabling detection, perhaps even with a sharp eye).
Undetectability  (to some quantifiable degree) is demonstrable under some assumptions, typically that a key is unknown to the adversary, and most critically assuming a model of the data in the vector (sorry, my only simple example is when that model is: true random data). In a real world, such schemes still can fail because the adversary has some better model (e.g. taking into account some details about how a particular camera allegedly the source of the vector image generates its files, or some characteristics of its sensor or lens).

In addition, some steganography schemes have another, even harder goal: prevent removal of the hidden payload without drastically altering the perceived quality of the vector (or at least, by casual transformation leaving the vector mostly undisturbed, e.g. saving an image as highly-compressed JPEG, or recoding digital audio as MP3). That would be necessary in some DRM schemes. Sometime this is called (digital) watermarking, but the analogy with the eponymous printing paper-manufacturing technique is reversed: in DRM, the designer's hope is that an unauthorized copy holds the watermark/payload, when on a banknote the hope is that the watermark is not copied. The three coarse levels above hold with some alterations.


What do I use as the encryption key and initialization vector in AES cfb128 I'm writing a program that can encrypt a file using AES cfb128 (using Openssl and C++).

The scenario of the program is this:

Person A visits computer, encrypts a file they make, takes away a key (on USB stick?)
Person B visits computer and is unable to decrypt encrypted file
Person A comes back and decrypts the file using their key

My question is I have an encryption key and initialization vector that I must set for the AES encryption. I plan on randomly generating numbers for one and using a hardware ID for the other. Also the person could choose to encrypt multiple files.

So how would I do this?
Can I make the encryption key the hardwareID and the init vector a sequence of random bits?

If the same hardwareID and init vector are used to encrypt multiple files per machine, is this unsecure given that an attacker will not have the init vector but may have the encryption key? Should the encryption key be the random bit instead and the hardware key be the init vector?

Or should both the encryption key and init vector be random and unknown to the attacker? And if so, is it secure to encrypt multiple files using the same 2 unknown keys?

You can use your HardwareID as basis for the encryption key. If the ID provides enough entropy it'll work. However, if anyone can somehow obtain the ID (which might be quite easy to do) one can decrypt the file.

For CFB-Mode the IV must indeed be unpredictable (but need not be secret), so random is just fine, but DO NOT REUSE AN IV.

Encryption large amounts of data with the same key and different IVs is just fine and no problem at all.

However, I want to propose some improvements for the security level.

Don't use CFB-Mode but EAX/CCM/GCM-Mode, as they are authenticated and hence you've authentication "for free" without any further worries.
As replacement for the Hardware-ID based Key I'd suggest either storing the key (plain - not recommended) on the USB-Stick, or only use a password (+ scrypt) or store the key encrypted (AES-GCM+scrypt) on a stick.
You might want to consider generating a key for each file you encrypt and storing this key (+IV) as a "header" for the encrypted file. The header would be decrypted using the secret key (from USB / from password / from USB+password)


Will two KEK's provide the same KCV or should these be different? If you were to have an MDKac key that you need to send to two parties you would need to encrypt this key with two different KEK/ZCMKs.

Will the KCV of the MDKac under KEK1 provide the same KCV as MDKac under KEK2?

This is using DES3 - ECB encryption.

The KCV generally consists of a single encryption of a block of all zeros using the key itself - and then taking a number of leftmost bytes, usually displayed as hexadecimals.

That means that the KCV doesn't change. The whole idea of a KCV is that it is deterministic; if it would be different for an identical key then it would lose its function.

Note that I didn't see any KCV calculation in the EMV specifications. Other methods may use e.g. a hash over the key value - but this isn't common. So in the end it depends on how it is specified outside of the EMV standards - if at all. However, the KCV should only be determined by the key value.

For 3DES keys the usual encryption of a zero block makes more sense, as some implementations ignore the parity bits, while others do not. This means that a functionally identical key could lead to different KCV values if hashing would be used. The KCV of 3DES keys that only differ with regard to the parity bits will be identical.

However, the use of a zero valued block encryption is dangerous as well: if a zero block encrypt is ever used in the protocol then the KCV will leak information about the value (e.g. when CTR mode encryption is used with a zero IV).


Zero Knowledge - Who is greater? I just encountered the term "zero-knowledge" and wanted to know more about it.

I understood that there is a zero knowledge protocol between two parties to determine whether $x$ is greater than, equal to, or smaller than $y$, given that one side knows $x$ and the other knows $y$, but I couldn't find anything about it.

I searched in google, but couldn't find an answer (maybe I'm just bad at searching).

Hopefully you guys can give me a simple answer.

If you just encountered the term, I would suggest that you get used first to the intuition of how it can be achieved. ZK using graph isomorphism is great as an introductory example (although impractical for more cases).

That said, what you are looking for is known as [Yao's] Millionaire's Problem. The description of the problem talks about two millionaires who want to find out who is the richest of them without disclosing their actual wealth.

I believe that, for your problem, it is not zero knowledge what you're looking for. Look instead for multiparty computation, but beware: this is a huge research area. In MPC, you want multiple entities to interact, but you know that some of them can cheat in very different ways. The literature is strongly associated with e-voting. You will meet there with Zero Knowledge, but also with homomorphic encryption, commitments and other concepts. You'll be specially interested in oblivious transfer: Bob knows a function $F$. You, Alice, want to get the value of $F(n)$ without telling Bob the value of $n$.

There are different ways to approach the problem, each with a set of trade-offs. You can start at the Wikipedia page about the problem and come back later if (when) you have more questions. It all depends on the capabilities of your adversary. After all, you could just ask the two millionaire's independently in separate rooms and tell them who is the richest without disclosing their values, without using any crypto!


Is EC integrated encryption scheme used in practice? I know ECDSA and ECDH are used a lot but what about the ECIES? Is it used or specified as an option in any protocol?

Yes, ECIES is used in practice. That's the simplest way (thus arguably the best) to establish a key or/and encipher using Elliptic Curve Cryptography in contexts including unidirectional data transfer, or data-at-rest like backup with encryption under public key.

As an illustration, it is often listed in the Other algorithms section of FIPS-140-validated cryptographic devices; I count like 28 occurrences.

ECIES is in the de-facto standard SEC 1, IEEE Std 1363a-2004, and ANSI X9.63-2011. It is used e.g. in Intelligent Transport Systems as specified by ETSI TS 103 097. The similar ECIES-KEM is in ISO/IEC 18033-2:2006 following a well-documented proposal by Victor Shoup.