Exploiting AES with IV similar to password and fixed key While reviewing a 'secure communication protocol' made by a colleague, I noticed a usage of AES-128 CBC that caught my eye. I think they are trying to implement a HMAC but have made some very questionable decisions.

The steps look like this:

The IV is initialized to be the same as a user's (plaintext) password with just one byte changed.
AES CBC takes the password, this IV, and a key as input, however the same key is used each time.
The output of this encryption is then XORed with the original password, giving the user's password hash.

Now presuming I have the key and some hashed passwords, is it possible to obtain the original plaintext passwords, in order to prove to my colleague that this system is horribly broken?

It seems completely possible to break this scheme. Lets take 2 passwords, using some deterministic padding scheme. Now remember that the IV is XOR'ed with the plaintext before encryption:

Now it seems that the output of this XOR operation will only be different by one byte. So if you have enough passwords that are hashed then the input and therefore output of the blockcipher is likely to repeat. Due to the birthday bound repetition is likely with a chance of 0.5 after 16 tries.

One way to take advantage of this as attacker is to create a few accounts with different passwords. The output of the cipher can be retrieved using the output of the password hash, recovered later. It can simply XOR this value with the password given, which will result in the output of the cipher. Then the attacker can XOR this value with the other password hashes until it finds something that looks like a valid password strings (e.g. by detecting if there are no control characters in the output). This way most if not all passwords should be retrievable.

The fun thing with this attack is that you don't even need the key. The adversary just requires a hashing oracle (the server itself) and (parts of the) hash database.


AES and One Time Passwords I have used AES to secure my short term wireless network(1 day lifetime). The same symmetric key is used for securing entire network traffic. is it possible to improve security with onetime password scheme? ie, Again AES encryption,but with different 128 bit keys each time.

Think about it this way.. with AES, you only generate one key, and use that for all encryptions(of the day).., however with OTP a single key won't work and you'll need to have (say) $n$ keys to send $n$ packets securely..

Now, again, you might suggest using a seed with a PRNG to create a $128*n$ bit key for all $n$ packets.. but then here's the problem: You need to maintain states .. the $i^{th}$ packet will only make sense when decrypted with $i^{th}$ key, i.e the string  from $128.(i-1):128.i$, so suppose now you send a message, and somehow, say due to racing conditions in connection, your $(j+1)^{th}$ message reaches before $j^{th}$ message, your server won't be able to decrypt it ..

Also, even simply, PRNGs are key-ed functions (the seed IS the key) .. so you'll need to set that up anyway :)

You can probably come up with many more attacks here.. OTPs, as called, are for ONE TIME USE!! two time's a over kill :D ..


CSPRNG generation vs asymmetric encryption performance It might sound like a weird comparison, but which one is faster, If I were to generate a CSPRNG every time or to sign(private encrypt) a data?

It costs a median of about 300 cycles on a modern x86 system to compute the ChaCha pseudorandom function, generating 64 bytes of output from a 32-byte reusable key and a 16-byte input.

It costs a median of about 50000 cycles on a modern x86 system to compute a 64-byte Ed25519 signature.

These numbers are from https://bench.cr.yp.to/.  The fastest signature schemes reported there still cost over 1000 cycles.

But what on earth are you doing where there is any question of whether you should use a PRNG or a public-key signature?  This is like going to a bicycle shop and asking whether you should buy a wheel or a handlebar.  You should identify what your application's goals, threat model, and security needs are first before you try picking the fastest handlebar for your bicycle.

If I screw up my eyes and stand on my head and take your inquiry to mean that you want some properties of a pseudorandom function and some properties of a signature, maybe you want a VRF—but causing onlookers to have to stand on their heads is no way to build a secure system!

P.S.  Signature is a fundamentally different concept from ‘encrypting with the private key’.


Is OCSP multi stapling supported by OpenSSL? can anyone tell me for sure if OCSP multi stapling is supported by/implemented in the current version of OpenSSL?

Those are the hints I found on the Web:

OCSP stapling now is supported by OpenSSL, see also a security note from 22 September 2016:
https://www.openssl.org/news/secadv/20160922.txt

Mailing list entry from February 2016 discussing it: https://mta.openssl.org/pipermail/openssl-dev/2016-February/005309.html

When looking on the GitHub project, you see a "status_request_v2" entry (the TLS handshake extension for OCSP multi-stapling):
github.com/openssl/openssl/blob/master/crypto/x509v3/v3_tlsf.c#L50

Does anyone have more insight into the current version of OpenSSL regarding OCSP multi-stapling?

Still unsupported.
I think it still is not supported.
From openssl/blob/master/ssl/statem/extensions_srvr.c:
if (s->tlsext_status_type != TLSEXT_STATUSTYPE_ocsp) {
    /*
     * We don't know what to do with any other type so ignore it.
     */
    s->tlsext_status_type = TLSEXT_STATUSTYPE_nothing;
    return 1;
}

And from openssl/blob/master/doc/man3/SSL_CTX_set_tlsext_status_cb.pod

A client application may request that a server send back an OCSP status response (also known as OCSP stapling). ... Currently the only supported type is TLSEXT_STATUSTYPE_ocsp.


Is it possible to deduce the IV from CBC ciphered data, without knowing the key? The question came up here, which left me thinking:

Is it possible to deduce the IV from CBC ciphered data, without knowing the key?
And if not, why is it considered a bad idea to create an IV by, for example, filename$\oplus$Key, if you never store the IV?

I know, that XOR is a no-go, when you are using ciphers, because, XOR is bidirectional. Having the filename and the IV will give me the key. But HOW will you get the IV from CBC ciphered data without having the key first?

For CBC mode, the IV must be

Never used twice with the same key
Unpredictable

So, in your example (filename$\oplus$key), if you ever encrypt two files that have the same filename with the same key, you will violate #1.

Now, you may be tempted to say "but I always generate a new key for every file that I encrypt, so that example doesn't apply". Fine, it doesn't. There are probably some use cases where filename$\oplus$key is fine. But, there are a lot of use cases where this will have big problems. In crypto, we typically try to develop our systems so that they are secure no matter how they are used. This is often not entirely possible, but that is what we aim for. So instead, we would generate a random IV and publish it with the ciphertext.

To give you an example of where filename$\oplus$key could have issues, consider the following. What if you publish your IV (which is a very, very common practice). Then all I have to do is brute force the file name and I have the key.


ECDSA is specified in SEC1. It's instantiation with curve P-256 is specified  in FIPS 186-4 (or equivalently in SEC2 under the name secp256r1), and tells that it must use the SHA-256 hash defined by FIPS 180-4.

I'll leave aside ASN.1 decoration (since the question uses none), conversions between integer to bytestring of fixed width (which all are per big-endian convention), and to hexadecimal¹.

Signing using ECDSA on P-256 takes as input

a private key $d$ (the question's D), which is a 32-byte bytestring
a message, which is bytestring $M$ of $0$ to $2^{61}-1$ bytes
a random number generator

and outputs

a signature $S=(r,s)$ consisting of

an $r$ component (the question's R), which is a 32-byte bytestring
an $s$ component (the question's S), which is a 32-byte bytestring

Verifying a signature using ECDSA on P-256 takes as input

a trusted public key $Q$, which should be a point of curve P-256 other than the point at infinity. It was originally computed as $d\,G$ during key generation. It is defined by its Cartesian coordinates

$x_Q$ (the question's Qx), which is a 32-byte bytestring
$y_Q$ (the question's Qy), which in the question is³ a 32-byte bytestring

a message $M$
the signature $S=(r,s)$ in the form output by the signature process.

and outputs valid (if the message matches the one signed and there was no errors) or invalid (in all other cases except a successful forgery).

The question's message is the 27-character Example of ECDSA with P-256 converted to bytestring per some unspecified convention, likely ASCII or UTF-8. Both yield the same 27-byte bytestring $M$4578616D706C65206F66204543445341207769746820502D323536

Both signing and verification manipulate $M$ only to compute it's SHA-256 hash $H$ (the question's H), which is a 32-byte bytestring. It is converted to an integer $e$ (the question's E), which when using P-256 thus SHA-256 is² $H$.

Signing is per SEC1 section 4.1.3. In a nutshell:

Draw a secret random number $k$ (the question's K) in range $[1,n)$, where $n$ is the order of the curve P-256. It is critically important that $k$ is uniformly distributed on this interval and independent⁴ of other $k$.
Compute the Elliptic Curve point $R=k\,G$ of the curve P-256, where $G$ is the generator point. $R$ has Cartesian coordinates $(x_R,y_R)$ (the question's R_x and R_y), but only $x_R$ is needed.
Compute  $r=x_R\bmod n$ (the question's R). If $r=0$ something went wrong⁵, ⁶.
Compute $k^{-1}$ modulo $n$ (the question's Kinv), that is the integer in range $[1,n)$ with $k\,k^{-1}-1$ a multiple of $n$.
Compute $s=k^{-1}(e+r\,d)\bmod n$. If $s=0$, something went wrong⁵.
Output $(r,s)$.

CAUTION: Signing can be the target of various attacks, e.g. timing or other side channel, and fault injection. Mitigation of these attacks is difficult.

Verification is per SEC1 section 4.1.4. In a nutshell:

Check that the point $Q$ of coordinates $(x_Q,y_Q)$ is an ordinary point of P-256; otherwise, output invalid.
Check  that $r$ and $s$ both are in range $[1,n)$; otherwise, output invalid
Compute $s^{-1}$ modulo $n$ (the question's Sinv), that is the integer in range $[1,n)$ with $s\,s^{-1}-1$ a multiple of $n$.
Compute $u_1=e\,s^{-1}\bmod n$ (the question's U)
Compute $u_2=r\,s^{-1}\bmod n$ (the question's V)
Compute the Elliptic Curve point $R=u_1\,G+u_2\,Q$ of the curve P-256, where $G$ is the generator point, and $Q$ is as determined by the public key. $R$ has Cartesian coordinates $(x_R,y_R)$ (the question's Rprime.X and Rprime.Y), but only $x_R$ is needed.
If $R$ is the point at infinity, output invalid.
If $e\bmod n\ne x_R\bmod n$, output invalid (see note⁶).
Output valid.

DISCLAIMER: This contains simplifications and likely errors⁷. It is only meant as an aid to understand the standards.

¹ Hexadecimal is only for display purposes in the question and this answer. It's use in application is uncommon, and would waste space.

² Some implementations avoid the rare case $e\ge n$ (where $n$ is the order of the curve P-256) by reducing $H$ modulo $n$ to produce $e$. That changes the outcome of neither signature nor verification, thus does not hamper interoperability.

³ If point compression is used, $y_Q$ is reduced to its low-order bit, which combined with $x_Q$ and the curve's equation is enough to fully define point $Q$.

⁴ In particular, independence precludes reuse. If we want to be standards-conformant, that's including when signing the same message with the same key. However, from a security perspective it is safe, exclusively in this case, to reuse an earlier $k$. In some ECDSA variants, that's used to generate $k$ as the output of a Pseudo Random Function keyed by $d$ with input $H$.

⁵ It is then advisable to consider this an attack and erase/zeroize/burninate the private key, although the official thing to do is to try another $k$.

⁶ In overwhelmingly most cases occurring absent attack or deliberate test, $x_R<n$. The official thing is to handle the contrary unmoved, but it is a corner case worth consideration, if only to handle it as above⁵ during signature. The case $e\ge n$ is rare² (like one in four billion), but comparatively very common.

⁷ Thanks to dave_thompson_085 for pointing some of the many errors I made, as usual; and pardon the endless stream of edits.


Real-world offline phase implementation in MPC setting I've been reading up on various basic MPC primitives (multiplication, inversion, exponentiation and so on of secrets shared between multiple parties).
One of the problems of implementing MPC in real-world is performance. One of the common solution trends is splitting of the protocols into offline (preprocessing) and online phases.
The more complicated and resource-intensive a computation is, the more we win by offloading it into the offline phase... and I am trying to imagine what would that mean in practice:
I am imagining a constant stream of requests for some "business" functionality (say, for example, for computing AES), each of which requires for some (potentially multiple) preprocessed data pieces (say, Beaver Triples) to have already been prepared in the offline phase... so, basically, an even (computationally) bigger stream of "offline" processing to be happening in the background...
My own vision includes either computing such offline resources in background when the "business" load is lower, pooling those in some storage (which is also sensitive, I guess?) or trying to offload the preprocessing into separate processes (servers?).
So, my main question is:
Are there any works/guidelines that discuss the way to implement such offline phase(s) in practice?

I don't think there are some guidelines as such. However, different approaches have been considered.
A common consideration across several implementations that aim at making these things more accessible in practice (e.g. TF-Encrypted, or PySyft) is to consider a third trusted party that distributes the necessary preprocessing material before the computation starts. This, however, introduces different security assumptions and generates new potential points of failure.
Another approach that has been suggested in the literature consists of letting a set of servers produce triples "as a service" towards the servers requiring the computation. This would reduce the single point of failure that an individual preprocessing producer would imply.
This is all, however, research literature. I am not aware of any actual deployment of protocols with heavy preprocessing, nor any guidelines about how to do so. Also, there is an argument that this idea of the preprocessing not "mattering" so much, due to it being input-independent, is not that valid in practice. For actively secure 2-party protocols, the preprocessing can really take a large amount of time with respect to the online phase, so in a real scenario in which you get a constant flow of computation requests, it is more accurate to count end-to-end running times.
Finally, heavy preprocessing times are common in the dishonest majority setting, but when you're willing to assume that the adversary corrupts at most a strict minority of the parties, we can find protocols with very cheap preprocessing, or even no preprocessing at all. This is common in the $3$-party setting (with $1$ corruption), so I'd expect a real deployment in practice to make use of one of these settings, instead of, say, $2$ parties.


Specification of the Megamos crypto algorithm It has recently emerged that a paper that was scheduled to appear at Usenix Security 2013, titled "Dismantling Megamos Crypto: Wirelessly Lockpicking a Vehicle Immobiliser", has been censored according to a newspaper article in the "Guardian".

A court in the UK issued a temporary injunction barring the scientists from publishing their paper.  Based upon the newspaper article, it sounds like the paper describes how to break Megamos, a crypto algorithm that is used in several luxury cars — "including Porsche, Audi, Bentley and Lamborghini".

That same newspaper article indicates that software for Megamos has been available on the Internet since 2009.

Does anyone know what the Megamos algorithm is?
Is there a specification of the algorithm that is publicly available, or any publicly available code that implements it?

As cybergibbons notes in his answer, the court decision itself is quite interesting reading.  In particular, while the details of the "Megamos algorithm" itself are obviously not given in the court decision, the manner in which it is used is described in a surprisingly clear manner in paragraphs 4 and 5:

"In detail the way this works is as follows: both the car computer and the transponder know a secret number. The number is unique to that car. It is called the "secret key". Both the car computer and the transponder also know a secret algorithm. That is a complex mathematical formula. Given two numbers it will produce a third number. The algorithm is the same for all cars which use the Megamos Crypto chip. Carrying out that calculation is what the Megamos Crypto chip does.
"When the process starts the car generates a random number. It is sent to the transponder. Now both computers perform the complex mathematical operation using two numbers they both should know, the random number and the secret key. They each produce a third number. The number is split into two parts called F and G. Both computers now know F and G. The car sends its F to the transponder. The transponder can check that the car has correctly calculated F. That proves to the transponder that the car knows both the secret key and the Megamos Crypto algorithm. The transponder can now be satisfied that the car is genuinely the car it is supposed to be. If the transponder is happy, the transponder sends G to the car. The car checks that G is correct. If it is correct then the car is happy that the transponder also knows the secret key and the Megamos Crypto algorithm. Thus the car can be satisfied that the transponder is genuine. So both devices have confirmed the identity of the other without actually revealing the secret key or the secret algorithm. The car can safely start. The verification of identity in this process depends on the shared secret knowledge. For the process to be secure, both pieces of information need to remain secret - the key and the algorithm."

Translated (back) into standard crypto terminology, it appears that the "Megamos algorithm" is an (evidently failed) attempt to implement a pseudorandom function family (PRF).
Specifically, the authentication protocol described in the paragraphs above can be rephrased as follows:

Both the car computer $\rm C$ and the transponder $\rm T$ hold a shared secret key $K$ and a pseudorandom function family (implemented using the Megamos algorithm) $\sf PRF$, of which ${\sf PRF}_K$ is a specific instance parametrized by the key $K$.  The PRF outputs a bitstring that is split into two parts, $F$ and $G$.  To perform an authentication exchange:

$\rm C$ chooses a random number $r$ and computes $(F,G) = {\sf PRF}_K(r)$.
${\rm C \to T:}\ r, F$
$\rm T$ computes $(F',G') = {\sf PRF}_K(r)$ and aborts unless $F = F'$.
${\rm T \to C:}\ G'$
$\rm C$ verifies that $G = G'$.

Now $\rm C$ and $\rm T$ have verified that they can each compute ${\sf PRF}_K$, and therefore hold the same key $K$.

An interesting feature of this protocol is that, since $r$ is chosen solely by $\rm C$, an attacker who manages to eavesdrop on a legitimate exchange could easily impersonate $\rm C$ by replaying the earlier $r$ and $F$, and could even verify $\rm T$'s response by comparing it with the earlier $G$.  Under the expected usage scenario, this might not be considered a major security risk, since the important part is presumably authenticating $\rm T$ to $\rm C$; on the other hand, since the protocol evidently does try to also authenticate $\rm C$ to $\rm T$, it might simply be that the summary above is incomplete, and that the actual protocol uses some additional mechanism to prevent such replay attacks.
That said, other than the flaw described above, the protocol seems solid provided that $\sf PRF$ is indeed a secure pseudorandom function family.  In particular the assertion in the court decision that "[f]or the process to be secure, both pieces of information need to remain secret - the key and the algorithm" appears patently false: if the algorithm were a secure PRF, such as, say, AES-CMAC-PRF-128, the protocol described above would be secure as long as just the key $K$ was kept secure.
Indeed, the same holds regardless of the details of the protocol: by definition, any instance of a secure pseudorandom function family is indistinguishable from a truly random function, as long as one does not know the key used to choose the instance.  Thus, by definition, the choice of the algorithm, or the manner in which it is used, does not matter as long as it's a secure PRF: they all look identical to anyone who doesn't know the key.  Indeed, there are many published and freely usable PRF algorithms that have withstood extensive public scrutiny and cryptanalysis, and are in common use worldwide.  By failing to publish their own algorithm (or to use one of the already published algorithms), the makers of the Megamos Crypto chip have not only violated Kerckhoffs' principle, but also deprived themselves of this scrutiny by the global crypto research community.
All that said, I can easily enough understand why they may have chosen to do so: the Megamos Crypto chip is designed to be embedded into a car key, with all the attendant limitations on memory capacity and power consumption.  Implementing standard crypto primitives like AES on such small, low power devices is often a challenge, and of the few crypto algorithms specifically designed for such devices, most are new and still poorly analyzed, not to mention that even the published designs often end up making questionable tradeoffs in speed vs. security.  The designers of Megamos Crypto may have been hoping that, by designing their own algorithm and keeping it secret, any security weaknesses it may have might not be so easily exploited.
Alas, Kerckhoffs' principle has a habit of reaffirming itself: if there's profit to be made in discovering the algorithm, someone will do so and profit from it.  Indeed, based on the court decision, in this case this appears to have happened long ago, by 2009 (when the algorithm was included in the Tango Programmer tool, sold for €1000 by a Bulgarian company and described in the court decision as being of "clearly murky origin") if not earlier.

By the way, the court decision even quotes some interesting parts of the redacted paper, including the following, which sheds some light on the nature of the weaknesses discovered in the Megamos algorithm:

"Unfortunately, our first attack is hard to mitigate. It seems unfeasible to prevent an adversary from gathering two authentication traces. Furthermore, this attack exploits weaknesses in the course of the cipher's design - e.g. the size of the internal state. It would require a complete re-design of the cipher to fix these weaknesses. To that purpose, lightweight ciphers, like grain, and so on, have been proposed in the literature and could be considered as suitable replacements for the Megamos Crypto. On the positive side, our first attack is more computationally intensive than the attacks in section 6 and 7, which makes it important to take the aforementioned mitigating measures in order to prevent the more inexpensive attacks."

Earlier in the text, the defendants also note in their case (paragraph 19(xiv)) that:

"The attack based on the Megamos Crypto algorithm still requires the criminals to have a car, plus a key, plus two days to use a computer program which tries out a lot of possibilities."

From the phrasing, and from the suggestion of Grain as an alternative, it appears that the "Megamos algorithm" may in fact be some kind of a stream cipher.  This does make sense, insofar as, with the input somehow combined with the key, a stream cipher may be regarded as PRF with arbitrary-length output.  Stream ciphers, despite their limitations as crypto building blocks, also still remain very popular as crypto primitives for low-end systems.
The attack itself appears to be some kind of a related-key attack based on comparing the output of the cipher for two different random nonces (which are made known during the authentication process) and presumably involving some kind of "informed brute force" enumeration of the internal cipher state in order to recover the secret (fixed) part of the cipher key.  Or at least, that's what it looks like based on the court decision.


Is there any existing obfuscation scheme that makes cipher text indistinguishable from plain text? Suppose a totalitarian government (in the name of anti-terrorism / protection of intellectual property):

has outlawed encryption itself - encryption is only approved for cases where the state has reviewed the design and made sure it can decrypt/inspect the message, and made any unapproved encryption a criminal offense
has total control over anything in and out of the network at ISP-level, as well as anything that passes through web services

How could two citizens Alice and Bob, using approved (and monitored) instant messaging service to set up a secure line of communication, conceal the fact that the communication is encrypted, i.e. to make it indistinguishable from unencrypted data, or at least, make it computationally- or financially-infeasible to distinguish it from plain text?

For example, no one would assume the following message to be encrypted:

  Across the Great Wall, we can reach every corner in the world.

But it would be assumed that the following is:

  WZ2A805Wq3rzpiuzE+ZCulgDrn76pVRW5PVUJ4DDadFQD4P9PsTeegbo5CAkqI4yZrO//p
  sYT+ZQkqZ6IrSGng==

  599D80F34E56AB7AF3A62BB313E642BA
  5803AE7EFAA55456E4F5542780C369D1
  500F83FD3EC4DE7A06E8E42024A88E32
  66B3BFFE9B184FE65092A67A22B4869E

For the purpose of this question, we assume the following technical details:

the IM service is text-only, binary data is not allowed (in an IM setting, sending primarily small binary fragments back and forth would probably raise suspicion anyway)
communication between Alice and the IM service, Bob and the IM service, are both end-to-end encrypted. A government agent Eve has a copy of the decryption key the IM service used
proof that the message is encrypted is not required. I.e. Eve does not need to know the plain text or the algorithm used to produce the cipher text. She only needs to tell, with a reasonably-low false-positive rate, if a message is the result of an encryption
the endpoint is secure, no backdoor or malware on the computer/router, etc.

I'd like to know if there are any reliable research on this, is it feasible or not, and if feasible, any existing protocol or algorithm developed for this?

Eve, in case you are watching, I'm asking this for academic purposes only.

As was mentioned, what you're asking for is a form of steganography,which may or may not use encrypted content.

The classic approach derives from talking around the subject (Crimes and Spies) as in:

"The Apple crates are Golden Delicious. There are 15 crates."

A more technical approach I've seen is  Spam Mimmic

Spam Mimmic encode:  Bob, meet me at the secret lair at 1900.

Spam Mimmic decode:

  Dear Friend , We know you are interested in receiving  red-hot news !
  This is a one time mailing there is  no need to request removal if you
  won't want any more  . This mail is being sent in compliance with
  Senate  bill 1626 ; Title 1 , Section 307 ! THIS IS NOT MULTI-LEVEL
  MARKETING ! Why work for somebody else when you can  become rich
  inside 31 DAYS ! Have you ever noticed  the baby boomers are more
  demanding than their parents  plus how many people you know are on the
  Internet !  Well, now is your chance to capitalize on this . WE  will
  help YOU use credit cards on your website plus  increase customer
  response by 120% ! You can begin  at absolutely no cost to you ! But
  don't believe us  . Mr Anderson who resides in Montana tried us and
  says  "My only problem now is where to park all my cars"  ! We are
  licensed to operate in all states . For the  sake of your family order
  now ! Sign up a friend and  you'll get a discount of 10% . Thanks .
  Dear Internet  user , This letter was specially selected to be sent
  to you ! If you are not interested in our publications  and wish to be
  removed from our lists, simply do NOT  respond and ignore this mail .
  This mail is being sent  in compliance with Senate bill 1620 ; Title 9
  , Section  303 . This is not a get rich scheme . Why work for
  somebody else when you can become rich within 92 WEEKS  . Have you
  ever noticed most everyone has a cellphone  plus nearly every
  commercial on television has a .com  on in it ! Well, now is your
  chance to capitalize on  this ! We will help you decrease perceived
  waiting  time by 120% and process your orders within seconds  . You
  can begin at absolutely no cost to you . But  don't believe us . Ms
  Ames of Mississippi tried us  and says "Now I'm rich, Rich, RICH" . We
  are licensed  to operate in all states . We urge you to contact us
  today for your own future financial well-being . Sign  up a friend and
  your friend will be rich too . God  Bless ! Dear Web surfer ; This
  letter was specially  selected to be sent to you ! If you are not
  interested  in our publications and wish to be removed from our
  lists, simply do NOT respond and ignore this mail .  This mail is
  being sent in compliance with Senate bill  1619 ; Title 3 ; Section
  301 ! THIS IS NOT MULTI-LEVEL  MARKETING . Why work for somebody else
  when you can  become rich in 41 DAYS ! Have you ever noticed people
  love convenience plus most everyone has a cellphone  . Well, now is
  your chance to capitalize on this !  We will help you deliver goods
  right to the customer's  doorstep and deliver goods right to the
  customer's  doorstep . You can begin at absolutely no cost to you  .
  But don't believe us . Mrs Simpson of Montana tried  us and says "My
  only problem now is where to park all  my cars" ! This offer is 100%
  legal ! DO NOT DELAY
  - order today . Sign up a friend and you'll get a discount  of 50% ! Warmest regards !

It's rather wordy and not practical for heavy use, but it gives you an idea. In general auto generating believable text is very difficult, hence the use of SPAM as it tends to blend in with other unbelievable text.


Poly1305-AES vs AES-GCM What are the advantages of  Poly1305-AES  over AES-GCM? Please note I am not talking about chacha20-Poly1305 that has been widely adopted, including by Google. But I would like to know pros and cons of Poly1305-AES vs  AES-GCM

Poly1305-AES is a message authentication code.  AES-GCM is an authenticated cipher.  So it isn't a meaningful comparison.

But we could compare Poly1305-AES with AES-GMAC, which is a message authentication code.  They're both Carter–Wegman–Shoup MACs built out of the block cipher AES and a universal hash family based on polynomial evaluation with differential probability bounded well below $2^{-100}$.

One essentially inconsequential difference is that Poly1305-AES uses part of its key directly for its universal hash while AES-GMAC passes its key through AES to derive a universal hash key.

The main difference between Poly1305-AES and AES-GMAC is the type of arithmetic used by the underlying universal hash family, Poly1305 or GHASH, respectively:

Poly1305 uses arithmetic in the prime field $\mathbb Z/(2^{130} - 5)\mathbb Z$ which is easy to implement fast in software without timing side channels.
GHASH uses arithmetic in the binary field $\operatorname{GF}(2^{128})$ which is hard to implement fast in software without timing side channels: if you don't have hardware support—or if a bug somewhere deep inside your leaning tower of software in a modern software stack has caused it to fail to take advantage of hardware support—then either your software will be slow, or your software will leak secrets through timing side channels.

Poly1305 is optimized for fast safe software implementations, whereas GHASH is a security risk unless you can guarantee you're using hardware support.  Optimized implementations with hardware support are comparably fast, running at about 1 cpb.

Of course, the same criticism of GHASH applies to AES itself, which is why you should really use ChaCha20-Poly1305 instead of AES-GCM or anything built out of Poly1305-AES.


How difficult is inverting a non-square matrix? Partially inspired by ring learning with errors (RLWE), I am trying to construct a cryptosystem that requires the use of a non-invertible matrix.

Of the methods I've thought of to generate a matrix of determinant $0$, erasing a row/column or two seems the easiest, but I have no idea on how non-invertible this is.

I would like to know about known methods of reconstructing an unknown square matrix with known structure from its product with a non-square matrix.

As far as I know, there is no well-behaved and canonical topology on finite fields that would enable a consistent and useful definition of pseudoinverse. The main point in computing pseudoinverses over the complex or real field is that they minimize some second moment error functional, since there is no unique inverse defined.

However, and I may regret this, but there is a recent 2015 conference paper from the Springer Lecture Notes in Electrical Engineering book series (LNEE, volume 339)[behind paywall] which claims to construct such a beast, subject to some strong conditions, but there is no proof of any error minimizing properties for such an inverse, and I'd be really surprised if it results in a meaningful definition of pseudoinverse for lattice based cryptosystems, though it might be worth looking into. A quick look at the paper titles show that this is a very generic and broad conference, not really focused on cryptography, but that may well not be important.


Why would it be risky to let Huawei build 5G networks? I'm wondering why there is so much debate about letting Huawei build 5G networks in Europe and other countries. Shouldn't encryption which is used more and more on the web today make all communication unreadable? Are people just worried about metadata? Thanks.

There is a political and economic question here:  Who should be granted the power (via economic might or monopoly, via government contracts for building infrastructure, via government endorsement of standards that prefer the technology already in production by one company but not another, etc.) to determine the technology used by the ubiquitous communications infrastructure of telephony?  That question involves issues of consent of the governed, international diplomacy, social rules for power plays, economic theory around monopoly and concentration of power, and so on, and as such is off-topic for crypto.se or security.se, but maybe not for politics.se.

There is a security question here:  What powers does the party in control of the infrastructure has to wreak havoc if their handlers should so request?  If, hypothetically, under pressure by the NSA, Juniper put a remote management back door into all of their firewalls, and if the Chinese power grid's industrial control network or the Chinese agricultural control network were built out of Juniper routers, would that give the United States of Armed Forces a strategic advantage in warfare against China?  That question involves issues of coercion by threat of economic devastation and famine, international diplomacy, and so on, and as such is off-topic for crypto.se, but maybe not for security.se or politics.se.

Finally, there is also a cryptography-related question here: What is the problem with a malicious adversary controlling all the world's networking infrastructure, if all the world's cryptography is designed under the premise of a malicious MITM with the power to intercept, eavesdrop, and forges all the world's traffic?

There are two broad categories of problems that could threaten most applications of crypotgraphy:

A global passive adversary (GPA), who only eavesdrops and never interferes with traffic, enables efficient collection of mass surveillance of metadata in interpersonal communication like Signal.  Most cryptography is designed to conceal the content of conversations, but not the event that conversations happened or when or between whom—as you note, metadata is much harder to conceal.  And metadata collection is invisible to the outside: operationally, the network is still allowing communication to happen.

There are anonymity networks like Tor that aim to conceal metadata with the help of cryptography and a diverse network of operators, but a global passive adversary would also threaten anonymity in low-latency networks like Tor, if the government in control of the GPA is in your threat model.  Of course, we're talking about 5G, not the entire internet, but this is already a problem with the Five Eyes network, which is why you should run Tor nodes in as many different jurisdictions and on as many different networks as you can to diffuse the power to monitor the Tor network.

(Doing this is much easier than persuading everyone to browse the web through high-latency mixnets by email like Richard Stallman does.  And the FVEY or hypothetical Huawei threat doesn't mean Tor is useless: there are many threat models other than the US or Chinese governments against which Tor is useful, like abusive spouses, corporate competitors, puritanical parents, etc.)
A global active adversary like this may have the power to unilaterally deny service to whatever parts of the network they don't like.  See this question for some examples of how availability can be related to cryptography.  Cryptography can detect forgeries or other active attacks, but it can't prevent them.

There are many past examples of internet censorship all over the world.  Most of them are limited in scope essentially to a single geographical region, like the Great Firewall of China, or like when Mubarak cut off the internet in Egypt in a failed attempt to persuade the people how responsibly he wielded power, or like when the United States Senate discusses an internet kill switch for the sake of freedom—except in cases where like when the Pakistani government decided to block YouTube in Pakistan but accidentally the whole world, but a large-scale block that was quickly reversed.

Governments are getting better at making censorship unobtrusive, like asking Baidu to quietly discard politically inconvenient search results for Tianenman Square but otherwise function as desired for the vast majority of queries.  This happens above the level of mere networking gear, but what if you had the power to just make some things unreliable for parts of the world, like making Vkontakte slower than Facebook—or cut off access to a power substation's 5G-connected remote control system at a convenient moment?  Nothing in cryptography can detect these latent powers, nor prevent the consequences of exercising it.
And, of course, cryptography engineering for end-to-end authenticated encryption in applications takes work and a lot of systems just don't have that work put into them because the economic incentives aren't there.  We've made enormous strides in getting billions of people to use more or less end-to-end authenticated encryption for personal messaging in systems like WhatsApp and Signal.  What about other applications, like banking, like document management for corporate secrets, like personnel files?

At resourceful companies where security engineers have clout like Google the premise of a secure network may have been discarded in favor of pervasive end-to-end authenticated encryption, but there is no shortage of corporate environments today that rely on a corporate VPN for access control.  If Cisco, or Huawei, or whoever it is, gets essentially exclusive access to the market for 5G, it would be awfully convenient for these corporate networks to be built out of a nice integrated product with 5G and VPN support—and it would be an awfully convenient vector for nationalist industrial espionage or sabotage.


RSA keys are multiplicative inverse in mod phi(n), but also in mod n? I understand that the RSA keys $pk$ and $sk$ are choosen such that one is the multiplicative inverse of the other, in $\mod \phi(n)$

But for the encryption and decryption to work, in other words, that

${m^{pk}}^{sk} \mod n = m$

holds, $pk$ and $sk$ must also be multiplicative inverse to each other in $\mod n$, right?

I understand that the RSA keys $pk$ and $sk$ are chosen such that one is the multiplicative inverse of the other, in $\bmod \phi(n)$

Mostly correct.  Actually, they're always multiplicative inverses modulo $\lambda(n) = \phi(n) / \gcd(n)$; selecting them as inverses modulo $\phi(n)$ does work (they will encrypt and decrypt properly), but using the smaller $\lambda(n)$ also works, and yields smaller key values.

  $pk$ and $sk$ must also be multiplicative inverse to each other in $\bmod n$, right?

That is wrong; $pk \cdot sk \bmod n$ need not be any specific value; there's no reason it needs to be 1.  One trivial example is $n = 85, e = 5, d = 13$; in this case, $e$ is not relatively prime to $n$, hence it doesn't have a multiplicative inverse.

After all, when you look at ${m^{pk}}^{sk} \bmod n$, you're not multiplying by $pk$ or $sk$; you're raising $m$ to the power of $pk, sk$; those are different operations.


What is meant by this notation in the ElGamal key generation process? Alice chooses
i) A large prime $p_A$ (say 200 to 300 digits)
ii) A primitive element $\alpha_A$ modulo $p_A$,
iii) A (possibly random) integer $d_A$ with $2 \le d_A \le p_A-2$.
Alice computes
iv) $\beta_A \equiv \alpha_A^{d_A} \pmod {p_A}$.
Alice's public key is $(p_A,\alpha_A,\beta_A)$. Her private key is $d_A$.

What is meant by the notation $\alpha_A$, $p_A$, and what is meant by a 'primitive element', does it mean a small number or something else entirely?

The subscript $A$ indicates that these numbers ($p_A$, $\alpha_A$, etc.) are the ones involved in Alice's key. In a description of a protocol with more participants each having their own key, Bob's public key would be $(p_B, \alpha_B, \beta_B)$, and so on.

A primitive element of a finite field is a generator for the multiplicative group, i.e. the set $\{1, \alpha_A, \alpha_A^2, \alpha_A^3, \ldots, \alpha_A^{p_A-1}\}$ must be the whole set $\{1, 2, 3, \ldots, p-1\}$ of nonzero elements of the field $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$, i.e. any nonzero element of the field can be expressed as a power of $\alpha_A$. Another way of expressing this property is that $\alpha_A$ must have the order $p-1$ (the largest possible order of an element of the field), which means that none of the $\alpha_A^k$ for $1 \le k \le p-2$ are equal to $1$ modulo $p$.


Is there an algorithm that allows to distribute elements securely between parties? Let's say we have a set of numbers $n = \{ 1, 2, 3, 4, 5, \ldots \}$ and $m$ players ($m < \operatorname{sizeof}(n)$, of course).

I want to know if there's a way for all $m$'s to pick different numbers from $n$ in a way that it doesn't reveal which one did they pick or which ones were picked by the others.

It is doable. Assuming all parties are semi-honest and you have a public key encryption scheme allows threshold key generation and threshold decryption, as well as re-encryption, that is:

$keyGen(\lambda,m)$: given the security parameter $\lambda$ and an integer $m$, output a public key $pk$ and $m$ shares of the secret key, each share is given to a player (each player only knows its own share). The secret key is $sk$ and the $i$-th share is $s_i$.
$Enc(pk;m,r)$: encrypt $m$ with random $r$, using the public key $pk$.
$Dec((s_1,\cdots, s_m);c,i)$: $m$ players jointly decrypt a ciphertext c, and output it to the $i$-th party.
$Reenc(pk;c,r)$: Given $c=Enc(pk;m,r')$, re-encrypt it with a random number $r$, so that the output is a valid ciphertext of the original plaintext (i.e. $Enc(pk;m,r'')$).

Elgamal satisfies the above requirements.

Then the players do the following:

They run $keyGen$ jointly to get the public key and shares of secret key.
The first player $P_1$ encrypt each of $n$ numbers, permute the list of the ciphertexts randomly, passes the permuted list to $P_2$.
Then $P_i$ re-encrypts each ciphertext in the list it received and permute the list randomly, and passes the permuted list to $P_{i+1}$.
$P_m$ re-encrypts each ciphertext in the list it received and permute the list, and publish the final list.
Each party pick a different ciphertext in the list.
From $i=1$ to $m$, the players jointly decrypt $P_i$'s ciphertext and reveal it to $P_i$.

If the parties are malicious, zero-knowledge proofs need to be in place to ensure the parties follow the protocol.


What is the difference between honest verifier zero knowledge and zero knowledge? Zero-knowledge proof systems have three properties: soundness, completeness and zero-knowledge.
I can't understand the definition of "zero-knowledge".
What does "simulate" mean?
And what is the difference between "honest-verifier zero-knowledge" and "zero-knowledge"?

The intuition behind Zero Knowledge is that the Verfifier should not learn something about the secret. That means, that the communication between the Prover and the Verifier ("Transcript") must not reveal any information about the secret. So, there must exist a Simulator, not knowing the secret, that can falsify the transcript between Prover and Verifier. A "real" transcript and a transcript falsified by a Simulator must be indistinguishable. Thus, "simulate" means that the Simulator simulates the communication between a Prover and a Verifier.

Honest Verifier ZK means, that we can expect that the Verifier behaves honestly according to the specified protocol. That is, he does what the protocol specifies. In "normal" ZK, the Verifier can be malicious.
Example: The Graph 3-Color protocol [1]. An honest Verifier chooses a random edge (as the protocol says). A malicious Verifier may choose every time the same edge.

[1] http://www.cs.cornell.edu/courses/cs6830/2011fa/scribes/lecture18.pdf


AES-CTR security if S-boxes substituion is omitted? I understand why s-boxes are needed in general especially when ECB mode is used(because of using the same key for encryption of other blocks)but I wonder if it's still relatively secure if we omit S-boxes substitution step in these circumstances

using AES-CTR mode to make sure the same key with the same blocks will encrypt to different ciphertexts
if we select a total random key

I'm asking since this way it seems that it's like we encrypting in a similar manner(not exactly) to one-time pad encryption since the result of encryption(that will get x-ored with plaintext) will be random. I know that using S-boxes will increase the security but is this way fine for non-top-secret documents, so we can get some extra performance for like embedded devices, without sacrificing too much in terms of security, also what kind of attacks can be used.

An Sbox is a necessary condition for the security of the AES or a similar block cipher but may not be sufficient. We can list all AES operations on a high level as

SubBytes – a non-linear substitution step where each byte is replaced with another according to a lookup table.
ShiftRows – a transposition step where the last three rows of the state are shifted cyclically a certain number of steps.
MixColumns – a linear mixing operation that operates on the columns of the state, combining the four bytes in each column.
AddRoundKey

wonder if it's still relatively secure if we omit S-boxes substitution step in these circumstances

If you omit the SubBytes then the new AES cipher will be a completely linear cipher. That is a complete failure for a block cipher. When the attacker, in the simple attack, gets a known-plaintext then they will set up linear equations in total 128 for any AES. If there is no linear dependency on the equation, then they can solve AES-128 with a single-known plaintext pair.
Your design has no KPA security and in modern cryptography, we at least require CPA security.

using AES-CTR mode to make sure the same key with the same blocks will encrypt to different ciphertexts

I've got two understandings.

You use a new key for each block. This is useless.

one uses so many keys to encrypt messages
Instead of this use OTP with the key that has other problems.
one needs to run the key schedule again and again

Use one key

KPA attack can break this.

this way it seems that it's like we encrypting in a similar manner(not exactly) like one-time pad encryption since the result of encryption(that will get x-ored with plaintext) will be random.

Not really random, linearly depend on the key.
Instead in modern Cryptography what we do, we turn a PRF or PRP into a stream cipher like CTR mode. PFR can work since CTR mode doesn't require the reverse of the PRF. So that we can use one key with one key schedule for a long time. AES-CTR or ChaCha are examples of among the many. AES is believed but not proven to be a PRP. And. remember that for CTR mode one should not use a key-IV pair again.
For file encryption, it is better to use AES-GCM or ChaCha20-Poly1305 which also provides integrity and authentication. AES-GCM is faster since the hardware support like the Intel's AES-NI. The blow in my machine for AES-128 NI
openssl speed -elapsed -evp aes-128-ctr
The 'numbers' are in 1000s of bytes per second processed.
type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes  16384 bytes
aes-128-ctr     556160.77k  1822893.03k  3765397.08k  5115820.71k  5694253.74k  5739358.89k

If there is hardware support for ChaCha and Poly1305 it can beat AES.


Recovering private key from Secp256k1 signatures I've seen many answers here and many articles that says we can recover the private key from reused R signatures.
But, what if the r,s signatures are different in transaction of bitcoin then is there a way we could find the ephemeral Key k used in both the cases and find the private key?

In ECDSA, each signature has its own ephemeral key $k$. If $k$ is generated properly, then no amount of signatures will help you recover the private key. "Proper" generation here means either random uniform selection in the proper range, or an appropriate derandomization process such as the one described in RFC 6979.

If the very same $k$ value is used in two signatures, on two distinct messages, but with the same private key $x$, then the private key is revealed. This is the deadly mistake of Sony back in early 2011 (and the initial motivation for RFC 6979, btw). Indeed, if the two messages are $m_1$ and $m_2$, and both values use the same $k$ values, then the two signatures are $(r,s_1)$ and $(r,s_2)$:
\begin{eqnarray}
  s_1 &=& (h(m_1) + xr) / k \\
  s_2 &=& (h(m_2) + xr) / k \\
\end{eqnarray}
The ephemeral key $k$, and the private key $x$, can then be computed as:
\begin{eqnarray}
  k &=& \frac{h(m_1) - h(m_2)}{s_1 - s_2} \\
  x &=& \frac{ks_1 - h(m_1)}{r} \\
\end{eqnarray}

If the values of $k$ are not reused, but are generated with some bias (i.e. not all values in the $[1,q-1]$ range are selected with the same probability), then the private key $x$ can still be recovered from a set of signatures. If for instance $q$ has size 256 bits, but values of $k$ are always lower than $2^{253}$ (i.e. the top three bits are always zero), then a few hundreds of signatures suffice.

If the values of $k$ are generated with a strong, cryptographically secure source, and with no bias, then there is no known attack against ECDSA that would recover the private key $x$, even if many signatures are known. The first reuse of $k$ out of pure back luck is expected to happen after an average of $2^{n/2}$ signatures for an $n$-bit curve, i.e. never in practice if you use a decent curve.

Also, in Bitcoin, people tend not to sign a lot with any given key. For privacy reason, address reuse is discouraged.


Can I break a random number into two smaller vectors and consider them as two random numbers? I have a cryptographically secured RNG that uses a recommended block cipher to generate the random number. As its output, I receive the random number which is very large, but the application requires the usage of two random numbers, and both of them with smaller bit-size of the RNG output.

Can I split the random number into two smaller vectors and consider them as two random numbers? Is this a recommended practice?

Yes you can.

Suppose that you have a pseudorandom generator that, on some seed $s$, outputs $n$ pseudorandom bits, where $n$ is even. Then on a uniformly random input seed $s$, prg$(s) = r$ can be written $r_1 + 2^{n/2}r_2$, with $(r_1,r_2) \in (\{0,1\}^{n/2})^2$. I claim that both $r_1$ and $r_2$ are computationally indistinguishable from uniformly random elements from $\{0,1\}^{n/2}$.

The intuition behind this is as follows: suppose toward contradiction that some polynomial size algorithm can distinguish $r_1$ from random, when $r_1$ is computed as the $n/2$ least significant bits of prg$(s) = r$, for a uniformly random $s$. Now, you are given an $n$-bit string $r$ and must tell whether it is random or it is the output of the PRG. Just decompose $r = r_1 + 2^{n/2}r_2$, and run your distinguisher on input $r_1$: if it tells you that $r_1$ is non-random, then $r$ is non-random (as the distribution of uniformly random $n$-bit numbers is perfectly equal to the distribution obtained by picking two uniformly random $n/2$-bit numbers $r_1,r_2$ and computing $r$ as $r_1 + 2^{n/2}r_2$), hence you can distinguish outputs of the PRG on random seeds from random $n$-bit values, contradicting the fact that the PRG is cryptographically secure. The same argument shows that $r_2$ cannot be distinguished from random.

More generally, fix any size-$k$ subset $S$ of $\{1, \cdots, n\}$, for some $k \leq n$; a similar argument shows that the $k$-bit string obtained by running a secure prg on a random seed, and taking the $k$ bits of the output indexed by $S$, is computationally indistinguishable from random (and the distinguishing advantage of any polytime adversary is at most equal to its distinguishing advantage against the PRG). You can have a bunch of random-looking bit strings just by considering any partition of the bits of your PRG output.


Are chosen-prefix collisions for SHA-1 a major threat? GPG signing of Git commit tags relies on the collision resistance of SHA-1, which is weak.  However, the attacker does not get to choose the prefix.  How much does this translate to an actual vulnerability?

This is the same issue as with MD5, so you can search for attacks on that scheme.

An attacker can create executables that can do one thing during testing and another during deployment by replacing one file by another. As the signature doesn't change, the files in the repository would still validate. If you have a changed file then it is pretty easy to execute an entirely different code path when an application is run.

You would have to analyze the entire (sub-)system to see the impact of such a vulnerability on the system itself. I'd say that a well maintained Git repository isn't as vulnerable as e.g. GPG. It's probably not that easy to simply replace files that are already within a Git repository (but you'd better ask a Git expert instead).

In general signature generation and validation through message digest values are most vulnerable to attacks on the hash functions.


server aid secure equality test The scenario is like this:

$P_1$ has $m_1$, $P_2$ has $m_2$, they want to compare whether $m_1=m_2$ via the server $S$. After the protocol, only $S$ knows the result, and there is no interaction between $P_1$ and $P_2$.

An example solution:

$P_1$ encrypts $m_1$ with his public key $PK_1$; Then he sends $E(PK_1,m_1)$ and $PK_1$ to $S$; ($E$ is additively homomorphic)
$S$ forwards $E(PK_1, m_1)$ and $PK_1$ to $P_2$;
$P_2$ encrypts $m_2$ with $PK_1$, and calculates $E(PK_1,m_0) = E(PK_1, m_2-m_1) = E(PK_1,m_2) - E(PK_1,m_1)$; Then he sends $E(PK_1, m_0)$ to $S$;
$S$ does an oblivious decryption with $P_1$ to get $m_0$, and checks whether $m_0=0$

But in step 2, a malicious $S$ can sends $E(PK_s, 0)$ and $PK_s$ to $P2$ ($S$ knows the decryption key $SK_s$). Then $S$ will get $E(PK_s, m_2)$ from $P_2$, so that he will get $m_2$.

How about hashes?

$P_i$ choose random numbers $R_i$ that they exchange through $S$.
They calculate $H_i = H(R_1|R_2|m_i)$ that they give $S$.
If $H_1 = H_2$, then $S$ can be reasonably sure $m_1=m_2$.

Assuming $H$ is a strong cryptographic hash function and $R_i$ are long enough to avoid collisions (e.g. 256 bits), the worst the server can do is a brute force attack to find $m_i$. Giving an incorrect $R_i$ will only cause the equality check to fail.


Authenticated Encryption mode & AEAD I'm studying Authenticated encryption with Associated Data (AEAD).

My questions are

About AE - I heard that when it comes to Encrypt-then-MAC, if an attacker forges the ciphertext then he gets the wrong MAC value and can't decrypt the ciphertext to plaintext. Is this correct? If so, what is happening Encrypt-and-MAC and MAC-then-Encrypt? Isn't there a filter like Encrypt-then-MAC that filters out invalid ciphertext?
Questions about the history of AE and AEAD. I wonder what the limitations of AE have led to the emergence of AEAD. In some papers, the limitation of AE is that it cannot effectively authenticate by binding associated data to ciphertext. If so, I would like to ask the following question: "Do I have to bind the associated data to the ciphertext?"
About AEAD. The input of the encryption process is key, nonce, plain text, and associated data, and goes through some algorithm to return a ciphertext and a tag for authentication. The input of decryption process is key, nonce, ciphertext, associated data, tag, and plaintext if authentication is completed successfully, and an error is returned if there is a problem. However, for attackers, the key is not known during the decryption process. Moreover, I thought nonce was not even known by the attacker. In my opinion, the only information the attacker knows during the decryption process is ciphertext, related data, and tags. So, is the attacker attacking without knowing both key and nonce? So is AEAD called a strong cryptographic algorithm?

I heard that when it comes to Encrypt-then-MAC, if an attacker forges the ciphertext then he gets the wrong MAC value and can't decrypt the ciphertext to plaintext.

Indeed, a forged ciphertext would immediately imply a forge on the MAC used therefore if the MAC is secure, the system is unforgeable.

  If so, what is happening Encrypt-and-MAC and MAC-then-Encrypt?

They both also achieve authenticated encyption if done properly (that is if "tidiness" is achieved and you treat the nonce explicitly). However in the other cases there is a simple counter-example to these constructions' AE security: Namely pick a CPA-secure encryption scheme and append an unchecked random bit. Now for the attack, simply flip that bit and you get a "different" ciphertext which the decryption oracle will happily decrypt.

  Do I have to bind the associated data to the ciphertext?

No, you don't have to bind associated data to the ciphertext. However, if there's context that needs to be sent publicly (such as routing information) or that is known by both parties and important to the state of the protocol (such as the current packet index), using associated data is a neat mechanism to conveying the correctness of the current state.

  So, is the attacker attacking without knowing both key and nonce?

No, it's usually assumed that the adversary can see and change the nonce if they want to (which is why it must be MAC'ed as well). Also in common security definitions the adversary has access to a pre-keyed encryption / decryption function so they have some sort of "access to the key" though not directly.


Can we construct fully homomorphic encryption scheme based on non-circuit approach? At present, all FHE scheme are be constructed based on circuit approach. Can we construct fully homomorphic encryption scheme based on non-circuit approach?  Is Polly cracker non-circuit approach ?

Is Polly cracker non-circuit approach?

Polly Cracker is non-circuit.

  Can we construct fully homomorphic encryption scheme based on non-circuit approach?

The best info for this I could find comes from a recent paper proposing a non-circuit approach due to Xiao, et al..

They identify a number of non-circuit systems, but go on to say that "they all either have been broken or lack conclusive security evidence."

They then propose a symmetric system which reduces to the problem of factoring.

So it seems that the answer is yes, one can be constructed. It is still an active area of research, however, and I personally wouldn't use the proposed systems yet.

Now, what I am exactly not quite sure of is what non-circuit means? In the paper I reference, they state:

  The main works on homomorphic encryption algorithms are circuit based. They develop the encryption schemes and computation algorithms considering a single bit plaintext. All operations on various operand types can then be achieved by constructing the corresponding circuits.

So is a circuit approach simply that the cryto algorithms assume a single bit plaintext? If that is the case, then there are many, many more FHE systems which are "non-circuit". In fact, the BGV system does not require single bit plaintexts. So perhaps I am missing something in the circuit vs non-circuit discussion.


What is the importance of Modular arithmetic in cryptography? Why do we use modular arithmetic so often in Cryptography?

A few reasons:

As mentioned, modular arithmetic allows groups. See @mikeazo's answer.
Cryptography requires hard problems. Some problems become hard with modular arithmetic. For example, logarithms are easy to compute over all integers (and reals), but can become hard to compute when you introduce a modular reduction. Similarly with finding roots.
Cryptography is implemented digitally. It is nice if values can't be of arbitrary size. If you work with modular arithmetic, you have guarantees about the largest value you will see and can allocate the correct amount of space to hold values.


Generating cyclic group for Ciphertext-Policy Attribute-Based Encryption I am doing Project under the topic CP-ABE.I need to generate a symmetric bilinear group Go of prime order p and with generator g...Then how to choose random elements from Zp....kindly anyone help me...Is it possible to do this with Java?

There are libraries allowing to do that:

PBC: C library
JPBC : Java library

Hope it helps.


Is the dealer a volunteer in Shamir secret sharing scheme? In this Paper, Shamir secret sharing scheme  there is one dealer and n players. The dealer gives a share of the secret to the players, but only when specific conditions are fulfilled will the players be able to reconstruct the secret from their shares. The dealer accomplishes this by giving each player a share in such a way that any group of t (for threshold) or more players can together reconstruct the secret but no group of fewer than t players can. Such a system is called a (t, n)-threshold scheme (sometimes it is written as an (n, t)-threshold scheme).
I found that everyone who is participating in the secret sharing scheme has some benefit. For suppose, participants can able to get shares and reconstruct the secret, which they didn't know in prior. But, for a dealer, I feel that there is no benefit or purpose for itself to participate in the whole system since the dealer knows all the things in prior and is just doing its role to make the scheme work.
Is it true? Is the dealer a volunteer in Shamir secret sharing scheme?
If no then what is the purpose for him to involve in the scheme?

If no then what is the purpose for him to involve in the scheme?

This sort of "why would someone perform this protocol" question is something that crypto does not address.
Perhaps the dealer is the author of his own will, and he is delivering shares of it to his inheritors (for them to recombine after his untimely death).  Perhaps he is the owner of a cryptocurrency purse, and is distributing shares of his private key to save as backups (so that, even if one of his backups is stolen or lost, he's still safe).  Perhaps he is an HSM, and is distributing shares to the key that unlocks the administrator account.
To the protocol, the "why" question doesn't really matter.


Calculate the Number of active s boxes I really want to learn how to calculate the number of active s _boxes for block cipher cryptographic algorithms.
I want to do that manually after running each round of an algorithm such as LED algorithm, what should I notice or compare in order to calculate the number of active s_boxes ?
I read that definition ".You run the algorithm with two different plaintexts (whose difference is usually small – just a few bits, everything else being equal).

Wherever these plaintexts lead to different inputs to an S-box (in any layer/round of the algorithm), we call this S-Box “active” (since the other S-boxes produce the same result for both plaintexts, they are called “passive” and are not considered further)"", and want to learn how to calculate the number of differential active s_boxes?

If you want to do this manually as stated in your question the approach would be similar to this:

choose an input difference $\alpha$ compute the active input sboxes $n_0$ as the number of sboxes that have a non-zero input difference,
when $\alpha$ is the input difference
choose an plaintext $p_0$ and $p_1 = p_0 \oplus \alpha$

compute one round of encryption to get $t^1_0$, and $t^1_1$
compute $\gamma_1 = t^1_0 \oplus t^1_1$, which is the output difference after one encryption round.
compute the active sboxes after one round $n_1$ as the number of sboxes that have a non-zero input difference, regarding $\gamma_1$
repeat for number of rounds $r$ you want to cover

the number of active sboxes for input difference $\alpha$ is $n(\alpha) = \sum_i n_i$
repeat the full procedure for every possible $\alpha$
the minimum number of active sboxes is $\min_\alpha n(\alpha)$.

Of course, there are more sophisticated ways than this, but if you want to do this manually, it might be a good start to understand the concept.


implication of tweak on bruteforcing a block cipher Consider a KPA attack, where the attacker gets known plain text and the corresponding cipher text. Since the encryption algorithm is known, he can brute force all possibilities of key bits. What is the implication of having additional tweak on brute forcing the algorithm?

Is this correct to say that now the attacker must try $2^k * 2^t$ possibilities, thus increasing the effort required to break the algorithm and so making it more secure?
(where k is number of bits in key and t is number of bits in tweak).

Edit: Assuming tweak is kept secret . And also that my application prepends the tweak string to the plain text while encrypting it , $AES_K(Tweak || plain ) $. Is my above assumption correct ?

Edit 2 : The AES in above is being used as a PRF in Luby Rackoff Construction like any other Format Preserving Encryption mode. So the AES is not exactly an encryption of the plain text but right half of the Feistel Network .(Honestly apologize for multiple edits)

The tweak is generally not secret, i.e. the adversary knows it (perhaps even chooses it, depending on the attack model) and thus doesn't have to try to guess it.  So no, tweaks don't increase the effort to brute force a cipher ... unless of course the tweak is kept secret, in which case it may or may not increase the required effort, depending on how the tweak is mixed into the cipher state.


Why choose an authenticated encryption mode instead of a separate MAC? What are cryptographic reasons to choose an authenticated-encryption mode of operation (such as GCM) over a traditional encryption mode plus an independent MAC, or vice versa?

Assume there is no implementation reason to pick one or the other (crypto library supports both, no backward compatibility constraints, etc).

If you look closely at the definition of authenticated encryption modes, you will see they all are, actually, the combination of symmetric encryption and a MAC.

Using traditional encryption and an independent MAC has a few tricky points, none of them being unsolvable:

The encryption mode will use a key, and the MAC will also use a key; using the same key may trigger unwanted weaknesses (e.g. if the encryption uses CBC mode and the MAC is CBC-MAC). Solution: derive both the encryption key and the MAC key from a "master key" through a Key Derivation Function.
The encryption uses an Initialization Vector, and the MAC may also use an IV of its own. Using the same IV for both may, then again, imply weaknesses, especially since the requirements for both IV may be distinct. Solution: use a KDF to derive two IV from a "master IV"; or use an IV-less MAC such as HMAC (that's the great advantage of HMAC: no IV; hence, it is very hard to get it wrong with HMAC).
A MAC may (theoretically) leak information about the processed data. This is the whole mac-then-encrypt or encrypt-then-mac debate. Solution: encrypt-then-mac is the "right thing" but it is easy to get it wrong by forgetting to MAC the encryption IV and/or the encryption algorithm identifier. SSL/TLS does the "wrong thing" but gets away with it because HMAC is "sufficiently different" from block-cipher based encryption.

An Authenticated Encryption mode is designed to solve these questions and do "the right thing" so that the requirements for the user are as light as possible (e.g. a single IV with just a "non-repeating" clause, not needing unpredictable randomness or uniform distribution).

Summary: authenticated encryption should not be opposed to traditional encryption combined with an independent MAC; authenticated encryption is "combined traditional encryption and independent MAC, done properly".


Proving knowledge of a value and computation that uses it Alice picks random points P and Q in a group where DLP w.r.t. a base point G is hard (I am thinking an eliptic curve, but it doesn't have to be). Alice doesn't know the DLP of those two points.

Alice sends (P,Q) to Bob.

Bob is to pick a random scalar r, and return (r*P,r*Q) to Alice, while keeping r secret.

Is there a way for Bob to prove to Alice that he knows that r, and that the pair of points that he sent her are what she is expecting, but without revealing r?

This looks like your typical Schnorr identification protocol. Here $r$ is some secret value, which we could think of as having two public keys $r\cdot P$ and $r\cdot Q$. You'll probably want to assume that the DLPs wrt base $P$ and $Q$ are hard as well, as otherwise Alice could possible solve one of these two for $r$. Let's just assume the group has prime order $n$.

Now we could proceeds as follows (similar to the questions the @SEJPM referred to):

Bob chooses random $s\in \mathbb{Z}/n\mathbb{Z}$.
Bob sends $(s\cdot P, s\cdot Q)$ to Alice.
Alice chooses random $c\in \mathbb{Z}/n\mathbb{Z}$.
Bob computes $t = (s + cr)\bmod{n}$.
Bob sends $t$ to Alice.
Alice checks that $tP = (s\cdot P) + c(r\cdot P)$ and $tQ = (s\cdot Q) + c(r\cdot Q)$.

If the checks of Alice pass, she will believe that Bob knows the DLP of $r\cdot P$ and $r\cdot Q$. I haven't done a too thorough checking, but the properties of a sigma protocol seem to hold.

Moreover the secrets must both be equal to $(t-s)c^{-1}\bmod{n}$, so they are the same.


Forgery attack for Merkle–Damgård MAC scheme with prefix method Consider a hash function $H$ based on an iterated hash function $H_0$
  with $l$-bit block messages an the Merkle–Damgård strenghtening pad.
  That is, $m||pad(m)$ has a length multiple of $l$ and $H(m)
 =H_0(m||pad(m))$

  We consider the MAC algorithm defined given a $l$-bit secret key K and a
  message m as $MAC_K(m) = H_0(K||m||pad(m))$ where || denotes the
  concatenation operation.

  Show that given the MAC of a known message m the adversary is able to
  output a forgery on a message $m' \neq m$

The solution of the exercise forges MAC for message $m′ = m || pad(m) || m^⋆$
for arbitrary $m^*$. It hashes $m^*$ and uses $IV = MAC_K(m)$.

The problem is that I don't understand how this scheme works. First, what is the $f$ function of the drawing? Is it $H_0$? But then how is it that it is taking two parameters, namely, and $l-block$ and an IV? Also, can you do some math that show that this construction works?

A lot of this is explained well on the wikipedia article.

The function $f$ is called the compression function. It is a function $$f:\left\{0,1\right\}^n\times\left\{0,1\right\}^\ell\to\left\{0,1\right\}^n.$$

That is, it takes as input an $n$-bit value and an $\ell$-bit value, and outputs an $n$-bit value. This function is a building block for the function $H_0$. This function $H_0$ is called a hash function, with the restriction that its input is a multiple of $\ell$ bits. So we can think of it as a function
$$H_0:\left(\left\{0,1\right\}^\ell\right)^*\to\left\{0,1\right\}^n.$$
By definition, $H_0$ is defined as
\begin{align*}
H_0(M_0||\cdots||M_t) &= f(\cdots f(f(f(IV,M_0),M_1),M_2)\cdots,M_t).\\
\end{align*}
So we compute $f(IV,M_0)$, followed by $f(f(IV,M_0),M_1)$, etc.

The function $H$ is a hash function without the length restriction. We build it on top of $H_0$, so to do so we may have to pad the message to have length a multiple of $\ell$. That is, $H$ is a function
$$H:\left\{0,1\right\}^*\to\left\{0,1\right\}^n$$
defined by $H(M)=H_0(M||pad(M))$.

So what is the relation between $f$ and $H$? Well, it can be shown that if $f$ is a collision-resistant one-way function, then $H$ is a collision-resistant hash function. So the idea of the Merkle-Damgard construction is that we can build collision-resistant hash functions from collision-resistant one-way functions.

You can make this hash function into a MAC function by prepending a key, so defining ${\tt MAC}_K(M)=H(K||M)$. The exercise asks you to show that this is not a good idea, i.e. for this MAC we can find forge a signature.

Constructing a forgery:

I feel this is the type of question that becomes hard by overload of notation. The best way (in my opinion) to get through this is to calmly figure out what all this notation means (which the above should help with), and then figure out what the question is asking. This is not always easy.

  Show that given the MAC of a known message m the adversary is able to output a forgery on a message m′≠m

So, what does this mean? We are given a MAC of known message $m$, and are asked to output the MAC of any other message $m'$, as long as $m'\neq m$. Thus, the question can be rewritten as

  Given ${\tt MAC}_K(m)$, compute ${\tt MAC}_K(m')$ for some $m'\neq m$.

Assume for simplicity of the argument that $K$ has length a multiple of $\ell$.
By definition, we have
\begin{align*}
{\tt MAC}_K(m)  &= f(\cdots f(f(f(IV,K),m_0),m_1)\cdots, ..||pad(m)).
\end{align*}

From this, we see that the key is used only once. Moreover, it is used right at the start of the computation. The idea should thus be to choose $m'$ in such a way that the start overlaps with $m$. For example, take some $\ell$-bit message $m'_0$ and take $m'=m || pad(m) || m'_0$. By definition,
\begin{align*}
{\tt MAC}_K(m')  &= f(f(\cdots f(f(f(IV,K),m_0),m_1)\cdots, ..||pad(m)),m'_0) \\
                 &= f({\tt MAC}_K(m),m'_0).
\end{align*}

Hence we know ${\tt MAC}_K(m')$, and $m'\neq m$ since $m'$ is longer. The crux of the argument was appending $m'_0$ to $m$, which is a so-called length-extension attack. You can generalize this to appending any message of any length.


Verify authenticity of TLS/HTTPS communication I have a question regarding https/tls. Lets say a client requests a website from a server via https. The client stores the entire traffic and his secrets to disk. Can i afterwards verify the authenticity of the data in the recording?

To my understanding after the initial key exchange (which is signed by the server certificate) the client and server use the same keys for synchronous encryption and hmac calculation. Thus a malicious client can afterwards (before storing the conversation to disk) generate a fake response and encrypt it with the same key the server would have used.

Is my assumption correct?

Your assumption is correct; after the initial key exchange, everything is done with symmetric encryption.  As the client has the symmetric keys, he can create any transcript he wants, and figure out how it would be encrypted and integrity protected.

TLS was designed to do secure communication; nonrepudiable transcripts were never a design goal.


New Cryptographic Algorithm I was wondering about an algorithm that would take a bitstring as an input, shuffle it and output it. You could use a deterministic RNG to select pairs of bits to swap, using the seed as some sort of password, handing it to people to let them reconstruct the shuffling process. Is this a good idea? Has anyone already thought of this? If not, are there any flaws I would have to bear in mind?
I'm a newbie to cryptography and I don't really know how to approach this.

Excuse my poor English grammar and thank you for your time!

EDIT: I forgot to specify that this is for learning purposes.

They call this a transposition cipher.  Bits commonly have more semantic meaning assembled into characters and numbers, so you may be performing  fractionation specifically.  Also, in cryptography we'd use a CSPRNG for the shuffle rather than a plain RNG for invertability reasons detailed in the link.     Frequency analysis means that it's fairly easy to break though.  Stuff to think about then.

It's a lot to take in, and there are very subtle nuances that mean creating a cipher from scratch is pretty tough. It's better to stick to library functions/ standardised methods /primitives in non scholarly uses.   Hi!


What are the constraints on using GCM with a tag size of 96 and 128 bits? Say we want to use AES (or any other secure 128 bit block cipher) with GCM and a tag size of 96 or 128 bits. I'm assuming an AES key size of 128 bits and an IV size of 96 bits (the default).

NIST SP 800-SP 38D, Appendix C: "Requirements and Guidelines for Using Short Tags" specifies the amount of AAD and plaintext together with the number of invocations for 32 and 64 bit short tags, but not for the larger tag sizes. NIST specifies these properties using a table with the following columns set off to each other:

Maximum Combined Length of the Ciphertext and AAD  In a Single Packet (bytes)
Maximum Invocations of the  Authenticated Decryption Function

Here are the constraints for a 64 bit tag size:

Furthermore, the paper "The Galois/Counter Mode of Operation (GCM)" contains the following equation right at the end (chapter 7: "Security"):

  The results of this analysis show that GCM is secure whenever the block cipher is indistinguishable from random and the condition $q^2l^22^{−142} + q^2l^32^{−147} \ll 1$ is met, where $q$ is the number of invocations of the authentication encryption operation and $l$ is the maximum number of bits in the ﬁelds $P$, $A$, and $IV$.

The Wikipedia page on GCM also has a lot of information and references (but not this information, obviously).

I'm not sure if any subsequent analysis has put a dent into the numbers of NIST or the paper though.

I don't understand where the formula $q^2 \ell^2 2^{-142} + q^2 \ell^3 2^{-147}$ came from.  The power of $\ell$ seems too high; the fractions $2^{-142}$ and $2^{-147}$ seem awfully small; the citation is to an unpublished draft of the original security analysis that is no longer available; the final draft does not seem to support it.

First, let's assume you use sequential 96-bit nonces.  (The story is much more complicated if you have to worry about nonce collisions, and the original authors got it wrong.)  The usual approach to security analysis comes by composing two standard theorems:

Forgery probability of a Carter–Wegman universal hashing authenticator: after $f$ forgeries of messages up to $\ell$ blocks long with an authenticator tag of length $\tau$, the forgery probability is bounded by $$\frac{f \ell}{2^\tau}.$$

The forgery probability bound grows linearly with the number and length of forgery attempts, and drops exponentially in the tag length.

This is the main reason why it is more dangerous to truncate tags of universal hashing MACs like GHASH and Poly1305 than to truncate, say, CBC-MAC tags or HMAC tags, for which the analogous term $f/2^\tau$, not $f\ell/2^\tau$.
Distinguisher advantage from substituting a uniform random $b$-bit permutation for a uniform random $b$-bit function, used to derive the one-time authenticator key for each nonce (PRF/PRP switching lemma): if a random algorithm $A$ (say a forger) making $q$ queries has probability $\Pr[A(f)]$ of success on an oracle for a uniform random function $f$, then its success probability on an oracle for a uniform random permutation $\pi$ is bounded by $$\Pr[A(\pi)] \leq \Pr[A(f)] + \frac{q(q - 1)}{2\cdot 2^b} < \Pr[A(f)] + \frac{q^2}{2^b},$$ or more tightly $\Pr[A(\pi)] \leq \delta\cdot\Pr[A(f)]$ where $\delta = (1 - (q - 1)/2^b)^{-q/2}$.

The forgery probability bound grows quadratically with the number of blocks fed to the oracle (in forgery attempts or encryption queries), and drops exponentially in the block length.

Add in the distinguisher advantage against AES, and note that $q = 1 + (n + f) \cdot (1 + \ell)$ since there's one AES call to derive the GHASH key, one AES call per message to derive the GHASH mask, and one AES call per block.  The result is a bound of $$\operatorname{Adv}^{\operatorname{PRP}}_{\operatorname{AES}} + \frac{(1 + (n + f)\cdot(1 + \ell))^2}{2^b} + \frac{f \ell}{2^\tau}$$ on the forgery probability, or more tightly, $$\operatorname{Adv}^{\operatorname{PRP}}_{\operatorname{AES}} + \biggl(1 - \frac{(n + f) \cdot (1 + \ell)}{2^b}\biggr)^{\frac{-(1 + (n + f)\cdot(1 + \ell))}{2}} \cdot \frac{f \ell}{2^\tau}.$$

What does this mean for specific volumes of data that your application might process?  First, always assume the adversary can attempt more forgeries than the legitimate users will handle data—legitimate users use only as much bandwidth as their needs require, while forgers will saturate the remaining bandwidth attempting forgeries.

Let's consider three different regimes for the volume of data your application can process: a single block-message, an IP packet-sized message, and a megabyte of data per message.  We'll consider the tighter bound.

\begin{equation}
\begin{array}{llll}
\text{max bytes} &
\text{messages} &
\text{forgeries} &
\tau=128 &
96 &
64 &
32 \\
\hline
\text{one block: $16$}
  & 1 & 1 & 2^{-127} & 2^{-95} & 2^{-63} & 2^{-31} \\
\hline
\text{IP packet: $2^{11}$}
 & 2^{16} & 1 & 2^{-120} & 2^{-88} & 2^{-56} & 2^{-24} \\
 & 2^{16} & 2^{16} & 2^{-104} & 2^{-72} & 2^{-40} & 2^{-8} \\
 & 2^{16} & 2^{24} & 2^{-96} & 2^{-64} & 2^{-32} & 0.6 \\
 & 2^{16} & 2^{32} & 2^{-88} & 2^{-56} & 2^{-24} & (?) \\
 & 2^{16} & 2^{48} & 2^{-72} & 2^{-40} & 2^{-8} & (?) \\
 & 2^{16} & 2^{56} & 2^{-64} & 2^{-32} & 0.6 & (?) \\
\hline
\text{IP packet: $2^{11}$}
 & 2^{32} & 1 & 2^{-120} & 2^{-88} & 2^{-56} & 2^{-24} \\
 & 2^{32} & 2^{32} & 2^{-88} & 2^{-56} & 2^{-24} & (?) \\
 & 2^{32} & 2^{48} & 2^{-72} & 2^{-40} & 2^{-8} & (?) \\
 & 2^{32} & 2^{56} & 2^{-64} & 2^{-32} & 0.6 & (?) \\
 & 2^{32} & 2^{60} & 2^{-14} & (?) & (?) & (?) \\
\hline
\text{IP packet: $2^{11}$}
 & 2^{48} & 1 & 2^{-120} & 2^{-88} & 2^{-56} & 2^{-24} \\
 & 2^{48} & 2^{48} & 2^{-72} & 2^{-40} & 2^{-8} & (?) \\
 & 2^{48} & 2^{56} & 2^{-64} & 2^{-32} & 0.6 & (?) \\
 & 2^{48} & 2^{60} & 2^{-14} & (?) & (?) & (?) \\
\hline
\text{megabyte: $2^{20}$}
 & 2^{32} & 1 & 2^{-111} & 2^{-79} & 2^{-47} & 2^{-15} \\
 & 2^{32} & 2^{32} & 2^{-79} & 2^{-47} & 2^{-15} & (?) \\
 & 2^{32} & 2^{40} & 2^{-71} & 2^{-39} & 2^{-7} & (?) \\
 & 2^{32} & 2^{48} & 2^{-63} & 2^{-31} & (?) & (?) \\
 & 2^{32} & 2^{50} & 2^{-50} & 2^{-18} & (?) & (?) \\
 & 2^{32} & 2^{51} & 2^{-14} & (?) & (?) & (?) \\
 & 2^{32} & 2^{52} & (?) & (?) & (?) & (?) \\
\end{array}
\end{equation}

Entries labeled (?) have no bound at all on forgery by the above analysis.  Note that rotating keys doesn't help: the forger's attempts at forgery for the first key are independent of the forger's attempts at forgery for the second key.  Very small tags provide almost no security for even a modest number, tens of thousands, of modestly sized packets.

To put these forgery probabilities into perspective, the Bitcoin network rolls a 1 on a $2^{64}$-sided die about once a second.

Exercise for the reader: Compute the forgery probability bounds for the volumes of data in NIST's table, and assess how sensible they are.

WARNING 1: There may be fenceposts in the above analysis and errors in the calculation of the table entries.  For better confidence, trust anonymous reviewers at meatspace crypto conferences rather than pseudonymous strangers at internet crypto forums, and/or double-check the calculations yourself.

WARNING 2: Did you remember to use sequential 96-bit nonces?  You forgot, didn't you?  Go back and use sequential 96-bit nonces, or switch to crypto_secretbox_xsalsa20poly1305 which is faster and safer in software and allows random nonces and has better bounds than the above even with random nonces.


RC4 encryption -> AES encryption = more or less secure than RC4 or AES alone? Say I have

$k1 = "keyhere";
    $k2 = "keyhere";

$rc4key = sha256($k1 . $seed);
    $aeskey = sha256($k2 . $seed . $rc4key);

$input_data = "hello world";

$rc4 = new RC4 -> encrypt($input,$rc4key)
    $aes = new AES -> encrpt ($rc4, $aeskey);

Meaning...
If I have two keys (1 rc4 and 1 aes), Is it more secure to encrypt my RC4 output with AES, than to use AES or RC4 alone and a single key?

What type of attack are you trying to prevent?

If it's a brute-force attack, AES-128 is more than sufficient. In the best case scenario, combining RC4 and AES gains you negligible additional security due to a meet-in-the-middle attack.

Are you trying to hedge against a "break" of either RC4 or AES? If so, in the real world, this is extremely unlikely to happen. If either one is weakened by a cryptanalytic result, you will have plenty of time to migrate away from the affected cipher — and you should do this regardless of if you're encrypting only with this cipher, or encrypting with two separate ciphers.

So, practically speaking, there's very little upside. On the downside, you're now heavily increasing the likelihood that you implement the cryptography incorrectly. It's infinitely more likely that you will, as an amateur cryptographer, generate keys insecurely, store keys insecurely, generate two keys that are not independent of one another, use an insecure mode of encryption (e.g., ECB), use static IVs, generate IVs that don't satisfy the requirements of the cryptographic mode for which they're used, fail to use authenticated encryption (e.g., GCM / EAX modes), introduce timing attacks when creating your own authenticated mode (e.g., CTR + HMAC), and so on. There is a near infinite number of ways in which even experienced cryptographers can fail when working directly with ciphers, and well-intentioned amateur cryptographers have practically no hope of implementing it correctly.

The general advice here is to use a high-level cryptographic library like NaCl or KeyCzar that handles the details for you. If you're typing the letters A-E-S into your code, you're doing it wrong.


CBC-MAC length extension attack with IV simulation I'm doing the Cryptopals challenges (formerly the Matasano challenges) and struggling with second part of the 49th problem where I'm asked to do the length extension attack with CBC-MAC without IV manipulation. There is a hint that I can simulate an IV somehow to do this but I don't understand. Can someone drop me some hint at least? I did the part with forging the first block of the message with changing the IV.

In particular there is a message format like this

  from=#{from_id}&tx_list=#{transactions}

With the transaction list formatted like:

  to:amount(;to:amount)*

The task is: capture a valid message from target user. Use
length extension to add a transaction paying the attacker's account 1M
spacebucks.

EDIT
Alright, as I failed to explain it properly with my own words, here is the original problem

49. CBC-MAC Message Forgery

Let's talk about CBC-MAC.

CBC-MAC is like this:

  1. Take the plaintext P.
  2. Encrypt P under CBC with key K, yielding ciphertext C.
  3. Chuck all of C but the last block C[n].
  4. C[n] is the MAC.

Suppose there's an online banking application, and it carries out user
requests by talking to an API server over the network. Each request
looks like this:

  message || IV || MAC

The message looks like this:

  from=#{from_id}&to=#{to_id}&amount=#{amount}

Now, write an API server and a web frontend for it. (NOTE: No need to
get ambitious and write actual servers and web apps. Totally fine to
go lo-fi on this one.) The client and server should share a secret key
K to sign and verify messages.

The API server should accept messages, verify signatures, and carry
out each transaction if the MAC is valid. It's also publicly exposed -
the attacker can submit messages freely assuming he can forge the
right MAC.

The web client should allow the attacker to generate valid messages
for accounts he controls. (Feel free to sanitize params if you're
feeling anal-retentive.) Assume the attacker is in a position to
capture and inspect messages from the client to the API server.

One thing we haven't discussed is the IV. Assume the client generates
a per-message IV and sends it along with the MAC. That's how CBC
works, right?

Wrong.

For messages signed under CBC-MAC, an attacker-controlled IV is a
liability. Why? Because it yields full control over the first block of
the message.

Use this fact to generate a message transferring 1M spacebucks from a
target victim's account into your account.

I'll wait. Just let me know when you're done.

~ waiting ~

~ waiting ~

~ waiting ~

All done? Great - I knew you could do it!

Now let's tune up that protocol a little bit.

As we now know, you're supposed to use a fixed IV with CBC-MAC, so
let's do that. We'll set ours at 0 for simplicity. This means the IV
comes out of the protocol:

  message || MAC

Pretty simple, but we'll also adjust the message. For the purposes of
efficiency, the bank wants to be able to process multiple transactions
in a single request. So the message now looks like this:

  from=#{from_id}&tx_list=#{transactions}

With the transaction list formatted like:

  to:amount(;to:amount)*

There's still a weakness here: the MAC is vulnerable to length
extension attacks. How?

Well, the output of CBC-MAC is a valid IV for a new message.

"But we don't control the IV anymore!"

With sufficient mastery of CBC, we can fake it.

Your mission: capture a valid message from your target user. Use
length extension to add a transaction paying the attacker's account 1M
spacebucks.

HINT:

  This would be a lot easier if you had full control over the first
  block of your message, huh? Maybe you can simulate that.

Food for thought:

  How would you modify the protocol to prevent this?

It seems that all this discussion about the IV is just to confuse the reader. Ignore IV. You just have to do a simple length-extension attack on the CBC-MAC. Yes, one message is enough.


How can padding be disambiguated from data, when encrypting using a block cipher? How can padding be disambiguated from data, when encrypting using a block cipher?

I'm by no means an expert in cryptography, but rather a programmer with a keen interest.

Suppose, I've X bytes of data, message M, that I want to encrypt using an N-byte block cipher, where N >> X.

How can M be padded using N-X bytes of padding O, such that there would be no ambiguity between decrypting the padded message M´ and the (concatenated) message M|O?

How is this done in practice? Normally, when encrypting using a block cipher, I don't see a header being output describing the original length of the message M?

The usual padding for block ciphers ("PKCS#7 padding") is not a sequence of zeroes, but a sequence of P = N - (X % N) bytes each with value P.

If the message is a multiple of the block size, then a full block of padding is added (where each byte value is the block size).

For example, is the message is 15-byte long and the block size is 16 bytes, than one byte of padding will be added, and the value of the byte is 1. If the message is 14-byte long, two bytes with value 2 will be added. If the message is 16-byte long, sixteen bytes with value 16 will be added.

With these rules, the padding is unambiguous.


Derive a shared secret between different curves Is it possible to derive a shared secret between different curves?
An explanation would be nice.
How can I decide which curve I should use in my software?
Highest amount of bits has in my case the brainpoolP320r1 curve, but on this site https://safecurves.cr.yp.to/ the brainpool curves are rated as not safe.
The German Federal Office for Information Security recommend amongst others the brainpoolP320r1.

These curves can I use with my HSM (hardware security module):

secp192r1 (aka prime192v1)
secp256r1 (aka prime256v1)
brainpoolP192r1
brainpoolP224r1
brainpoolP256r1
brainpoolP320r1
secp192k1
secp256k1 (the Bitcoin curve)

Additional Question:
If I want to perform signing and generating a shared secret, should I always use different instances of a curve? Because if not, I would perform different actions one the sone instance. Which is bad?

You can probably come up with some key exchange using different curves, for example if they are isomorphic (a curve and its twist). If you have two curves that are independently chosen, it will become much harder (if not impossible).

With regard to SafeCurves, I would be quite careful making too strong conclusions based on the website. By their logic any curve with a prime number of points is insecure. The reasons are that

Prime order curves do not have a ladder. This is not true. They do have a ladder, the formulas are just not as efficient. Even so, you would usually not want to use a ladder since it prohibits precomputation.
Prime order curves do not have a complete addition law. This is not true. They do have one, it is just not as efficient.
Prime order curves have points that are distinguishable from random. This is not true. There exist an encoding (Elligator Squared).

It is nonsense to conclude that these points make prime order curves insecure. They are perhaps not as efficient as other curves, but in no way more insecure.


The role of IV when AES is used as $PRF$ We want to use AES as a pseudorandom function. Given a random master key, we want to derive a set of pseudorandom values/keys, e.g say $n$ keys. Then from each of those derived keys, we want to derive a set of pseudorandom values, say $d$.

I think, one way of doing that is to encrypt $1,...,n$ using the master key. This gives us $n$ ciphertext. Then, we use each ciphertext as a key to encrypt $1,...,d$.

Question 1: In the above case, do we need to generate a random IV each time we encrypt a message. Does that mean we have to store all IV?

Question 2: If the answer to the above question is yes, then which PRF  (that requires only one seed and IV) is suitable for the above case? Can we use the hash of each input, i.e. index, as IV?

Note that in the above case, IV does not need to be public.

AES does not itself have a concept of ‘initialization vector’—initialization vectors are basically an artifact of ciphers for long messages built out of fixed-size components.  AES is just a keyed family of permutations of 128-bit strings.

You can use the AES permutation as such as you described—with the caveat that you should use AES-192 or AES-256 if you want a standard ‘128-bit security level’.  Of course, then you need a 256-bit key which you can't get by a single invocation of AES  One way you can use AES-256 to generate 256-bit keys is to alternate between even and odd inputs: derive the $i^{\mathit{th}}$ subkey $k_i$ from the master key $k$ by $$k_i = \operatorname{AES256}_k(2i) \mathbin\| \operatorname{AES256}_k(2i + 1).$$  You'll never get a key that consists of the same 128 bits repeated twice, but the probability of that was negligible anyway; the standard PRF/PRP switching lemma provides bounds on the probability of a problem from this.  Essentially this structure is used by, e.g., AES-GCM-SIV (or at least the last incarnation of it that I saw).  However, there's another couple of caveats about AES:

In software, changing AES keys is expensive.
In software, there is a conflict between fast AES implementations and secure AES implementations that don't leak secrets through timing side channels.

Systems like AES-GCM-SIV were designed under the premise that you can actually audit your software stack all the way down to the assembly code to guarantee that you're actually getting hardware AES support.  There's a much simpler, safer, and more confidence-inspiring way to do it, which doesn't even involve a PRF/PRP switching cost: use a PRF designed for security in fast software like ChaCha instead.