The example of Wikipedia on steganography doesn't work I was reading some stuff on steganography.

There is an example on the wikipedia page :

However, I tried many software to get the hidden image, but no one worked. Is there anything wrong about that?

I tried OpenStego (Windows), SecretLayer (Windows) and VSL (Linux).

The Wikipedia example is something you probably would not really want to do, but does demonstrate just how much information you can add to a non-lossy image format without it being obvious to the human eye.

Importantly, the technique used in Wikipedia only works for hiding a lower-quality image of the same dimensions as the container in the low bits of the main image. More general steganography programs will attempt to store more arbitrary messages, and will use different storage strategies. It is unlikely that any would support the example approach for "hidden-image-in-image" shown in Wikipedia. Instead you can verify the Wikipedia example using a short program in e.g. Matlab, to mask out and re-normalise the low bits.

In pseudocode:

tree_image_pixels <- load_image( 'example.png' )
cat_pixels <- ( tree_image_pixels & 3 ) * 85
save_image_from_pixels( 'cat.png', cat_pixels )

The value of 85 is so that maximum pixel value is 3 * 85 = 255, using the full colour range. Lower values also work, but produce a less bright image.


Differential privacy per record Generally, differential privacy adds noise to a query result, such as a sum or an average, in an interactive way.

Is there any way for implementing differential privacy such that noise will be added in an non-interactive way, record by record ?

Thanks in advance

Yes, the classic example is Randomized response: when doing a survey with a yes/no question that is sensitive (for example, "are you currently an undocumented immigrant living in the US"), you ask each respondent to flip a coin first. If the coin hits tails, you tell them to answer randomly (by flipping a second coin), otherwise, ask them to answer honestly. Then, you remove 25% of the "yes" answers to take into account people who answered randomly, and you get a noisy total count that has differential privacy.

It corresponds to this idea of "adding noise to each record" instead of adding noise to the end-result (in this case, the total number of illegal immigrants). The main advantage is that you don't need a trusted third-party that has all the "real" data. The main disadvantage is that the result is more noisy for the same privacy property.

You can compute more complex statistics with this randomized response idea. For example, things like "which websites are most commonly used as home pages in Google Chrome" are computed using RAPPOR. The method is described in their paper.

More recently, Vincent Bindschaedler, Reza Shokri, and Carl Gunter have detailed a generic method to generate a synthetic dataset from real data, with differential privacy guarantees. It's not exactly "adding noise record by record", but it's similar to this idea of releasing not simply noisy statistics, but a full dataset that can be used for data mining.


Why does the crypto_box functionality in NaCl library exposes the nonce to the programmer The idea of crypto_box API in NaCl library is to shield the programmer away from the technical details and provide easy to use functions for encrypting and encrypting messages.

Given what I've just written, I do not understand why the idea of nonce is exposed in this API. Explaining what nonce is and how to use it takes up a significant portion of the documentation and it is quite possible to get this wrong. Wouldn't it be better to just generate a random bytestring under the covers?

The article on NaCl by its authors touches this subject. I'll quote here the relevant bit:

Nonces. The crypto_box API leaves nonce generation to the caller. This
is not meant to suggest that nonce generation is not part of the
cryptographer’s job; on the contrary, we believe that cryptographers
should take responsibility not just for nonces but also for other
security aspects of high-level network protocols. The exposure of
nonces simply reflects the fact that nonces are integrated into
high-level protocols in different ways.
It might seem simplest to
always generate a random 24-byte nonce n, and to transmit this nonce
as part of the authenticated ciphertext; 24-byte random strings have
negligible chance of colliding. If ciphertexts are long then one can
tolerate the costs of generating this randomness and of expanding each
ciphertext by 24 bytes. However, random nonces do nothing to stop the
simplest type of forgery, namely a replay. One standard strategy to
prevent replays is to include an increasing number in each packet and
to reject any packet whose number is not larger than the number in the
last verified packet; using these sequence numbers as nonces is
simpler than giving each packet a number and a random nonce. On the
other hand, choosing public nonces as sequence numbers means giving
away traffic information that would otherwise be somewhat more
expensive for an attacker to collect. Several different solutions
appear in the literature; constraints on nonce generation are often
tied directly to questions of the security and privacy that users
expect.
Current applications of NaCl, such as DNSCurve and CurveCP,
have different requirements regarding nonces, replays, forward
secrecy, and many other security issues at a higher level than the
crypto_box API. A nonceless API would require higher-level
complications in all of these applications, and would not simplify
their security analysis.


Are one time pads still secure when using randomly generated words as the pad? I was researching the US military's DIANA one-time-pad system and came across the following quote purportedly from a former US Special Forces soldier:

  Special Forces were one of (if not the only) units in Vietnam to
  utilize Morse code on a regular basis. We used a method of encryption
  called the Diana Cryptosystem.

  The basis of these one-time pads, is that there were only two matching
  pads in existence, and they would only be used one time. They were
  booklets that contained randomly generated groups of 5-letter words,
  30 words to a page. The person sending a message would first write the
  letters to the message, over these random groups of words. Included in
  the front of each one-time pad was a one-page encryption table. If I
  wanted to send the letter P, and the letter under the P was an A, then
  I would send a K. The person listening on the frequency at the other
  end, would have the other matching pad. They would write the letter
  they received (a K) over the letter in their one-time pad (an A), and
  decipher it based on the table, yielding the original letter P.

(source: https://dodona.ugent.be/en/exercises/2088793301/)

Wouldn't the use of random words as reported by the soldier rather than groups of random letters diminish the security of the system, as the letters in 5 letter English words are not randomly positioned?

I am aware that "secure" in this context--messages between Special Forces camps during wartime--may just mean keeping messages secure long enough that they are no longer useful even if broken.

Do those look like English words to you?

WHTVI AUCFU RETFK OMSAL
MYMNE ZIEGP UKVTF WZHOK

(Quoted from the page.)

When they say ‘5-letter words’, they don't mean words chosen from an English dictionary.  They mean that they rolled a d26 five times independently and strung the resulting letters together, with spaces between every five letters and line breaks between every four ‘words’ for legibility.  This method is just as secure as using a d2 (i.e., flipping a coin) to choose the bits of a binary one-time pad; it just uses a different alphabet.


Should I be using RSA to Encrypt and ECC to Sign? I want to combine RSA and ECC. First of all, a particular file is encrypted with the RSA algorithm and then that encrypted data is again encrypted with ECC algorithm.

However, can I use RSA to encrypt and ECC to sign, or do I have it backwards?

Both RSA and ECC can be used to encrypt/decrypt or sign/verify data. Neither is efficient when it comes to doing either (for larger amounts of data). That's why in general a symmetric cipher such as AES (in a specific mode) is used to encrypt/decrypt the bulk of the data. A secure hash such as SHA-512 is used to perform a one-way compression when doing a sign / verify method. A combined asymmetric algorithm and symmetric algorithm is called a hybrid cryptosystem.

The most common/recent methods would be to use RSA-OAEP and AES-GCM for encryption and RSA-PSS with SHA-512 for signing. For ECC you can do EC-IES with AES-GCM for encryption and ECDSA with SHA-512 for signing. These can be mixed any way you want. Other variants are possible of course.

Generally you would sign the message first and then encrypt it. Otherwise somebody could strip the signature from the file and sign it himself.  You will need a minimum of two key pairs of course, one for the sender and one of the receiver. The AES keys should be generated specifically for encrypting the single message.


Can you help me understand this pseudo random generator example? I'm new to crypto. I'm learning according to the book "Introduction to Modern Cryptography". I'm having troubles with understanding of PRG and how to prove if some function is PRG or not.

I'm trying to solve this simple example:

  G(x1,x2...xn) = x1,x2,...xn, x1 xor x2 xor x3... xor xn

  Is G a PRG?

Well, according to the book I need to check if

  $$|Pr[D(r)=1]-Pr[D(G(s))=1| <= negl(n)$$

  where $r$ is chosen uniformly at random from $\{0,1\}^|G(s)|$
  the seed $s$ is chosen uniformly at random from $\{0, l\}^n$,
  and the probabilities are taken over the random coins used by $D$ and the choice of $r$ and $s$.

but I don't know how to calculate $D(r)$ and $D(G(s))$... I'm feeling like I'm missing something here. Can you help me grasp what I’m missing?

Assuming your question is whether $G(x_1,x_2,...,x_n) = x_1,x_2,...,x_n, x_1 \oplus x_2 \oplus x_3 ... \oplus x_n$
is a PRG.

$D$ is some fixed probabilistic polynomial time distinguisher.

So to prove that $G(.)$ is a PRG, you need so show that for all such distinguishers, $D(G(.))$ cannot be distinguished from $D(.)$.

e.g.
$\big| Pr[D(G(s))=1] - Pr[D(s)=1] \big| \leqslant negl(n)$ where $s \leftarrow \{0,1\}^n $

Conversely to show $G(.)$ is not a PRG you simply need to identify a distinguisher $D(.)$ such that the above equation does not hold.

In this case, $G(.)$ looks like it could be distinguished from a random distribution, since the output is just the input, followed by the xor of the inputs.

i.e. $D(.)$ is some function which outputs $1$ if the final bit of output is the xor of all of the previous bits. This would be true half of the time applied to a random distribution, but would always be true for $G(.)$. This would mean that $\big| Pr[D(G(s))=1] - Pr[D(s)=1] \big| = \big| 1 - 0.5 \big| = 0.5$

Since a half is not negligible we can say that $G(.)$ is not a PRG.


CAs are pre-loaded on the system, but how is it able to get intermediate certs? I have the following X509 certificate:

-----BEGIN CERTIFICATE-----
MIIG3TCCBcWgAwIBAgIQAtB7LVsRCmgbyWiiw7Sf5jANBgkqhkiG9w0BAQsFADBN
MQswCQYDVQQGEwJVUzEVMBMGA1UEChMMRGlnaUNlcnQgSW5jMScwJQYDVQQDEx5E
aWdpQ2VydCBTSEEyIFNlY3VyZSBTZXJ2ZXIgQ0EwHhcNMTcwOTEzMDAwMDAwWhcN
MTkwOTEzMTIwMDAwWjBqMQswCQYDVQQGEwJVUzETMBEGA1UECBMKV2FzaGluZ3Rv
bjEQMA4GA1UEBxMHUmVkbW9uZDEeMBwGA1UEChMVTWljcm9zb2Z0IENvcnBvcmF0
aW9uMRQwEgYDVQQDEwtvdXRsb29rLmNvbTCCASIwDQYJKoZIhvcNAQEBBQADggEP
ADCCAQoCggEBAIz2tovvgBmK4sOHgpyzCdtXrI0XOujctf6LHMj16wzUnMEatioS
tH0Pz0dKkCr/0yd9qtXbGhD1o6WhFsd7k651K9MZ98+uQ29SzTIAl6y1gkaBbp4h
MFXcE5EpRNHHmK8t2OR7hzmrvvNr6OTYv7BhVCw9pSrQqEFNno0K2TQRhAD9uzrL
OY+rBBVedCXWXH7uhZoZ6joUU7CEA5pPMzKPL1ro+Eorc8vt5FYOC+oAT587+b1M
z+jbZVQlq0qaMkBKRtUIII78MYY0n8DopGqHyzwqWoGySHJNC8256q+MwsZQvvQ3
vmy/rf61h2sg1tU0s7O88Yufxp0LSaMMzZcCAwEAAaOCA5owggOWMB8GA1UdIwQY
MBaAFA+AYRyCMWHVLyjnjUY4tCzhxtniMB0GA1UdDgQWBBT7hLoZ/03rqwcslIc2
0k0z2R+vNTCCAdwGA1UdEQSCAdMwggHPggtvdXRsb29rLmNvbYIWKi5jbG8uZm9v
dHByaW50ZG5zLmNvbYIWKi5ucmIuZm9vdHByaW50ZG5zLmNvbYIgYXR0YWNobWVu
dC5vdXRsb29rLm9mZmljZXBwZS5uZXSCG2F0dGFjaG1lbnQub3V0bG9vay5saXZl
Lm5ldIIdYXR0YWNobWVudC5vdXRsb29rLm9mZmljZS5uZXSCHWNjcy5sb2dpbi5t
aWNyb3NvZnRvbmxpbmUuY29tgiFjY3Mtc2RmLmxvZ2luLm1pY3Jvc29mdG9ubGlu
ZS5jb22CC2hvdG1haWwuY29tgg0qLmhvdG1haWwuY29tggoqLmxpdmUuY29tghZt
YWlsLnNlcnZpY2VzLmxpdmUuY29tgg1vZmZpY2UzNjUuY29tgg8qLm9mZmljZTM2
NS5jb22CFyoub3V0bG9vay5vZmZpY2UzNjUuY29tgg0qLm91dGxvb2suY29tghYq
LmludGVybmFsLm91dGxvb2suY29tggwqLm9mZmljZS5jb22CEm91dGxvb2sub2Zm
aWNlLmNvbYIUc3Vic3RyYXRlLm9mZmljZS5jb22CGHN1YnN0cmF0ZS1zZGYub2Zm
aWNlLmNvbTAOBgNVHQ8BAf8EBAMCBaAwHQYDVR0lBBYwFAYIKwYBBQUHAwEGCCsG
AQUFBwMCMGsGA1UdHwRkMGIwL6AtoCuGKWh0dHA6Ly9jcmwzLmRpZ2ljZXJ0LmNv
bS9zc2NhLXNoYTItZzEuY3JsMC+gLaArhilodHRwOi8vY3JsNC5kaWdpY2VydC5j
b20vc3NjYS1zaGEyLWcxLmNybDBMBgNVHSAERTBDMDcGCWCGSAGG/WwBATAqMCgG
CCsGAQUFBwIBFhxodHRwczovL3d3dy5kaWdpY2VydC5jb20vQ1BTMAgGBmeBDAEC
AjB8BggrBgEFBQcBAQRwMG4wJAYIKwYBBQUHMAGGGGh0dHA6Ly9vY3NwLmRpZ2lj
ZXJ0LmNvbTBGBggrBgEFBQcwAoY6aHR0cDovL2NhY2VydHMuZGlnaWNlcnQuY29t
L0RpZ2lDZXJ0U0hBMlNlY3VyZVNlcnZlckNBLmNydDAMBgNVHRMBAf8EAjAAMA0G
CSqGSIb3DQEBCwUAA4IBAQA3zjN7I6jTeL+08nhG5eAY0q4pLY40bCQHqONBLSI3
uRmQFUfrQOPYBqLC1QU+J2Z2HcX7YiqE3WAR3ODS9g2BAVXkKOQKNBnr2hKwueOz
qPwyvTyzcIQYUw+SrTX+bfJwYMTmZvtP9S7/pB1jPhrV7YGsD55AI9bGa9cmH7VQ
OiL1p5Qovg5KRsldoZeC04OF/UQIR1fv47VGptsHHGypvSo1JinJFQMXylqLIrUW
lV66p3Ui7pFABGc/Lv7nOyANXfLugBO8MyzydGA4NRGiS2MbGpswPCg154pWausU
M0qaEPsM2o3CSTfxSJQQIyEe+izV3UQqYSyWkNqCCFPN
-----END CERTIFICATE-----

When I open it up in Windows I see a path from the cert to the CA with one intermediate cert:

So the CA is pre-loaded on the system but how is it able to get the intermediate cert?

An X.509 certificate may contain extensions, one of them called Authority Information Access, which contains "pointers" to the certificate for the (intermediate) CA that issued it. In your case, the AIA extension is present and contains the following URL:

http://cacerts.digicert.com/DigiCertSHA2SecureServerCA.crt

Windows simply sends an HTTP GET request to that URL, and tries to interpret what it obtains as an encoded certificate. Which is the case. Windows can then verify that the intermediate certificate is indeed a valid issuer for your certificate (the signature is valid, the subject/issuer names match, the validity dates are correct, and so on...). Once it has obtained the intermediate CA cert, it repeats the process, until it hits one of the preloaded root CA.

The certificate viewer of Windows can show you such URL (see the "details" pane). Alternatively, you can decode the certificate structure to see for yourself the gory details (personally, I use my own tool called DDer).

Amusingly, this feature can be used to make, in some circumstances, a remote machine issue HTTP GET requests at URL of your choosing (but only GET, not POST, and only HTTP, not HTTPS; and you don't get to see what is obtained). For instance, if there is a Windows-based SSL server that asks for client certificates, then a malicious client may submit a phony certificate that makes the server issue on HTTP GET at a URL that will be interpreted by the server itself (and thus may contain "internal" IP addresses, or even "localhost").


Understanding public key cryptography example Frankly, I wasn't sure whether this belongs in crypto.stackexchange.com or here, so forgive me. I've been going through a book where in one of the chapters the author tries to illustrate public key cryptography by imagining a "four-step business plan for Murder Incorporated" in a "world of strong privacy".

Arrange for mystery billboards on major highways. Each contains a
single long number and the message “write this down.” Display ads with
the same message appear in major newspapers.

Put a full-page ad in the New York Times, apparently written in
gibberish.

Arrange a multiple assassination with high-profile targets, such as
film stars or major sports figures – perhaps a bomb at the Academy
Awards.

Send a message to all major media outlets telling them that the number
on all of those bulletin boards is a public key. If they use it to
decrypt the New York Times ad they will get a description of the
assassination, published the day before it happened.

I don't quite understand the mechanics of how the outlets are able to decrypt the ad and get a description of the assassination. Is the ad encrypted with his private key and since both public and the private keys are mathematically related, whatever is encrypted with the private key can be decrypted with the public key (visible on the billboard) and vice versa?

Interesting premise.
Q : "Is the ad encrypted with his private key ..."
A : no, I don't believe so
Edit - To clarify, I entertained the possibility that the author meant to say "private key" in item #4, but once you consider the subsequent paragraph in the source (excerpt below), I don't think the ciphertext that describes the crime in advance is encrypted with public-key cryptography. I reckon the author's protagonist is using the same bytes that are in the public key as the key for a symmetric cipher. (In this case, KDF could potentially be HKDF, PBKDF2, Argon2, scrypt, or even a keyed hash-digest.) eg.
broker_pk = PUBLIC_KEY( secret_key )
ciphDetailsOfCrime = E( KDF(broker_pk) , EvilPlanToMakeCelebsEvenMoreFamous )

eph_cli_pk = PUBLIC_KEY( ephemeral_client_secret_key )
kRequestForQuote = DH_or_ECDH( broker_pk , ephemeral_client_secret_key )
ciphRFQ = E( kRequestForQuote , DetailsOfNewTarget )
msg = eph_cli_pk || ciphRFQ

(This is a contrived example that shouldn't be used, especially if conspiring to commit murder and/ or acts of terrorism.) My original answer continues ...
It may be that the author meant to say "private key" in list item #4, however, I suspect the author is thinking about using the public key, posted on billboards, as a symmetric key (or password to be used in some key derivation function - aka. KDF) to decrypt the prior description of the heinously foul act of murdering film celebrities en masse ...
The paragraph that follows is:

"You have now made sure that everyone in the world has, or can get, your public key – and knows that it belongs to an organization willing and able to kill people. Once you have taken steps to tell people how to post messages where you can read them, everyone in the world will know how to send you messages that nobody else can read and how to identify messages that can only have come from you. You are now in business as a middleman selling the services of hit men. Actual assassinations still have to take place in realspace, so being a hit man still has risks. But the problem of locating a hit man – when you are not yourself a regular participant in illegal markets – has been solved."


How were the P-256 parameters chosen? In NIST FIPS 186-4 (page 90), it is said that $c$ is the output of SHA-1 on a seed that was chosen randomly. Then the parameter $b$ of the EC is chosen, according to the formula: $$b^2 \times c \equiv -27 \pmod p$$ Why choose $b$ this way? Why, as an example, couldn't $b = c$?

The algorithm for generating EC curve is in appendix D.5 of NIST FIPS 186-4, and the verification algorithm is in D.6. They are taken from ANSI X9.62, which justified the rationale as the following:

  In order to verify that a given elliptic curve was indeed generated at
  random, the defining parameters of the elliptic curve are defined to
  be outputs of the hash function SHA-1 (as specified in ANSI X9.30 Part
  2 [4]). The input (SEED) to SHA-1 then serves as proof (under the
  assumption that SHA-1 cannot be inverted) that the parameters were
  indeed generated at random.

The curve generation algorithm requires $a,b$ to satisfy $b^2\cdot c \equiv a^3 \bmod p$, and it is not necessary that $a$ and $b$ be chosen at
random. In the case of NIST Prime curves, they all use fixed $a=-3$, so $b^2\cdot c \equiv -27 \bmod p$.

As to the question why $b$ cannot equal to $c$, note if $a$ is not fixed then it is actually valid to choose $a=b=c$. But  $a=-3$ is chosen by NIST, so this is not possible because the seed does not hash to $-3$.


Corner cases of addition on short Weierstrass elliptic curves I am trying to implement arithmetic over points on a short Weierstrass elliptic curve and I have trouble with corner cases of the points addition operation. Let me specify the parameters of the curve and what is the problem exactly:

As a test curve I use Bitcoin elliptic curve $y^2 = x^3 + 7$
For testing purpose I do integer arithmetic $x\bmod 11$ to keep it simple for debugging purpose
I do arithmetic exactly as specified herein Wikipedia

The problem I have is with doubling of the point $(5, 0)$. In the doubling formula, there is a modulo inverse of $y$ point coordinate, that clearly doesn't exist for $(5, 0)$ since $y=0$. So my questions are:

How am I supposed to handle this case?
Is $x$ or $y$ equal to $0$ even allowed when doing math for short Weierstrass elliptic curves?
What is the exact list of corner cases that need to be handled when implementing an addition for short Weierstrass elliptic curve

Currently, my implementation has the following branching in the following order:

If one of the arguments in addition operation is the point at infinity, the other argument of operation is returned as the result
If one of the arguments is equal to a negative of the second argument result is the point at infinity
If arguments in addition operation are equal to each other then doubling formula is used as specified here in Wikipedia
Otherwise a basic addition formula is used as specified in Wikipedia

Negation is done by simply negating the $y$ coordinate with the exception that the negation of point at infinity gives back the point at infinity.
How far is this list from being complete? What else needs to be handled for this type of elliptic curve?
For those of you terrified by the fact that some noob is implementing math of an elliptic curve himself have no fear. This is not for practical crypto application, this is just a fun home project, the goal is to understand rather than to get a crypto-ready implementation :)
UPDATE: I used the comment of @corpsfini to update the routine and it turns out that I had an implementation flaw cause with $(5, 0)$ we have a case 2 of my branching scheme since $(5,0)$ is equal to negative of itself. So I fixed the bug and now all the unit tests work fine for $\bmod 11$ and some other random small groups. However the question remains, is it all that's out there? The SafeCurves web site warns that there are some failure cases that might not be disclosed by the random tests and that it's really hard to get them right. What I've coded up so far doesn't seem to be complex at all, yeah a bunch of if/else statements, but not something that I would call hard to get right. I expect that there is something else. Does anybody have an idea?

The Group Law on Affine Coordinates

Arithmetical rules are derived from the line intersection and tangent equations. The formulas are;
Let $P=(x_1,x_2)$ and $Q=(x_2,y_2)$ be two point in the elliptic curve.

$P+O=O+P=P$
If $x_1 = x_2 $ and $y_1 = - y_2$ and $Q =(x_2,y_2)=(x_1,−y_1)=−P$ then $P + (-P) = O$
If $Q \neq -P$ then the addition $P+Q = (x_3,y_3)$ and the coordinate can be calculated by;

\begin{align}
x_3 = & \lambda^2 -x_1 - x_2  \mod p\\
y_3 = & \lambda(x_1-x_3) -y_1 \mod p
\end{align}
$$
\lambda =
\begin{cases}
\frac{y_2-y_1}{x_2-x_1},  & \text{if $P \neq Q$} \\[2ex]
\frac{3 x_1^2+a}{2y_1},  & \text{if $P = Q$} \\[2ex]
\end{cases}$$

I have is with doubling of the point $(5,0)$ ... Is x or y equal to 0 even allowed when doing math for short Weierstrass elliptic curves?

When doubling we look at the tangent line. We have two cases;

$y_1 \neq 0$ for $P$, then
$$x_3 = m^2 - 2x_1, \quad y_3 = m(x_1 -x_3) - y_1,\quad \text{ where } m = \dfrac{3x_p^2 + a}{2y_p}$$

$y_1 = 0$ for $P$ then $P + P = [2]P = \mathcal{O}$

$(5,0)$ is the special case that the tangent line is vertical, the 4th case in the top figure. This means that $P+P = \mathcal{O}$ and $P$ has order 2. It also can be seen from the formulas, case 2.

update

This is about the implementation issue that people can forget the checks;

Maybe the implementor instead has "+" check for its inputs being equal. But this is less likely as an implementation strategy: it produces a slower and more complicated implementation. Furthermore, it does not catch all the failure cases. For example, the standard Weierstrass addition formulas fail if Q happens to match -P. This will not be caught by random tests.

and

2007 Bernstein–Lange showed that the Edwards addition law is complete for every complete Edwards curve E. This means that, for every rational point P on E, and for every rational point Q on E, the Edwards addition law for inputs P and Q produces as output exactly P+Q. There are no exceptional cases. The Edwards addition law can be used for complete single-scalar multiplication, complete double-scalar multiplication, etc.

So, one addition law for all!


Can we use elliptic curve cryptography in wireless sensors? Can we use elliptic curve cryptography in wireless sensors?

If so, how do you map points to message characters?

Yes, one can use Elliptic Curve Cryptography in wireless sensors.

A typical use of ECC in this domain would be to authenticate the sensor and establish a symmetric session key using a combination of ECDSA and ECDH. That symmetric session key would then protect application data, insuring confidentiality and integrity using AES-GCM. This is hybrid cryptography.

Notice that in this typical use case, there is no mapping of points on elliptic curve to "message characters" representing application data; rather, application data is dealt with by mean of symmetric cryptography.

The main benefit of using ECC rather than RSA or Rabin in resource-constrained devices like wireless sensors is that for equivalent security, ECC needs less RAM, and shorter keys and messages; and also less CPU power when computing a signature, or establishing a session key, or (hybrid) DEcryption. On the other hand, for signature verification or straight Public Key ENcryption, RSA uses less CPU power (and allows shorter signed messages as well for many real-life use cases, including certificates).

As a consequence, ECC has an edge when there needs to be a public method to authenticate the data coming from the sensor (which implies ability to protect confidentiality of a private key in the sensor), or when RAM is extremely constrained, or when the amount of data exchanged during key establishment needs to be reduced to the max.

For other uses, including protecting the sensor from rogue commands and insuring confidentiality of the data sent by the sensor (basically the only goals still achievable when it is impossible to protect long term confidentiality of key material held in the sensor), RSA or Rabin is often a better choice than ECC. More RAM is required, but 1kByte is plenty enough for 2048 bit modulus, and it is used only temporarily during signature verification or PK encryption.


understanding NTLM authentication The flow is like this.

Client sends GET to Server
Server responds with 401 UNAUTHORIZED and the authentication protocol: NTLM
Client re-sends the request including authentication information.

I don't get it. What exactly does the client send at step 3? The password? And if yes, what encoding does it use? The username should be sent in plain text and I don't see it. Here are the HTTP headers:

GET http://example.com
HTTP/1.1 401 Unauthorized. WWW-Authenticate: Negotiate. WWW-Authenticate: NTLM
GET http://example.com Security: Authorization: Negotiate YIIPQwYGKwYBBQUCoIIPNzCCDzOgMDAuBgkqhki...UMVM=

At step 3 I've cut part of text because it was way too long.

You missed some additional steps and your assumption to pass the username as plain text is not completely right. The whole authentication is done with HTTP headers containing binary messages as Base64.

What you see in step 3 is the negotiation message including host and NT domain in a documented format.

Next the server will respond with a message containing the “challenge” which is a random 8 Byte number. The client will add its own 8 byte random to flummox rogue servers.

To get authenticated the client has to send the encrypted challenge, knows as the response. The encryption is done using 56-bit DES with it’s MD4 hashed password as key.

The server compares the encrypted challenge with one he created the same way with the password known or passed it to a domain controller for verification.

So the password itself is never transferred.

A more detailed description see NTLM Authentication Scheme for HTTP or at MSDN.


What is the meaning of weight in cryptography and how is it related to branch number? I am trying to understand the mixcolumn design of AES. I read that the branch number is 5 and there was a definition that referred to weight of vectors. What is weight of a vector?

In cryptography, "weight" of a vector of bits is most often the Hamming weight, that is the number of non-zero bits in the vector. But in this AES context, that's most probably the "bundle weight" of a vector of bundles of bits (e.g. a vector of bytes), defined as the number of non-zero bundles.

In the AES context, the "(differential) (bundle) branch number" of a Boolean transformation with respect to a bundle partition, as defined by Joan Daemen and Vincent Rijmen in The Design of Rijndael (2002), section 9.3, is a measure of diffusion. It is defined as the minimum bundle weight of the XOR of two distinct input/output combinations of said transformation. For MixColumns, that's the minimum number of bytes that can change between two distinct input/output combinations (of a total of 32 bytes), or equivalently the minimum number of bytes in a non-zero input/output combination; which is 5.

This is consistent with the general definition of Hamming weight in coding theory, where, for a given symbol alphabet, the weight of a nonzero symbol is $1$ while the weight of the zero symbol is $0.$ The designers of AES used MDS codes over the finite field $GF(2^8)$ (which can be represented by binary vectors of length 8, i.e., the vector space $GF(2)^8$). This is a $[length=8,dimension=4,min.~distance=5]$ code and the minimum weight (same as minimum distance since the code is linear) is $5$. This minimum weight corresponds to the guarantee that there are at least 5 total nonzero bytes amongst the 4 input and 4 output bytes (the number of input bytes is the dimension of the code and the number of input+output bytes is the length) of the $\textsf{MixCols}$ mapping.

This answer further discusses the branch number.

Thanks for the many useful contributions in comments!


Efficiently computing the neutral element in a ring isomorphic to Z/NZ? Edited to clarify question

So my question is whether anyone knows of an efficient way to compute the neutral element (I'm gonna call it 1, but the operation doesn't have to be multiplication) in an abstract ring isomorphic to $\mathbb Z/ N\mathbb Z$? More specifically, the scenario is this:

Suppose we have a ring $ R = \mathbb Z/ N\mathbb Z$ (here, the operations are addition and multiplication) and a ring isomorphism $ f: (R,+,\cdot) \rightarrow (S, \triangle, *)$. However, we do not know what this bijection $f$ is. We also assume $N$ is very large, like an RSA-Modulus, and thus factorization is unknown. As has been pointed out, if $N$ is exponentially large, we can't just have a list of the elements, so we will assume that the elements are given through a black box that when invoked outputs an element of $S$, but does not tell us which element of $R$ it corresponds to. The elements of $S$ could, for example, be bitstrings.

D.W. has shown in his answer that if we only have oracle access to $\triangle$ and $*$, the neutral element regarding $*$ cannot be efficiently computed if $N$ can't be factored efficiently. So the question remaining is:

If the operations $\triangle$ and $*$ are explicitly given as a formula, can we always efficiently compute the inverse operation of $*$ and thus the neutral element?

Or are there cases when even having the formula instead of oracle access does not help us?

Here is a short example:

$R$ is $\mathbb Z/ 7\mathbb Z$ with regular modulo-addition and multiplication.
$S$ is $\mathbb Z/ 7\mathbb Z$, $ x \triangle y := x + y - 4 \bmod 7, \ \ \ x * y := (x-4)(y-4) + 4 \bmod 7$.
So in the ring $S, \ e_\triangle = 4$ (we get this through solving $x \triangle e_\triangle = x \forall x \in S \Leftrightarrow x + e_\triangle - 4 = x \forall x \in S \Leftrightarrow e_\triangle - 4 = 0$, or more generally because we know that the order of the group regarding $\triangle$ is 7, i.e. we can take an arbitrary $x$ and compute $ x \triangle x \triangle x \dots \triangle x$ (7 times)).

But what about $e_*$? In this specific example, we can easily solve $x * e_* = x \forall x \in S$ to obtain $e_* = 5$, but we are only able to solve it because this is an easy example.

Thank you for your help :)

This is a spectacularly ambiguous, poorly-posed question, so I'm going to instantiate it in a way that I find interesting.  If this wasn't the question you wanted answered, then edit your question to do a better job of asking a well-formed question.

$\newcommand{\tri}{\mathbin{\triangle}}$
I'm going to assume we are given an integer $N$ of unknown factorization, and we have a representation of elements of $\mathbb{Z}/N\mathbb{Z}$ as bit strings, via some representation function $[\cdot] : \mathbb{Z}/N\mathbb{Z} \to \{0,1\}^*$.  Thus, $[x]$ is the representation of $x \in \mathbb{Z}/N\mathbb{Z}$.  Define the operations $\triangle,*$ so that $[x+y] = [x] \tri [y]$ and $[xy] = [x] * [y]$.  Or, in other words, define $\tri$ by $s \tri t = [\langle s \rangle + \langle t \rangle ]$ where $\langle \cdot \rangle : \{0,1\}^* \to \mathbb{Z}/N\mathbb{Z}$ is the inverse map of $[\cdot]$, and similarly for $*$.

(In terms of the original question, the bit strings play the role of the ring $S$.)

Suppose we are given the following abilities (and only these abilities):

We have a black box that, when invoked, will generate a random element $r$ in $\mathbb{Z}/N\mathbb{Z}$ and output $[r]$ (it won't tell us $r$, though).
We have a black box that, when given $s,t$ as inputs, will output $s \tri t$.
We have a black box that, when given $s,t$ as inputs, will output $s * t$.

The question becomes: can we compute $[1]$, a bit string that is the representation of $1 \in \mathbb{Z}/N\mathbb{Z}$?  In other words, we're looking for a generic algorithm that will work correctly no matter what representation map $[\cdot ]$ happens to be chosen.

And the answer is: no, there is no efficient algorithm to compute $[1]$, given only these operations.  This can be shown, using the same techniques used to show lower bounds in generic black-box groups, e.g., the same techniques used to show that there is no polynomial-time generic algorithm for the discrete log in a generic group.

How do we show it?  I'll start by illustrating a proof, for the case where we are only allowed to invoke the first black box once: we can generate a single random value $[r]$, and then we can apply $\tri,*$ polynomially many times.  Here's the proof.  Let $x_0=r$, and let $x_i$ denote the $i$th element of $\mathbb{Z}/N\mathbb{Z}$ that we compute.  For instance, if our algorithm takes $[r]$ and computes $s = [r]\tri [r]$ and then computes $t = s*[r]$ (say), we'll have $x_0=r$, $x_1=r+r$, $x_2=x_1x_0$.  Say that the algorithm runs for $k$ steps.  For the algorithm to be correct, we need it to output $[1]$, or in other words, we need to have $x_k=1$.  Notice that each $x_i$ can be expressed as some polynomial of $x_0$, say, $x_i=p_i(x_0)$ (this can be proven by induction).  So our algorithm corresponds to a polynomial $p_k(\cdot)$.

If the algorithm is correct, we must have $p_k(r)=1$ with high probability over the random choice of $r$.  Is this possible?  It turns out that this is not possible, if $k$ is not too large and if $N$ is hard to factor.  In particular, if $\Pr_r[p_k(r)=1]$ is large, then we get an algorithm for factoring $N$ with $k$ steps and with a non-trivially large success probability.  Here's why.  Define the polynomial $q(\cdot)$ by $q(x)=p_k(x)-1$.  By assumption, $\Pr_r[q(r)=0]$ is large, i.e., the polynomial $q(x)$ has many roots.  On the other hand, it can't have too many roots: it has at most $k^2$ roots, by a simple application of the Chinese remainder theorem, so if $k$ is smaller than $\sqrt{N}$, $\Pr_r[q(r)=0]$ is large but strictly smaller than $1$.  Now suppose $N=PQ$, and consider the polynomials $q(x) \bmod P$ and $q(x) \bmod Q$.  Notice that

$$\Pr_r[q(r)=0] = \epsilon_P \times \epsilon_Q$$

where $\epsilon_P = \Pr_r[q(r)=0 \pmod P]$ and $\epsilon_Q = \Pr_r[q(r)=0 \pmod Q].$

Since the left-hand side ($\Pr[q(r)=0]$) is large, then both right-hand side terms ($\epsilon_P,\epsilon_Q$) must be large.  In particular, $q$ has many roots modulo $P$ and many roots modulo $Q$.  So, here is an efficient algorithm for factoring $N$. We pick $r$ randomly, compute $q(r)$, and then compute $\gcd(N,q(r))$.  Notice that this outputs a non-trivial factor of $N$ with probability $\epsilon_P (1-\epsilon_Q) + \epsilon_Q (1-\epsilon_P)$.  Since $\epsilon_P \times \epsilon_Q < 1$ but both $\epsilon_P,\epsilon_Q$ are large, it follows that $\epsilon_P (1-\epsilon_Q) + \epsilon_Q (1-\epsilon_P)$ is large, i.e., this algorithm for factoring $N$ has a large success probability.

So this is a reduction which shows that any efficient solution to this problem immediately yields an efficient algorithm for factoring.  As a consequence, we should not expect any efficient solution to this problem (since we don't expect there to be any efficient algorithm for factoring).  The reduction is tight, since I have shown in the comments that if you can factor $N$, then it is easy to solve this problem.

Technically, I only proved the result for algorithms that make just one call to the first black box (the one that generates a random value $[r]$).  However, this proof technique can be extended to algorithms that make any feasible number of calls to the first black box, by looking at multivariate polynomials instead of univariate polynomials.  These are basically the same techniques used to show that there is no generic algorithm for the discrete log (in generic/black-box groups) that runs faster than square-root time.


lookup encrypted text by clear text without decryption I've implemented vouchers module in my web project where I use it to generate redeem get etc... vouchers.

since voucher codes are considered sensitive, I've considered to encrypt them using AES-GCM.

but how can I query clear voucher code to encrypted one to check voucher validity in order to redeem later?

I've thought of these two solutions

I am thinking to make like a MD5 for the clear code to live in the
document, in order to match it with clear code queries?
Reversed distribute, where to give the user encrypted voucher codes, and store the clear voucher codes on the DB,
when a query is applied to redeem a voucher system decrypt code applied with secret key and iv and looks for a match?

Does those approaches carries less performance overhead than decrypting whole data?, is it safe to consider one of them.

Audience of threats

system admins
attackers
DB data breach

Query with SELECT

AES with ECB mode can be used as long as the vouchers codes are unique. ECB mode gives you the same results when the key and plaintext are same.
Another solution is continuing to use AES-GCM to save your vouchers codes. To have the equality on the SELECT statement, use a secure hash function e.g. choose from the SHA3 family. With negligible probability, you will have a collision. If you have a collision store the values, you will be famous. In any case, you will decrypt the AES-GSM after the match of the hash values.

Attacks

As I said in the comment you attack is very broad; I will give answer for single cases;

System admins: If you don't trust them, this is a serious issue. They can query everything, even you deploy an HSM. They can insert, delete, etc. Keeping a query log of the Database may help you investigate. Also, there are works as RSA Beehive's that can detect the behavioral change of the users of the system that will can block action. They claimed that "we can prevent the Snowden."
Attackers: For the database attack, see the next. If the attacker access the application servers they will be same as a malicious system administrator, probably, a short time.
DB data breach: Since the clear vouchers are not in the database, We expect that by the collision-free and the security of AES-GCM the database will be untouched. However, if the database attacker is also an active attacker, you may need some integrity into your rows and even some chaining link for the columns. A simple one as in blow;

r_i  = |data_1|... |data_k| h_i   = hash(data_1,...,data_k)| sign(h)|
r_i+1 =|data_1|....|data_k| h_i+1 = hash(data_1,...,data_k)| sign(h_i+1||h_i|)|


Definition Problem for toy SPN I am reading Differential Attack from Stinson-Cryptography: Theory and Practice on a toy example of S-box(block Cipher) with Nr=n=m=4.

I am mainly confused in the following definition

  Definition 3.1 : Let $\pi_S:\{0,1\}^m\rightarrow \{0,1\}^n$ be a S-box. Consider an (ordered) pair of bitstrings of length $m$, say $(x,x^*)$. We say that input XOR  of the S-box is $x\oplus x^*$ and the output XOR is $\pi_S(x)\oplus\pi_S(x^*)$.

Now, the point of confusion is how can the output of the S-box be separated as $\pi_S(x)\oplus\pi_S(x^*)$ when the input is $x\oplus x^*$?

For eg:
We choose the two plaintexts $x_1$ and $x_2$. Then we have $x_{12}=x_1\oplus x_2$
Now, we have round $1$ key $K^1$, we get $^1u^1=x_1\oplus K^1$ and $^2u^1=x_2\oplus K^1$
Then, we apply $\pi_S$ on the above, we get $^1v^1=\pi_S(^1u^1)=\pi_S(x_1\oplus K^1)$ and $^2v^1=\pi_S(^2v^1)=\pi_S(x_2\oplus K^1)$
Therefore, $^1v^1\oplus\enspace ^2v^1=\pi_S(^1u^1)\oplus \pi_S(^2v^1)=\pi_S(x_1\oplus K^1)\oplus \pi_S(x_2\oplus K^1)$

Now, I don't understand that How, $^1v^1\oplus\text{ }^2v^1=\pi_S(x_1)\oplus\pi_S(x_2)$?

Also, I don't know whether I got the definition or not?

EDIT: Notation Explanation:
$^iu^j$ denotes $i$th plaintext( either plaintext if j=1 or cypertext after $j-1$th round) XOR-ed with $j$th Round Key $K^j$
Also, note that $^iu^j=\pi_P(^iv^{j-1})$ if $j>1$, where $\pi_P$ is the permutation i.e diffusion layer.

Definition 3.1 : Let $\pi_S:\{0,1\}^m\rightarrow \{0,1\}^n$ be a S-box. Consider an (ordered) pair of bitstrings of length $m$, say $(x,x^*)$. We say that input XOR  of the S-box is $x\oplus x^*$ and the output XOR is $\pi_S(x)\oplus\pi_S(x^*)$.
Now, the point of confusion is how can the output of the S-box be separated as $\pi_S(x)\oplus\pi_S(x^*)$ when the input is $x\oplus x^*$?

The crux of your question is above. Differential cryptanalysis is a chosen plaintext attack.
The attacker presents the Sbox (more generally the full cipher) with two sets of chosen plaintexts with a chosen difference $d$
$\{u_i: 1\leq i \leq N\},\quad \{u_i\oplus d: 1\leq i \leq N\}$
and computes the set of output distributions corresponding to this input difference
$\{\pi_S(u_i)\oplus \pi_S(u_i\oplus d):1\leq i \leq N\}.$


Problem with testing MD5 collisions I am trying to test MD5 collisions presented in “Collisions for Hash Functions MD4, MD5, HAVA” (PDF) by Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu; 2004.

I wrote a PHP script to test it, but it doesn't produce the expected hash output. I tested everything several times and found no errors in my code. I don't know what is wrong. Please help me to find the reason and test the collisions.

Here is my PHP script:

<?php

$M='2dd31d1 c4eee6c5 69a3d69 5cf9af98 87b5ca2f ab7e4612 3e580440 897ffbb8
634ad55 2b3f409 8388e483 5a417125 e8255108 9fc9cdf7 f2bd1dd9 5b3c3780';

$N1='d11d0b96 9c7b41dc f497d8e4 d555655a c79a7335 cfdebf0 66f12930 8fb109d1
797f2775 eb5cd530 baade822 5c15cc79 ddcb74ed 6dd3c55f d80a9bb1 e3a7cc35';

function fix_word_length($str) { //we need this because some hex words u see r less than 8 chars (e.g. the first hex word: 2dd31d1) / this pads them on the left with '0's

    return str_pad($str, 8, '0', STR_PAD_LEFT);

}

function convert2binary($str) {

    $str=str_replace("\n", ' ', $str); //replaces line feed chars with space
    $str=explode(' ', $str); //this converts each hex word to an array element / sorry for the name, but str is really an array after this operation
    $str=array_map('fix_word_length', $str); // pad hex words with a length less than 8 chars by '0's on their left
    $str=implode('', $str); //joins all hex words together again (with spaces between them removed). / str is now a string again
    return pack('H*', $str); // convert hex encoding to raw/binary and return it

}

$M=convert2binary($M);
$N1=convert2binary($N1);

echo md5($M.$N1);

?>

The output hash is 8da3a17b43e0e134bdc17557ffef15ff instead of the 9603161ff41fc7ef9f65ffbca30f9dbf mentioned in the article.

This was pretty vexing, but for some reason I could only create the "big endian" results given by table 2 in this paper.

I get the same result as you for the first message ($M.$N0) : 8da3a17b43e0e134bdc17557ffef15ff and a different value for the second message.

The following code seems to work for a test vector given in table 2:

<?php

$M0='02dd31d1 c4eee6c5 069a3d69 5cf9af98 87b5ca2f ab7e4612 3e580440 897ffbb8
         0634ad55 02b3f409 8388e483 5a417125 e8255108 9fc9cdf7 f2bd1dd9 5b3c3780';
    $M1='d11d0b96 9c7b41dc f497d8e4 d555655a c79a7335 0cfdebf0 66f12930 8fb109d1
     797f2775 eb5cd530 baade822 5c15cc79 ddcb74ed 6dd3c55f d80a9bb1 e3a7cc35';

$N0='02dd31d1 c4eee6c5 069a3d69 5cf9af98 07b5ca2f ab7e4612 3e580440 897ffbb8
         0634ad55 02b3f409 8388e483 5a41f125 e8255108 9fc9cdf7 72bd1dd9 5b3c3780';
    $N1='d11d0b96 9c7b41dc f497d8e4 d555655a 479a7335 0cfdebf0 66f12930 8fb109d1
     797f2775 eb5cd530 baade822 5c154c79 ddcb74ed 6dd3c55f 580a9bb1 e3a7cc35';

function convert2binary($D) {
      // removes whitespace
      $D = preg_replace('/\s+/', '', $D);
      // reorders 4 bytes at the time
      $D = preg_replace('/(..)(..)(..)(..)/', '\4\3\2\1', $D);
      // hex2bin for older PHP
      $D = pack('H*', $D);
      return $D;
}

$M0 = convert2binary($M0);
$M1 = convert2binary($M1);
echo md5($M0.$M1) . PHP_EOL;

$N0 = convert2binary($N0);
$N1 = convert2binary($N1);
echo md5($N0.$N1) . PHP_EOL;

?>

Which should show the result:

a4c0d35c95a63a805915367dcfe6b751
a4c0d35c95a63a805915367dcfe6b751

I took the liberty to perform the padding manually. There seems little need to creating a specialized method for this (and my PHP skills leave something to be desired).

Note that cryptographers are often pretty sloppy when it comes to these kind of things, the test vectors don't seem very well defined (but at least they are documented).


Client-server communication The base scenario goes as follows: A program stores some user's confidential data encrypted on their disk. The user is most probably clueless and the disk might get stolen, but these are the classical problems.

Now there's a requirement to allow a sort of remote access without increasing the risk too much. The program gets split into a server and a client parts, each running on a different computer (both belonging to the user). The client part gets the password from the user and the server part gets the encrypted data from the disk. None of the parts is capable of authenticating itself to the other one, as both operate in a possibly compromised environment (so any secret stored in the program is void, but let's assume that the user can enter their password without being snooped).

The server part could send the encrypted data to anyone asking for them, but in comparison to the base scenario, it allows a remote attacker to obtain these data and let their cracking farm work on them. I wonder if there's a better protocol?

If your environment was fully compromised you could at no point actually decrypt your data, defeating the purpose. So I’m going to assume the user only uses an authentic client and the client’s memory is protected during execution.

Generate a private/public keypair. Store the public key on the server, encrypt the private key with the user’s passphrase and store it (encrypted) on the client.
Now the client can authenticate itself against the server without storing any secret between executions.


Relationship between exponent and modulus in RSA (as RSA properties as listed in X.509) In one of my assignments, I had the following question (Please read on. Not a homework assignment :) ):

  X.509 (1998 version) lists properties that RSA keys must satisfy to be
  secure. One such requirement is that the public exponent  $e > \log_2(n)$ where n is the modulus. Consider the
  following justifications for this:

  We require $e > \log_2(n)$ in order to prevent an attack to disclose the plaintext by taking the eth root modulus
  n.
  We require $e > \log_2(n)$ in order to prevent an attack to disclose the plaintext by taking the eth integer root.

  Which of these two is the correct justification of the above
  requirement? For the incorrect justification, explain why is it
  incorrect.

My question here is: Where is the X.509 certificate listed mentioning the above requirement? I tried googling a lot but could not find any such requirement listed in any  online available material unfortunately.
Also, if any such requirement does exist, what is the justification for the same?

The requirement was introduced in IUT Recommendation X.509 (November 1993), informative appendix D.5.2:

  It must be ensured that e > log2(n). If not, then the simple operation of taking the integer eth root of a ciphertext block will disclose the plaintext.

This advice was removed in the 2000 edition of the standard. It was arguably misguided, and at the very least the justification given was very incorrect (even when using RSA for encryption without padding, what's stated in the justification works only for a very small portion of plaintexts, including for $e=3$; it thus does not work at all for random plaintext, or when using RSA with proper padding).

The assignment itself is questionable: we are asked to choose among two incorrect justifications for advice so questionable that it was removed; and it turns out that the few plaintexts allowing the attack in 1 to work also allow to perform precisely what's claimed in 2. The only superiority of argument 1 is that it more clearly describes an attack which is NOT a good reason to use a public exponent larger than some bound.


One way shared key encryption with NaCl - is it safe to generate a throwaway keypair for the encrypting party Libsodium seems to be a famous library so I'm not sure I need to introduce it but just incase: https://nacl.cr.yp.to/ (Edit: NaCl not Libsodium, oops!)

So, I need users to be able to pass me information that no one else can read, so I've generated a secret key. Using NaCl I create a keypair from that secret key and I share the publicKey of the keypair with my users.
Now, they encrypt their information with nacl.box() which requires their message, a nonce, my public key, but also their private key? In the past I've traditionally used asymmetric encryption like AES (edit: I meant RSA) and only needed my public key... so I just generate, on the user's end, a random keyPair for the user to use. I'll call this throwawayKey.
encryptedMessage = nacl.box(message = "foo",
                            nonce = 0,
                            publicKey = MY_SHARED_KEY,
                            secretKey = throwawayKey.secretKey());

Then they can send me back this encrypted message AND send me back the public key for the throwaway key I generated them... throwawayKey.publicKey()
Then, I can later decrypt on my end, using this:
decryptedMessage = nacl.box.open(message = encryptedMessage,
                                 nonce = 0,
                                 publicKey = throwawayKey.publicKey(),
                                 secretKey = MY_SECRET_KEY);

Is this a safe way to have users send their info to my securely... I'm not used to having to generate a throwaway keypair for generic one way asymmetric encryption, am I using NACL wrong? It feels wrong to just generate a random throwaway key haha...

If you want users to be able to send you messages anonymously you can use "sealed boxes" instead of plain boxes.


Can AES-NI be used to accelerate asymmetric encryption? AES-NI optimized processors can be used to accelerate AES, which is a symmetric crypto. Can it also be used to accelerate asymmetric crypto?

These are the AES-NI instructions listed by wikipedia:

AESENC:   Perform one round of an AES encryption flow
AESENCLAST:   Perform the last round of an AES encryption flow
AESDEC:   Perform one round of an AES decryption flow
AESDECLAST:   Perform the last round of an AES decryption flow
AESKEYGENASSIST:  Assist in AES round key generation
AESIMC:   Assist in AES Inverse Mix Columns
PCLMULQDQ:    Carryless multiply (CLMUL)

If the asymmetric crypo in question were to use any of these operations, then yes, it could be accelerated by the appropriate hardware instruction.

However, standard asymmetric primitives such as RSA and Diffie-Hellman do not use these sorts of operations. Without knowing specifically what asymmetric algorithm you had in mind, we can conclude the answer is probably "No".


Recovering plaintext from AES-128 given round key 10 and ciphertext I'm working on an old CTF challenge where AES-128 was used on a 16 byte block. I have the round 10 key and the ciphertext. What techniques exist for obtaining the plaintext?

Since this is CTF, I'll give you some detailed hints.

Normally by using only a ciphertext, you cannot determine the plaintext, since for every key the deciphered ciphertext is a valid plaintext and some of them are perfect in English or any other language. So, some other information must be given to you for verification.
16-Byte just means one block for AES.
There is a difference in key schedules between AES-128 and AES-182,AES-256.
Your CTF is not possible with the key schedules of AES-192 and AES-256
You have given only, one round key. The different key schedule of AES -128 will enable this.
Search for AES master key Round Keys ( in this site)


Can Grover's Algorithm be combined with a meet-in-the-middle attack? We all know and love the meet-in-the-middle attack, which basically makes double encryption pointless using a time-memory trade-off. Now, the NSA recently recommended to use double encryption to adequately protect sensitive data from quantum attackers.

This made me ask myself:

Can one combine Grover's algorithm with the MITM attack to make double encryption "pointless" in the quantum setting?

Example:
The classical strength of double AES-256 encryption is 257-bits and $2^{256}$ storage. Using Grover's algorithm to attack the full cipher would take $2^{256}$ time. Can this time be reduced using a MITM trade-off and a quantum computer?

You could be able to reduce the space required for a meet-in-the-middle attack, if you follow a similar idea as the application of Grover's algorithm on collisions. Suppose you have two layers of $n$-bit encryption:

Partition the inner keyspace into $2^{n/4}$ parts of size $2^{3n/4}$.
For each partition generate the inner encryption table.
Run Grover's on the outer keyspace in $O(2^{n/2})$ time.
If you find the preimage in the table, you found both keys, otherwise return to 2.

You would get $O(2^{n})$ time and $O(2^{3n/4})$ storage, which is better than classical meet-in-the-middle and requires less quantum computations, $O(2^{3n/4})$, than just using Grover's on the whole combined keyspace in $O(2^{n})$ time.

The problem of the size of the quantum computer would probably apply (maybe $O(2^{3n/4})$ qubits here?).


RSA encryption secure mode, plaintext length limit vs. key length I have two questions about RSA encryption to confirm:

Assume use RSA 2048-bit key pair, what is the secure encryption mode? Are ECB / OAEPWithSHA-256AndMGF1Padding and ECB / OAEPWithSHA-1AndMGF1Padding secure modes?
For example, we know the maximim length of plaintext to be encrypted is limited by key length.

  RSA was not designed to work with large amount of data. You can process messages only with limited length, that depends on the key size. The bigger key is, the bigger message can be encrypted.

For 2048 key, what is the maximum plaintext length? What is the math relation between them?

Lets assume Java here. In that case the ECB part of the name is a misnomer. ECB is the most simple mode for a block cipher. It means splitting up the plaintext message into multipe blocks and then encrypting them separately. Java's RSA implementation doesn't split anything up, you can only encrypt a single block of plaintext. They should have used "None" instead or have left it out altogether.

Yes, OAEP is secure, if implemented correctly. It requires a mask generation function parameterized with a cryptographically secure hash function. You can compare MGF1 with a key derivation function. For that kind of usages SHA-1 is still secure. I'd still prefer SHA-256 none-the-less, if just to avoid nasty questions on the protocol. It is plenty fast for this kind of use and new processors even contain instructions to speed up the algorithm.

For the maximum plaintext message I'll simply refer to a previous answer. It lists a payload size of 214 bytes for SHA-1 and 190 bytes for SHA-256 if OAEP is used.


Complexity of a brute-force search I am currently thinking about the complexity of a brute-force attack on a cipher. Let the key length of the cipher be 64 bit. Then there are $2^{64}$ different keys in the keyspace. If you do a brute-force search, in the middle you will have to search through $2^{63}$ keys for success. So my question is now, what is the complexity of the attack? Is it $2^{64}$ or $2^{63}$? I am not sure about it.

It is exactly $2^{64}$. You need to look for all possible keys for a successful brute-force. One cannot guarantee that the key will be in the half, $2^{63}$, that you are going to search. In, CS there is an adversary argument, that the adversary can always force you to the worst case. Tell him how you the search, he will produce a case that you are not going to find in $2^{63}$ key-space.

Actually, $2^{63}$ is the average case that you will find your keys during the brute-force.

If you have multiple known-plaintext with encrypted different keys then with a multi-target attack you can find some keys faster. The expected cost of finding a key from $t$ target is $2^{64}/t$.


Why is Diffie Hellman used alongside public keys? I just read this post here: Why do we need asymmetric algorithms for key exchange? that asserts that in public key cryptography when asymmetric keys are used to secure communications, for parties to agree on a common shared secret, the following method is used:

  So, say you want to send me a very long message, using asymmetric
  encryption. Here's what you'd actually do:

  (1) Pick a random key for use with a symmetric (fast) cipher. Encrypt
  your message using that (fast) cipher and key. Send me that encrypted
  message.

  (2) Then use asymmetric (slow) encryption to encrypt the following
  message and send it to me

  "Hi, I just sent you a message encrypted using the BLAH   symmetric
  cipher with key ABCDE123456."

So, you use your peer's public key to encrypt a shared secret, send the peer the encrypted secret, and then the peer decrypts the secret with his or her private key. In this way, you can use the big certificates to authenticate parties as well as use them to establish a shared secret.

This makes sense, but i have to be missing something. Why/how would DH be used here as well? I see that there are plenty of schemes like RSA2048 that have large keys, which i assume would be used in this way above, but also incorporate DH in their cipher suite:RSA_DHE, ECDHE.

What benefit does the DH component add? What can it do, now that we can establish a shared secret with the public keys in the certificates?

DH is often used to build session keys, which are used to provide forward secrecy. If you only use the public key in the certificate, then corrupting the private key may reveal all the previous encrypted messages. The attacker can first decrypt the symmetric keys then decrypt previous messages if it keeps records of the previous communications. Using DH can prevent this. Even if you have the private key, you still can not figure out any previous DH results to get the symmetric keys. In this way, the privacy of previous messages is still maintained.


Is it feasible to get a hash collision for CRC32, MD-5 and SHA-1 on one file? I'm aware that individually, each has its weaknesses (especially CRC32), but is it feasible that a file could be created to falsely match all three?

Finding a simultaneous collision for all three would take the effort of approximately $2^{72}$ SHA-1 compression function evaluations.

The overall idea would be to take the general $2^{67}$ idea found in the answer to How hard is it to generate a simultaneous MD5 and SHA1 collision? and perform the attack 33 successive times (generating 33 places in the hash image where we can take either $X_i$ or $Y_i$ without affecting either the MD5 or SHA-1 hash).

That'll give us a total of $2^{33}$ images with all the same MD5 and SHA-1 hash; there must be a pair of images with the same CRC-32 value as well, and so that solves the problem.

Whether $2^{72}$ operations is in the realm of feasibility is another question entirely...


How to design a cryptographically secure file hosting service How would one go about designing something like Google Drive/Dropbox providing the following features:

files are encrypted and decrypted on the client
files can be synced between devices
the service provider shouldn't be store private keys/passwords on servers
if the user can have only one password to remember that'd be great (we want to design something user friendly)
ideally one could share files with other users

So I thought about a couple of things which don't quite solve the problems.

Using AES to encrypt files

So the first idea is that each user has one password. Now to encrypt a file we derive a long enough AES key from this password (by hashing it and taking the first N bits of the hash) and we encrypt the file. Decryption can only be done if we have the original password.

This fulfills requirements #1, #2, #3, #4.

But I see several potential drawbacks: first files cannot be shared (unless we decrypt them...). Also how bad would that be to derive the AES key from a hashed password? And how bad would that be to reuse the same AES key again and again?

Using a public/private key encryption scheme

To encrypt a file: generate a key pair, encrypt with the public key, save this to the servers. To decrypt use the private key.

This fulfills requirements #1, #2*, #3.

[*] while files can be synced between devices we don't have a user friendly way to pass private keys around (because the user would have to store them 'offline' and carry them with him 24/7)

Sharing is also an issue. Let's consider that Alice stores a file foo.bar and wants to share it with Bob. The only way to do that would be for Alice to decrypt the file locally and reencrypt it with Bob's public key and then send this to Bob. This is cumbersome because it means that sharing takes time and needs Alice to be 'online' to be able to send the new encrypted file.

tl;dr

Is there a way to design such a system without any of the aforementioned drawbacks/flaws?

Generate key-pair
Generate random salt, hash password with proper password hash (scrypt or PBKDF2) to derive a master key.
Use HKDF to derive one login key and one encryption key from master key
Encrypt private key with encryption key from previous step
Upload it to server, download only possible by proving possession of login key (either send over SSL, or use SRP)
Encrypt files with random AES key, encrypt AES key to public key of a user


How should the key schedule be designed for this general block cipher? After looking at the Wikipedia page for the Fiestel cipher, I thought about making a variation of it that is very general.

I basically followed the diagram on Wikipedia in order to structure the algorithm. The way my algorithm encrypts messages follows this diagram (the decryption is just the reverse method as seen in Wikipedia):

In case the diagram fails to let you know what is going on, I have made an implementation in python without a strong key scheduling method here.

The main question I have is what key schedule method should I create/use/adapt for this cipher? A side question is any general improvements that could be done. The key schedule needs to be able to generate an arbitrary amount of keys and be able to take an arbitrary length key.

It's not a good idea to assume that your F-function is strong by itself. With very few exceptions, it's not true even with professionally-designed Feistel networks. In fact, the reason Feistel networks are even needed is because they're used to build a secure PRP from an insecure PRP or PRF. Said insecure function must be designed so that it is extremely lightweight and is secure after sufficient iterations.

Without more information, no one can tell you how to design a key schedule. They're generally tightly integrated with the rest of the cipher. All we can do is give you possible designs that would be inefficient but would work, or which would only be secure assuming your F-function is a strong PRF (which is quite an assumption). You have to think about a few things when designing a key schedule:

Do you need key agility and if so, how light must the key schedule be?
How does it interact with the rest of the cipher (this is a very complex question)?
What is your maximum memory and ROM footprint?
Is side-channel resistance important to you?
What kinds of operations do you wish to implement it in?

If you are not making any assumptions about the F-function, then you could use an algorithm like HKDF to expand an input master key into an arbitrary number of subkeys. If you do assume that the F-function is a strong PRF, which it very likely will not be, then the key schedule could be as trivial as XORing a round counter (functioning as a round constant) with the key to derive each round key. That would be necessary to avoid the slide attack, but relies on assumptions about the F-function's security.


Is AES ECB good enough for key spreading? My apologies if I get my terminology wrong - I am new to this stuff.

I am writing a routine (in c) to encrypt plaintext.  I am using TinyAES to perform a CBC on the plaintext and sending a (pseudo)random IV with the encrypted text.

The user supplies a password (ascii) which I pad to key length with a known (constant) block of bytes (from https://keygen.io/).  I then want both to spread the key byte values across the entire key length and to distribute the values of the bytes across the entire 0-255 range.

To do this I am currently using AES ECB with another known (constant) block of byte values (again from https://keygen.io/) as the key.  For AES192 and AES 256 I perform a second ECB on the key buffer offset by 8 and 16 bytes respectively.

Using this method I can generate the same key from the same password every time.  Is this a good spreading technique? Or am I falling into one of the many traps for the unwary?

I am using AES ECB so that I do not need any more library code in my app.....

I then want both to spread the key byte values across the entire key length

Neither is useful. AES is secure without such "spreading" (not a standard term). The method discussed does that fine.

However it is missed a step critical for security of any password-based encryption: key stretching. The idea is to transform the password into the key for AES (as done by the question's method), in a purposely slow manner. This is necessary to avoid a password search attack.

To derive of a key from a password you need a password based key derivation function or PBKDF. A key derivation function based on a password is also called a password hash for short; it is also commonly used for password verification. Known PBKDF's are bcrypt, scrypt, PBKDF2 and the much newer Argon2 (in various forms). These all perform key stretching.


What implementation properties of a hash function prevent safe truncation? Truncating a hash function's output should, in theory, not increase the likelihood of a collision more than you would expect based on the truncated output size. This makes sense when thinking about the the ideal hash function, a random function.

Since real-world hashes are not random functions, what properties of algorithms like sha2 make us comfortable with truncating, and what (popular) hashes exist out there that are known to have issues?

You really should never be truncating a hash.  Really you're talking about the difference between traditional hashing algorithms and cryptographic hashing algorithms.  A cryptographic hash algorithm has to not be predictable, while a traditional hash algorithm doesn't have that concern.  You aren't guaranteed perfect random distribution, so really you shouldn't ever be truncating a hash in any situation.

Could you specify a situation where people "feel comfortable truncating a SHA2 hash"?  I don't know what you're referring to.


What does this advantage statement signify? In many Attribute Based Encryption papers I see this line...

The advantage of an adversary A in this game is defined as Pr[b' = b] − 1/2.

Can someone explain what it means to me?

I assume it means that the chances of the guess being correct is equal to 1/2. Is this assumption accurate?

It means exactly what is written, the advantage of the adversary is a quantity which is defined as the difference between the probability that $b = b'$ and $1/2$. For example if the probability that $b = b'$ is $3/4$, then the advantage of the adversary is $3/4-1/2 = 1/4$.


Levels of strength: The Caesar Cipher SITREP: I am deciding what form of "Random" Number generation would fit best for a Caesar Cipher that encrypts each letter with a different integer as a shift. This encryption is being handled via C# code I have and will write. I have a few options for this as follows.

(Note: The transmission of the key to the receiver is NOT a concern at this time and when it is a problem I will open a new question, this also includes how to hide which method I use to get the key, as that is a question for another time. Also to note, all random numbers not specified to be generated in a specific measure should be assumed to be generated from the C# code Random.Next(); Thank You.)

OPTIONS:

User Entered. This can be up to the length of my message or below it in which case I can either use random numbers or simply repeat the sequence provided by the user (Please advise best option if this is the selected method).
Randomly Generated Numbers. I am aware of the use of OTP's but would also like to know how viable shorter keys are.
Computer or User Generated Keys. This method entertains many ideas such as a key linked to file size, time stamps, others. Is there another well documented use of encryption that serves well while being covert as to my use of it at the same time that I may look into?

ANSWERS: Please back up claims if they are not openly supported by the community here. If you would like to link to another question or article that may help please feel free to do so. Thank you for your time.

To be honest, I think all of them do NOT make much difference, since Caesar Cipher is a weak cipher. You can see Breaking the cipher on Wikipedia.
It uses a method called frequency analysis, which ignores key strength.

Also, the three methods you mentioned all have their weaknesses. You should use a secure random generator.


Are there any applications of Quantum Computation to Cryptography? (besides Cryptanalysis) I know that people may be yelling "of course!" at the title of the question, but my concern is not about how to construct quantum-resistant primitives, but rather how to use the power of quantum computers to develop secure and efficient cryptographic primitives and protocols.

For example, in post-quantum Cryptography people are concerned about the power of quantum computing as an adversarial situation, and the main use of such power is to solve problems like factoring or discrete logarithm (whereas the quantum-resilient primitives involve classical algorithms).

Are there primitives that use this power as an advantage (for instance, to improve efficiency)?

If quantum computers are going to become a reality then I agree we should prepare and deploy quantum-resistant schemes, but besides using the quantum power to perform cryptanalysis on certain classical cryptosystems, we could also use it to develop primitives involving quantum algorithms in their implementation (these may not be deployable before we live in a post-quantum world, but they could be used once scalable quantum computers exist).

Have this been studied? are there any proposals? In other words,does having quantum computers improve the Crypto world somehow?

As noted by kodlu, you are basically asking about the existence of the whole field of quantum cryptography (which is different from post-quantum cryptography).
All the field was arguably started by Stephen Wiesner’s invention of Conjugate Coding in 1969, but which was rejected remained unpublished until 1983. He proposed a theoretical way to use quantum mechanics to construct unforgeable banknotes. This stayed a pedagogical example until (roughly) the last decade, which saw a renewed interest in quantum money schemes.
The main and best-known application is quantum key distribution (QKD), for which many protocols and have been studied since Charles Bennett and Gilles Brassard’s seminal paper in 1984. These protocols need the capacity to exchange attenuated light pulses (typically single photons or coherent states) between the partners, a capacity which has been recently demonstrated over 400 km. There is currently research going on to build quantum relay, some experimental networks using “trusted relay” are operational, and a satellite has been sent by China last year to serve as a quantum communication relay. Beyond this line of work optimizing the “practicality” of these protocols, theoreticians work to improve the security proofs, going in some cases until device-independent security (the protocol is secure even if the physical device you need has been built by the adversary).
Bit commitment (BC) schemes have been proposed since 1984, in the same paper as QKD, but attacks were always found. In 1997, Dominique Mayers, and, independently, Hoi-Kwong Lo and H.F. Chau showed that unconditionally secure quantum bit commitment was impossible. Since secure  BC protocols have been found in specific scenarios:

Protocols secure against adversaries with limited noisy quantum memories
Non-composable secure protocols in a relativistic setting, where the fact that no information can propagate faster than light is a key part of the security proof.

Other relativistic quantum protocols have been studied for position verification since 2010, but security proofs remain hard to be found. We know that we will be limited to computational security, but the best generic attack is known is currently exponential, which leaves hope for security protocols.
Another line of research is blind quantum computing, the quantum analog of completely homomorphic encryption: it is possible to make a quantum computer (if you have one) perform a commutation on encrypted data in a completely blind way, at a small extra cost. The operator of the computer has no way to know anything about the computation (except its size), while the client, which only needs a small quantum apparatus (similar to the QKD one) gets the result of the said computation.
There are of course other avenues of research in quantum cryptography. If you want to have an idea of some of the subjects of this community, you can look on the web the program of the annual QCrypt conferences, where the slides of many talks are online.


Creating hash data signatures using RSA-CRT I have taken two prime numbers p=137 q=131 M=64 and i want to create a digital signature
n=pxq=17947
phi=(p-1)x(q-1)=17680
e=3                                     (I have taken public key e=3 as gcd(3,n)=1)
d=e^-1 mod phi
 =3^-1 mod 17680 = 11787
dP= d^-1 mod (p-1)
  = (11787)^-1 mod 136 = 3
dQ= d^-1 mod (q-1)
  = (11787)^-1 mod 130 = 3
qinv= q^-1 mod p
    = (131)^-1 mod 137 = 114
mp= M ^dP mod p
  = 64^3 mod 137 = 87
mq= M ^dQ mod q
  = 64^3 mod 131 = 121
h= 114*(87-121) mod 137
 =97                              (after converting to positive remainder)
Sig= mq+ h*q
   =121+ 97*131
   =12828

Verification
 M= (Sig)^e mod N
 = (12828)^3 mod 17947
 = 8301

Not matching with the message M=64 . Where did i make a mistake?

The question's formula dP= d^-1 mod (p-1) is in error. Rather, $d_P=d\bmod(p-1)$, or more directly $d_P=e^{-1}\bmod(p-1)$, which makes it unnecessary to compute $d$. Same for $d_Q$. See this answer for proof of the formulas.
Use of CRT in RSA is an alternative computation modality for the transformation¹ $x\mapsto x^d\bmod n$. The conditions for the choice of $p$, $q$, $e$ remain unchanged. They depend on reference. Something common for theoretical work would be some small $e\ge3$, and $p$ and $q$ distinct large random primes such that $\gcd(e,p-1)=1=\gcd(e,q-1)$ and of about the same bit size.

Note: the question's computation is an illustration with small parameters of one of the steps of actual digital signature with RSA. But

The primes used are way too small for security. Actual RSA keys use primes $p$ and $q$ with hundreds of decimal digits, so that the public modulus $n=p\,q$ is hard to factor.
In an actual RSA digital signature, the input of the private key function is not the message. Rather, the message (an arbitrarily large piece of data) is hashed and padded to form the input of the $x\mapsto x^d\bmod n$ transformation.

¹ That private-key transformation is the inverse of the public-key transformation $y\mapsto y^e\bmod n$ when $n=p\,q$ and $e\,d\equiv1\pmod{\lambda(n)}$ or $e\,d\equiv1\pmod{\varphi(n)}$. These transformations are over the set $\Bbb Z_n$ or $\Bbb Z_n^*$. That depends on reference.


Sending KCV (key check value) with cipher text I was wondering why it is not more common to send the KCV of a secret key together with the cipher text. I see many systems that send cipher text and properly prepend the IV to e.g. a CBC mode encryption. Wouldn't it be easier to prepend another  bytes with the KCV together with it? A good block cipher should not be vulnerable to known plain text, so I personally don't see any issue with sending the KCV.

It would of course be less efficient, but the upside is that you can distinquish with some certainty between using the wrong key and a general decryption failure. I say "some" certainty because if the first [blocksize] bytes are (too) garbled, then the compare would obviously fail. That said, it's unlikely that an single block, ECB mode encrypt of [blocksize] bytes would go wrong in any way.

PS The cryptoki standards only use the first three bytes of the KCV, but I think that this is mostly a convenience, and only partly a security measure (against brute force)?

I suspect that KCV's are in general not used because they don't add enough to be worth the small overhead.

There are a number of cryptographical attacks on encrypted methods that involve the attacker modifying a valid ciphertext, and then having the receiver decrypt the modified message (and watch how the receiver reacts).  Because of these attacks, it is generally wise to include an authentication tag along with the message; if the authentication tag does not check out, then the receiver rejects the message (and in a way that is independent of how the message was modified; this prevents the attacker from deducing any information).

There are a number of ways to authenticate the message; you can generate a MAC of the ciphertext, you can sign the plaintext, you can use a cipher mode of operation that encrypts and authenticates (e.g. GCM).  One thing which is not a valid method would be adding a KCV value (a valid KCV value means only that the KCV value was computed by someone who knew the keys; it doesn't say anything about whether the rest of the message was modified).  So, if you use a KCV, you still would need an authentication method as well.

Which brings up a question: if you're already including an authentication method, what extra does a KCV bring to the table?  Well, I can't see much.  If the sender made a mistake, the receiver would be able to catch it earlier; however, that's not something we typically care about optimizing for (one possible exception would be a password-keyed file encryption method; you might not want to have to decrypt a full multigigabyte file before noticing that the password was wrong).  You might hope to try to distinguish the cases where the sender uses the wrong keys versus he makes another type of error; I don't see how that would be useful in general (and note that an attacker would be able to simulate both types of errors depending on how he modifies the ciphertext; hence if one type of reaction is useful to him, he can induce that).

KCV's don't add much expense (another cipher block evaluation and a few more bytes of encryption overhead), but if they don't bring any benefit (and except for that one case I mentioned above about file encryption, I don't see how they do), it's hard to see why to pay that small additional expense at all.


How can RSA be used to compactly sign and encrypt? How can RSA be used for digital signature with message recovery and encryption, providing transmission of a small message with confidentiality and authentication simultaneously, small cryptogram size, and little or no reliance on symmetric/hybrid encryption?

Re-using RSA key pairs for both encryption and signing is catastrophic, since it leaks the private key. So two pairs of keys will be needed.
RSAES-OAEP is a system that allows RSA to encrypt short (shorter than the modulus) messages. It's slow, and the length restriction is a big limit, but it does work.
RSASSA-PSS is a system for signing messages using RSA.
So encrypt using RSAES-OAEP and the recipient's encryption public key, then sign the ciphertext using RSASSA-PSS and the sender's private key.
A better solution is to use static-ephemeral ECDH to  create a shared secret between the recipient's static key and the sender's ephemeral key, then encrypt the message using an AEAD like AES-GCM-SIV, and sign the whole ciphertext+IV+Tag using RSASSA-PSS.


Why does Carter-Wegman MAC have 2n-bit output? The Coursera course on Cryptography 1 has a section about Carter-Wegman MAC. Here is the image of slide:

Now my question is both $F$ and $S$ output $n$-bit strings. We XOR two $n$-bit strings and we should get an $n$-bit string as a result. But the slide says the output result is a $2n$-bit string. How is this possible?

The MAC consists of the pair of the n-bit random value $r$ and the n-bit value $t = F(k_1,r) \oplus S(k_2,m)$. The length of $(r,t)$ is at least $2n$ bits, partly depending on how it is encoded. If the two values are simply concatenated, the total length is $2n$, as stipulated.


Length of key: symmetric vs asymmetric algorithms I am studying the fundamental concept of cryptography. I found the following statements:

You can compare symmetric algorithms based on the key (e.g., CAST-128 bit “weaker” than AES-256)
You cannot compare asymmetric algorithms based on key length.
More importantly, never compare asymmetric vs. symmetric key lengths!

The third point seems obvious. Can you explain me the other two?

Point 1: If two symmetric algorithms with no attacks better than brute force but different key lengths are to be compared, then simply comparing the key lengths tells you which is stronger. A larger key is stronger. Note that keys larger than 256 bits are typically slower and provide no practical increase in security (as in, even with quantum computers they'll take centuries to brute-force). Note that the "no attacks better than brute force" is the key here, FEAL-NX with a 128-bit key is thoroughly broken and far less secure than AES with a 128-bit key.

Point 2: The security of asymmetric algorithms is less related to key length because there are attacks better than brute force for all existing asymmetric algorithms. For a trivial example RSA uses large prime numbers, which must be odd, and thus one can skip the even numbers when performing trial division, thus dividing the brute force search time in half. The actual improvements on brute force search are more complicated and vary significantly from algorithm to algorithm.

Point 3: As symmetric and asymmetric ciphers are totally different things with different purposes it's like comparing the cargo capacity of a freight train with that of a container ship. The same units (mass or volume) are used, but they do very different things and can't simply be exchanged. Trains don't float.


Key change and key derivation There are two ways for key change: key update, and Re-keying.
Which of these methods use a KDF (Key Derivation Function) for getting new keys?

KDFs can be used for both: key update and re-keying.
As a KDF is usually a Function like this: $KDF(Secret,DerivationParams)$, you can use it to derive keys from old keys (key-update) but you can also use it for re-keying as nothing prevents you from setting a new secret (by the means of the KDF). As there are some KDF that look like this: $KDF(Secret,Salt,Params)$ you can even do a hybrid thing, where you depend on your old key and add new entropy to the new key.


Can Paillier ,RSA or any other schemes be used for universal re-encryption like elGamal? ElGamal, RSA, and Paillier cryptosystem have homomorphic property, and can be used fro re-encryption purposes. I want to use the encryption to re-encrypt ciphertext(as in  proxy re-encryption but differently/different scenario / may be like universal re-encryption)
Requirements:

Encryption:
Encryption: choose some random number r1 with other parameters like public key, private key, mod, message:m ,C1:ciphertext etc. The key pair (private key,public key).
C1=Encrypt(m,public key,r1).

Decryption: m=Decrypt(C1,private key)

Re-encrypt: choose random r2 (used to re-encrypt/re-randomize cipher text)
C2=Re-enc(C1,public key,r2)

Decryption: m=Dec(c2,private key) (may be 2 time decryption to retrieve m)

Note:
I want to  generate decryption key from receiver environmental variable(i,e from ip address etc), so that it can automatically decrypt when received by correct machine and the algorithm must have some random number in encryption used to re-encrypt (randomize) cipher text. I want re-encrypt cipher text without knowing the private key.
ElGamal: ElGamal meets all the above requirements exactly.
(I want some other cryptosystem like ElGamal)
RSA: I try RSA but RSA haven't used random r for encryption, so re-encrypting cipher text will issue. Is there solution for RSA?
Paillier: Another public key cryptosystem, have used random r and hence can have possibility to re-encrypt cipher text but the issue is private key lambda, lambda =LCM(p-1,q-1). So it can not be environmental key(because it is dependent on p and q). How to resolve this.
Is there alternate solution?
Any suggestion will be appreciated.

With Paillier, it's easy; generate a random encryption of 0 ($r^n \bmod n^2$ for random $r$ r.p to $n$), and then homomorphically add it to the encryption (that is, $C2 = C1 \cdot r^n \bmod n^2$), and you're done (and all you need is the public key).

I don't believe RSA allows this as a possibility...


Initialize the eight working variables SHA256 I have a little confusion in understanding explanation of SHA256 by FIPS

a, b, c, d, e, f, g, h

are being initialized as (this is what i don't understand)

  2 . Initialize the eight working variables, $a,b,c,d,e,f,g,$ and $h$, with the $(i-1)^{st}$ hash value:

  $\ \ \ \ a = H_0^{(i-1)}$
   $\ \ \ \ b = H_1^{(i-1)}$
   $\ \ \ \ c = H_2^{(i-1)}$
   $\ \ \ \ d = H_3^{(i-1)}$
   $\ \ \ \ e = H_4^{(i-1)}$
   $\ \ \ \ f = H_5^{(i-1)}$
   $\ \ \ \ g = H_6^{(i-1)}$
   $\ \ \ \ h = H_7^{(i-1)}$

cause with this, in stage 1 of iteration, variables

a, b, c, d, e, f, g, h

would have (pre-defined) Initial Values of H. But in Calculation Stage of these variables there is no use of next stage Intermediate Hash Values H.

  3 . $For\ t=0\ to\ 63:$
  $\ \ \ \ \{$
  $\ \ \ \ \ \ \ \ T_1=h+\sum_1^{\{256\}}(e)+Ch(e,f,g)+K_t^{\{256\}}+W_t$
  $\ \ \ \ \ \ \ \ T_2=\sum_0^{\{256\}}(a)+Maj(a,b,c)$
  $\ \ \ \ \ \ \ \ h=g$
  $\ \ \ \ \ \ \ \ g=f$
  $\ \ \ \ \ \ \ \ f=e$
  $\ \ \ \ \ \ \ \ e=d+T_1$
  $\ \ \ \ \ \ \ \ d=c$
  $\ \ \ \ \ \ \ \ c=b$
  $\ \ \ \ \ \ \ \ b=a$
  $\ \ \ \ \ \ \ \ a=T_1+T_2$
  $\ \ \ \ \}$

and what I see Intermediate Values are calculated with Variables not the other way around.

  4 . Compute the $i^{th}$ intermediate hashvalue $H^{(i)}$:

  $\ \ \ \ H_0^{(i)}=a+H_0^{(i-1)}$
   $\ \ \ \ H_1^{(i)}=b+H_1^{(i-1)}$
   $\ \ \ \ H_2^{(i)}=c+H_2^{(i-1)}$
   $\ \ \ \ H_3^{(i)}=d+H_3^{(i-1)}$
   $\ \ \ \ H_4^{(i)}=e+H_4^{(i-1)}$
   $\ \ \ \ H_5^{(i)}=f+H_5^{(i-1)}$
   $\ \ \ \ H_6^{(i)}=g+H_6^{(i-1)}$
   $\ \ \ \ H_7^{(i)}=h+H_7^{(i-1)}$

Can you please explain to me how 2. Stage (Initialization) fit in Iteration Process of SHA256.

The variables a, b, c, d, e, f, g, h are assigned on each round of the compression function main loop, but the interim hash values are considered only per message chunk (i.e. after all rounds have completed)

I found the Wikipedia pseudo-code easier to understand than the description in your question, and it is clear there how the variables relate to interim hash values. Note where your reference relates previous hash components $H_0^{(i)}=a+H_0^{(i-1)}$ the pseudocode just assigns h0 = a + h0, because there is no need to keep previous hash values, just a current one which is updated after processing each chunk.

Just before calculating the rounds for the each chunk, both the current H array and a, b, c, d, e, f, g, h hold the same data. This changes during calculation of the rounds, and you need to keep the value of H so it can be added back in at the end of the chunk.

When starting the first message chunk, before any processing rounds, H and a, b, c, d, e, f, g, h hold the "initial values of H" (based on square roots of first 8 primes). You do not use those initial values again.


Steganographic embedding of an RSA-encrypted message into an image The goal is to combine the RSA encryption system with the LSB steganography system in a BMP image. Since every pixel of the image is an integer between 0 and 255, if we choose $p$ and $q$ such that $N = p \cdot q > 255$, how could a message encrypted with $RSA$ be embedded in the image?

If I'm reading your question correctly, you want to hide an RSA encrypted message within a 256x256 BMP file and you're wondering how this can be done as each pixel only has a range of $[0;255]$.

This is fairly easy, as your message is likely to be shorter than the $256\times256=65536$ least significant bits at your disposal.

You first simply encrypt the message you want to send using standard RSA. This will usually result in a cipher text of length 2058 bits. You then go ahead and inspect the first (= least significant) bit of the cipher text. If it is $0$, you set the least significant bit of the first byte in the first row to zero. If it is $1$, you set the least significant bit of the first byte in the first row to $1$. You repeat this until you reach the end of your cipher text and go until the end of the row. If you reach the end of the row, you go ahead and continue in the next row. Once you reach the end of the cipher text you'll just treat the rest of the message as $0$.


Non-outsourceable digest-free signature scheme Given a message $M$, I am looking for a signature scheme that does not involve first computing the digest $H(M)$ and then signing $H(M)$. Signature schemes on digests are outsourceable in the sense that the private key holder does not need custody of $M$ while signing (the digest $H(M)$ suffices and can be generated by a third party).

For context, I am trying to build a "proof of custody" scheme, where some private key holder proves he also had the original message $M$ in full at the point of signing.

I will be basing this construction on Schnorr signatures, since I am most familiar with those. I will also use elliptic curve, for the same reason; see ECDH.

Recall:

Schnorr signatures are a Fiat-Shamir transformation of the Schnorr identification protocol. Fiat-Shamir transforms an interactive proof of knowledge into a signature.
The Schnorr identification protocol (interactively) proves the knowledge of a discrete logarithm; i.e., Alice (who signs $m$) has access to a secret key $x$, with corresponding public key $Y=xG$. Now $x$ is said to be the discrete logarithm of $Y$.

Applying this terminology to your question, I would say we want to prove that Alice has access to $m$ and $x$. Alice can, for example, prove that she knows the discrete logarithm $ms$ of $mxG=mY$. She can do this by applying a regular Schnorr signature using public key $Y'=mY$ and secret key $x'=mx$:

Let $k$ be a random field element; set $R = kG$.
Let $e=\mathcal{H}(R)$
Let $s=k-x'e=k-mxe$

The signature is $(s,e)$. Bob verifies:

Let $R_v=sG+eY'=sG+emY$
Let $e_v=\mathcal{H}(R_v)$

The signature is valid iff $e=e_v$, since $R_v=sG+eY'=(k-mxe)G+emY=kG-mxeG+emxG=kG$.

Of course, this supposes that it is feasible to multiple your (potentially large) message $m$ with the secret key. This also assumes that $m<q$ (smaller than the order of the field $\mathbb{F}_q$, since Eve can otherwise compress $|m| \bmod q$. You can circumvent this by signing in blocks of size $m_i<q$.


Can one reduce the size of ECDSA-like signatures? Using $n$-bit ECDSA, a signature has a size of $2·n$. It is possible to recover the public key from this signature, which shows that there is a publicly visible redundancy in the signature.

Is it possible to exploit this redundancy to reduce the signature size to $n$ bits, sacrificing key recovery?

I suspect it's not possible, but I don't know enough about elliptic curves to be sure.

ECDSA is actually a kind-of computational zero-knowledge protocol, played by the signer, with a "reduction function" as impartial verifier. For that matter, ECDSA is not very different from plain DSA.

Things basically go this way. There is a known public group $\mathbb{G}$ which I will denote additively, with $G$ as generator, and of size $q$ (a known prime integer). For DSA, $\mathbb{G}$ is the group of integers or order $q$ modulo a prime $p$ ($p$ is a bigger prime, such that $p-1$ is a multiple of $q$) with the multiplication as group law; for ECDSA, $\mathbb{G}$ is an elliptic curve (or a subgroup of an elliptic curve).

The signer knows a secret value $x$, an integer modulo $q$. The public key is $Q = xG$ (for DSA, with the multiplicative notation, public key is $g^x \mod p$). The underlying computational zero-knowledge proof protocol works like this:

Prover wants to prove to the verifier that he knows $x$, but without revealing $x$.
There is a known parameter $h$, a non-zero value modulo $q$.
Prover (aka, the signer) selects a random $k$ modulo $q$, and computes $A = kG$. He sends $A$ to the verifier; this is a commitment (by sending $A$, the prover marks that he has chosen some value $k$, which he will not be able to change later on in the protocol; but he does not actually reveal $k$).
Verifier chooses a challenge $r$ (supposedly random value modulo $q$) and sends it to the Prover. The cornerstone of the protocol is that $r$ is chosen after the commitment (the Prover cannot compute a specific value of $k$ which depends on the value of $r$).
Prover sends back $s = (h+rx)/k \mod q$ where $h$ is a non-zero. The verifier checks that this value matches the commitment and challenge by computing $(h/s)G+(r/s)Q$ which must be equal to $A$.

What goes on here is that the Prover commits to a random value $k$ and then proves that he knows $x/k$ (this is quite similar to the Schnorr identification protocol).

To turn this interactive protocol into a non-interactive signature scheme, we must replace the bit about the random challenge by something which can be computed by the signer alone, yet still be convincing enough about its "randomness" (as I said above, the protocol is good as long as the value $k$ cannot be chosen with a specific challenge $r$ as target); we also need to "inject" the signed message somewhere. So we do the two following things:

We say that the parameter $h$ will be the hash of the signed message.
We define the challenge $r$ to be the result of the evaluation of a given known function $f$ over $A$. The function $f$ can be quite arbitrary as long as it is deterministic and "somewhat uniform" over a big enough range of output value. For instance, if $\mathbb{G}$ is an elliptic curve, we can choose $f(A)$ to be "the $X$ coordinate of the curve point $A$, converted to an integer and reduced modulo $q$".

And, voila! you have DSA (or ECDSA).

The important point here is that the identification protocol is "computationally zero-knowledge" (i.e. yields no usable information on $x$, at least for a computationally bounded adversary) only because $k$ is chosen randomly and uniformly modulo $q$ every time the protocol is executed (i.e. for every signature). Indeed, the protocol does reveal quite a lot of information on $x/k$ (modulo $q$). But, as long as a fresh $k$ is used every time, the attacker is still short of information. In entropy parlance, we could say that $x$ is $n$ bits of entropy, the random $k$ injects $n$ extra bits of entropy, and the protocol reveals $n$ bits; so, if we run the protocol $z$ times, the total entropy is $n+zn$, and $zn$ bits have been revealed, to there still are $n$ bits of entropy unknown to the attacker -- precisely the private key $x$.

The seemingly redundant nature of (EC)DSA signatures comes from that point. We need to inject some entropy in the system, of a size similar to that of $x$. So, for instance, if we use a 160-bit private key $x$, there must be close to $2^{160}$ possible signature values for a given message $h(m)$, and since a signature on a message must not be valid for any other message, we still need $2^{160}$ distincts sets of signatures. Hence $2^{320}$ possible signature values altogether, for a 160-bit private key.

This extra size is consubstantial to the use of an underlying challenge-response identification protocol as the basis for the signature scheme, so we find it also for all kinds of derivative of the Schnorr identification scheme (including Schnorr signatures, ElGamal signatures, KCDSA...).