Alternatives to HMAC + CBC? I'm looking at using HMAC + CBC. The combination looks like this:

ciphertext = AES256(text, k1)
data = HMAC-SHA256(iv | ciphertext, k2) | iv | ciphertext

Where:

k1 = 32 byte key - Randomly generated, once
k2 = 32 byte key - Randomly generated, once
iv = 16 bytes - Randomly generated, for every message

The purpose is for storing sensitive information in a database.

Is the above approach cryptographically secure for sensitive information? Would there be any reason to consider a stream-cipher mode verses a block-cipher mode like CBC?

Would an AEAD mode like OCB or CCM be more appropriate?

If an AEAD mode is not available for the platform we are using (specifically Go), is it worth the effort trying to implement these modes?

Yes, this is fine, at the record level.  (What you've built would be classified as a "Encrypt-then-Authenticate" scheme in the literature, and there are standard provable security results for such schemes.)  Well done on constructing a solid, well-engineered cryptographic scheme.

An AEAD mode would spare you from having to invent such a scheme, but what you've got is fine, and there's no reason why you need to change.

There's no reason to switch to a stream-cipher mode of operation.

As others have mentioned in the comments, this would be more secure if you included an identifier in the input to HMAC that identifies the table, row, and column where this appears, so that a ciphertext cannot be replayed from one position to another.  There will still be the risk of rollback attacks, as fgrieu explains; that is more challenging to defend against, so if you need to stop them, you might want to elaborate on the specific application situation.


Where is Challenge/Response and Certifcate Verification in TLS-DHE We have been give a task to identify the following three components in TLS-DHE:

Diffie Hellman Key Exchange

I am fairly certain that this Part can be found in the Exchange of SKE and CKE, since they contain the public Key with Signatures and can be used by the other party to derive a shared key

Challenge/Response

I am having trouble identifying this part. Since this part is usually something you would do before exchange a key, i reccon it can only occur in the Part with the CH. However, i fail to see how CH (CHallenge?) is a challenge for the Server S, because usually challenges are solved by using private information

Certificate Verify

I know the Certificate consists of Public Key and digital Signature, but how can a Certificate be authenticated here without having established a shared secret yet? I do not see any Certification Authority here as well, so i am clueless

Aside: that diagram is only correct (or nearly) for TLS 1.0 through 1.2, not 1.3. It mentions, without explanation, the number 3.2, which is the internal version for TLS 1.1, suggesting it is intended to match that version, for the two DHE key exhanges (DHE_RSA and DHE_DSS). But it references CDH, which usually means Cofactor Diffie-Hellman, which TLS does not use -- and in that step it doesn't show $p,g$ as parameters which for these protocols they definitely are. (In 1.3 they still are, but via predefined curves which could be considered the 'source'.) 1.0 and 1.2 are identical for most of the handshake, but vary slightly in the second part of the (shared) key derivation.

Diffie Hellman Key Exchange
I am fairly certain that this Part can be found in the Exchange of SKE and CKE, since they contain the public Key with Signatures and can be used by the other party to derive a shared key

Basically, yes. SKE contains the parameters (p,g) and publickey which this calls Y but the RFCs call Y_s; CKE contains publickey here X but in RFCs Y_c. The server also provides a signature in SKE, and the client may provide a signature in CV (adjacent to but not in CKE); while these contribute to the overall handshake they don't contribute to DH itself.

Challenge/Response
I am having trouble identifying this part. Since this part is usually something you would do before exchange a key, i reccon it can only occur in the Part with the CH. However, i fail to see how CH (CHallenge?) is a challenge for the Server S, because usually challenges are solved by using private information

First, the all-caps and mostly-caps items (other than SID = Session Identifier, PRF, and CDH) are clearly abbreviations of the TLS message types:
CH = Client Hello
SH = Server Hello
SKE = Server Key Exchange
CRT = Certificate
CReq = Certificate Request
SHD = Server Hello Done
CKE = Client Key Exchange
CV = Certificate Verify
CCS = Change Cipher Spec
FIN = Finished
See e.g. the summary diagram in RFC 4346 7.3 at page 33.  Note Creq in server's first flight, and CRT and CV in client's second flight, are shown in brackets, indicating they are optional; this corresponds to asterisks in the RFC summary diagram.
There are two challenges in the TLS handshake: the client and server randoms, shown here as $r_C$ and $r_S$. These are included in the data signed (server always, client sometimes, as above), and the (shared) key derivation, and the Finished message values (which MAC the handshake).

Certificate Verify
I know the Certificate consists of Public Key and digital Signature, but how can a Certificate be authenticated here without having established a shared secret yet? I do not see any Certification Authority here as well, so i am clueless

Certificate verification and validation (terms which are often interchanged, although a distinction can be made) as applied to TLS includes several steps, and I'm not sure which your teacher intends you to cover. First off, a certificate (of the type relevant here) contains a publickey and signature, but also much other information. And the cert itself is not authenticated, rather it is used to authenticate something else -- in TLS the server is almost always authenticated by a certificate, and the client sometimes (but rarely) is. And although TLS connections almost always use cert-based authentication, strictly speaking it isn't part of the TLS protocol: TLS only conveys the cert data, leaving its processing up to the relying endpoint(s). TLS can also convey certificate 'status' (i.e. revocation) information, in the form of pre-generated OCSP responses; this is called 'stapling' and has become very common since about 2012, but is not in your diagram. And while each certificate is issued by a Certificate Authority, and the related CRL and/or OCSP information either by or on behalf of the CA, the CA is not involved in the TLS protocol.
For a basic explanation of cert chain usage and validation for HTTPS see my old answer to this Q. A bit more formally:

every certificate is issued and signed by a CA; in practice your server's cert is not signed directly by a root CA, instead there is at least one intermediate CA in between, and the list of certs from your server's cert (or client's when used) through the intermediate(s) to the root is called a chain

each certificate below the root in a chain is verified by verifying its signature using the publickey from the next cert in the chain or the root; and checking a number of items in the certificate data, see RFC5280 section 6; and checking for revocation, for which there are several options, and expiration

the set of root CAs that are trusted can be defined separately for each relier, although typically a system-provided or browser-provided default is used; the root CA information is usually stored as a series of self-signed certficates (although this isn't strictly necessary, see e.g. the Java CertPathValidator API) and called a 'truststore'

for some TLS applications like HTTPS, the name in the 'leaf' (end-entity) certificate for the server is checked to make sure it identifies the correct server (the one the client wanted to connect to)


Is the Blum Blum Shub PRNG suitable to create initialization vectors? Is it a good idea to use a Blum Blum Shub Generator to create my initialization Vector (IV) in AES-OFB (Output Feedback Mode)?

The choice or PRNG doesn't really matter much, as long as it's a decent one. I wouldn't use BBS because it's slow, and the security proof isn't too useful.

The interesting question is rather, how to seed the PRNG with sufficient entropy. You need a sufficient amount of data that an attacker can't predict. I strongly recommend not doing this yourself, but to leave the job to the OS. Any major platform or OS offers a built secure PRNG which is supposed to be well seeded(/dev/urandom on linux, CryptGenRandom on windows, RNGCryptoServiceProvider on .net, etc.) . There are some issues on embedded systems and virtual machines, but for normal desktop computers the built in mechanism should be sufficient.


Get secret_value from multiple hashes md5(known_value_n + secret_value) The attacker knows multiple hashes like md5(known_value_n + secret_value), for multiple known values. Does it help him to discover secret_value better then just single md5(known_value + secret_value)? secret_value is long enough, 20-30 characters.

No, having multiple hashes will not make determining the secret which was hashed any easier.


Key exchange and man in the middle issue. Secure solution I am trying to design MiTM protected key exchange algorithm.
For instance I am using RSA asymmetric keys.

Alice and Bob respectively have each their own pair of keys. And they should be able to exchange public keys. In real life implementation there would be a relay 3rd party which should only allow Alice and Bob exchange messages in case if there is no way for direct connection. However this relay party can be compromised by Eve where she would have her own pair of keys, accept Alices And Bobs public keys during the exchange and send out hers instead. Therefore all encrypted messages will be decrypted, read, encrypted again and sent further by Eve compromising the whole key exchange process.

Apparently there can be Trent that could sign the key before it is sent to the recipient and later after it has been received could verify the signature. However I feel that this schema also has a flaw as Eve could somehow obtain public key signed by Trent.

Is there a way to make sure that if Trent is not compromised (means that it is not someone disguised as Trent) we can make sure that keys are exchanged securely?

What comes to mind is that any party can have information about Trent (certificate, public key or something similar) using which they can make sure they communicate with Trent, whereas Trent would confirm to each party from whom they received the key. Does this schema has a flaw or any issues that I haven't noticed?

You are right that the session public keys can be replaced if they are not signed by long term private key known to all parties.

What you want to do is not have Trent do anything but be a relay, then you need a standard key exchange process between the two parties using new random key pairs. Then once all parties have both public keys, they can generate an authentication hash of the key pairs as well as the prime/exponent and any other common data. After the key exchange completes and the session key is generated, you would need some way to compare them, even if it is an insecure channel, as long as that comparison cannot be modified.

Several programs use this method or one like it. I use one over IRC, with the IRC server taking the place of Trent. The obvious alternative is known long term keys that are only used for signing the session public keys.


What language classes beyond NP allow constant-round zero-knowledge proofs? While discussing proving a language in $\Sigma_2$ from a client to a server with a friend we realized that while we know that such a language is provable in zero-knowledge, we didn't know whether it was provable in non-interactive zero-knowledge. This then led us to find this answer which states it is sufficient for a zero-knowledge proof to be constant-round to be transformable into a non-interactive one via Fiat-Shamir.
This then led me to confirm that in fact NP allows constant-round zero-knowledge proofs (PDF), which of course lead to the question in the title.
So:
Which language classes that include P allow constant-round zero-knowledge proofs - other than P and NP - and for which do we know that every zero-knowledge proof needs to have non-constant number of rounds?

The sumcheck protocol can be made non-interactive, both in the random oracle model and under strong cryptographic assumptions. Good starting points to read about that are this paper and this paper. The high level intuition that even if Fiat-Shamir fails in general for interactive protocols with many rounds, it holds whenever the protocol satisfies some stronger notion of round by round soundness which the sumcheck protocol does satisfy.
This gives you a non-interactive argument for $\#\mathsf{P}$ in the ROM. I believe that it should be relatively easy to make it zero-knowledge. It might extend to all of PSPACE, though one would have to check the details - I do not think it has been written formally anywhere.
Edit: An important point, though, is that this result in the ROM will not be easy to extend to the standard model, at least not with standard cryptographic assumptions. This is because to get a constant-round argument for a language outside of NP, we would need a cryptographic assumption (for the soundness) which withstands even attacks from prover which are given the power of this larger complexity class, and this is typically not something given by standard cryptographic assumptions.


How much does using the same $H$ for all messages weaken GCM? How much is GCM weakened by using the same MAC key $H = E_K(0^*)$ for all messages that use the same key (which is what GCM actually does) instead of using $E_K(N||0_{32})$ (which is different for each message)?

Under the ideal cipher model, security is not diminished by any choice of value $H = E_K(d)$ for a known value $d$, as long as none of the counter values that get encrypted to generate the encryption stream is equal to $d$. This is what "ideal cipher" means: you have no information on $E_K(x)$ for any $x$ that you have not already tried to encrypt with the same key, and that goes for all such $x$; none is beter or worse than any other. Using $d = N||0_{32}$ instead of $d = 0_{128}$ would thus not make GCM any weaker. It would not make it stronger either, for all we know, because making it "stronger" would require that we know of some weakness in GCM as it is defined nowadays; and we know of no such weakness.

Now, using $H = E_K(0_{128})$ has some implementation benefits. Namely, suppose that you want a constant-time implementation of GCM, thus without any memory access whose address depends on the data or the key (this is to avoid side-channel attacks through cache misses). On a modern PC, you will want to use specialized opcodes, but on a slightly less modern x86 CPU, or on a non-x86 architecture (e.g. ARM), you do not not necessarily have access to such facilities. Classical implementations of multiplications in $GF(2^{128})$ are either very slow, or use data-dependent table lookups, which are not constant-time. A constant-time multiplication by $H$ can be implemented relatively efficiently (at about 14 cpb) with the help of tables whose contents depend on $H$ -- but that's counting without the cost of generating these tables. If $H$ depends only on the key, not the IV, then the tables can be produced as part of the key schedule, for a much lower overhead if many messages are processed with the same key.

Thus, having an IV-dependent $H$ is not known to increase (or decrease) security, but may imply larger CPU costs in some situations. This is a good reason to have a fixed $H$, that depends on the key but not the IV.

Constant-time multiplications in $GF(2^{128})$ can also be done in other ways, but that's another story. One is to use additive Fourier transforms, which yields remarkable performance in generalized bitslicing, but only in situations where many blocks can be processed in parallel, and with a large fixed overhead. Another method is to use integer multiplications on the operands, with most bits cleared to make room for carries; this can be worthwhile if the architecture at hand offers constant-time efficient multiplications. An example of such an architecture is the very-low-power ARM Cortex M0+, where additions and multiplications have the same cost (1 cycle each).

Even then, having an IV-dependent $H$ still implies some extra work for each message, since that processing cannot be shared.


What is the purpose of four different secrets shared by client and server in SSL/TLS? I was looking through the working of SSL V3, and found that a connection state is defined by a set of things, including

client write mac secret,
server write mac secret,
server write key,
client write key.

I couldn't found the use of these in the SSL protocol.

As I understood from reading, after having a handshake, SSL creates a 48 byte master secret, which is used in encryption and this secret is shared by both client and server.

For what are these four values used?

In TLS (that's the standard name for SSL; TLS 1.2 is like "SSL version 3.3"), client and server ends up with a shared secret (the "master secret", a 48-byte sequence; when using RSA key exchange, the master secret is derived from the "premaster secret" which is the 48-byte string that the client encrypts with the server public key). That shared secret is then "extended" into six values:

the "client write key";
the "client write IV";
the "client write MAC key";
three similar values for the server.

The "extension" uses the PRF described in section 5; it can be thought of as a hash function with a flexible output length.

TLS main purpose is to keep data confidential; however, it also aims at maintaining data integrity: if someone or something, willingly or not, alters data in transit, then the receiver must be able to reliably detect it. Detecting alterations is important in many protocols; moreover, if an attacker can modify data, he can often handcraft precise alteration which, when sent to the peer in lieu of the correct data, may result in reactions which leak information about the encrypted data. Therefore, we not only want to detect alterations for the own sake of integrity, but also because unconstrained alteration may result in a confidentiality breach.

So we need encryption (for confidentiality) and integrity control (to support confidentiality, and because integrity is also needed by itself). This calls for several algorithms, typically AES for the symmetric encryption part, and HMAC for the integrity control. HMAC is a Message Authentication Code algorithm, which is a kind of "hash function with a key" (HMAC is built over a true hash function, like SHA-256, with a key inserted "the right way"). The HMAC value is computed by the client with its "client write MAC key" and appended to the record data; the server will recompute the HMAC value and see if it matches the one which was sent.

The encryption part requires a key (and an IV for symmetric encryption algorithms which use CBC mode, and this is subject to a few subtleties which depend on the SSL protocol version, so I will not detail these here). The MAC also needs a key. Using the same key for two distinct algorithms is, as a general rule, not recommended at all: there may be unwanted interactions between the two algorithms, an improbable but not impossible event which has not been thoroughly studied. So, to be on the safe side, we generated two keys, one for encryption and one for the MAC. The two keys come from the master secret, but the derivation mechanism is like a hash function, so it supposedly makes it impossible to guess the MAC key even if you know the encryption key, and vice versa.

Since TLS has a key derivation function (the "PRF") which can produce outputs of arbitrary length, it was easy to mandate production of encryption and MAC keys distinct for both directions (the key used by the client to encrypt data -- and that the server uses to decrypt received data -- is distinct from the key used by the server to encrypt data it sends to the client). Using distinct keys avoids problems with attackers who could otherwise get a copy of an encrypted record sent by the client, and feed it back to the client as if it was sent from the server. With distinct keys, the client will reject the attempt, because the HMAC value will not match what the client expects (it will be a HMAC computed with the client write MAC key, not with the server write MAC key).

There are newer symmetric encryption modes which do the encryption and the MAC with the same key in a controlled way, e.g. GCM -- and AES-with-GCM can be used with TLS although you may have a hard time finding compatible implementations (this is rather new).


What is sent on the initial communication with Kerberos? When a user wants to communicate with another user (let's say Alice and Bob), what is sent over the network during the initial communication?

Alice uses her Kerberos client and enters her password and username.

Something which is not clear to me:

Will she send a message containing

time
username
hash of password

generated with the session key of the kerberos client and authentication server?

Or will she send a message to the AS containing

time
username

encrypted with Alice's password and this again encrypted with a session key?

If you look at RFC 1510, (an overview and specification of Version 5 of the Kerberos network authentication system), the initial exchange involves the client (Bob) sending its own identity, and the identity of the server (Alice) for which it is requesting credentials in cleartext.  The response contains a ticket for the client to present to the server, and a session key that will be shared by the client and server.  The session key and additional information are encrypted using the client's secret key (which is stored on the Authentication Server).

The request message contains the client's principal name as well as the server's principal name, the time and a nonce to prevent replays.  The reply message contains information which can be used to detect replays, and to associate it with the message to which it replies.

In the normal case, the authentication server does not know whether or not the client is actually the principal named in the request.  It simply sends a reply without knowing or caring whether or not they are the same.  This is acceptable since nobody but the requesting principal (client) will be able to decode the reply.

For further information, have a look at Section 3 - Message Exchange of RFC 1510.


How to calculate kinv from the given k value I am implementing an ECDSA NIST test vectors verification application. The test vectors are taken from http://csrc.nist.gov/groups/STM/cavp/#09.

One of the test vectors is given below:

P-192 SHA1

Msg = 608079423f12421de616b7493ebe551cf4d65b92
d = e14f37b3d1374ff8b03f41b9b3fdd2f0ebccf275d660d7f3
Qx = 07008ea40b08dbe76432096e80a2494c94982d2d5bcf98e6
Qy = 76fab681d00b414ea636ba215de26d98c41bd7f2e4d65477
k = cb0abc7043a10783684556fb12c4154d57bc31a289685f25
R = 6994d962bdd0d793ffddf855ec5bf2f91a9698b46258a63e
S = 02ba6465a234903744ab02bc8521405b73cf5fc00e1a9f41

I am trying to calculate $k_{inv}$ from given $k$ value and I am using curve “NID_X9_62_prime192v1”.

Can anyone tell me how to calculate $k_{inv}$?

Just compute the multiplicative inverse $k^{-1}$ of $k$ modulo the prime order $n$ of the base point $G$ (I used the typical notation for the domain parameters of the curve). This can efficiently be done using extended Euclid and should be available in any reasonable big integer library (typically something like modinverse). Thats it.


Cracking a PRNG by observing ranks within groups of its output Suppose that I am generating random numbers with Python's random module, so that there is a known random number generator (Mersenne Twister in this case).   I've read: "[...] observing a sufficient number of iterations (624 in the case of MT19937, since this is the size of the state vector from which future iterations are produced) allows one to predict all future iterations."  This also got into how to actually crack it: Cracking Random Number Generators - Part 3

What if, instead of peeking at random numbers from the generator, you saw repeated rankings of the random numbers?  As an example, the generator repeatedly produces vectors of 100 ranks for 100 uniform 0-1 numbers:

first 100: (47, 22, 1, 12, ...)
second 100: (18, 44, 99, 24, ...)

How much would this slow down the cracking process?  I feel that this has a pretty precise answer, but I have no idea how one would even get started with the analysis/math.

Assuming $w=32$ (32-bit integers for internal state), $624 * 32 = 19968$ bits of information is found in the internal state. On the other hand, a maximum of $\lfloor\log_2(100!)\rfloor=524$ bits of information is revealed by each ranking of 100 outputs. $\lceil19968/524\rceil=39$ rankings of 100 outputs each would be the minimum information I would expect to need to identify the state. I do not, however, know of an algorithm to use the revealed ranking information to calculate the state.

You talk about "leaking" information and ask about a "cracking process". I hope you are not attempting to use a Mersenne Twister when a cryptographically secure pseudo-random number generator is needed.


Message exchange with textbook RSA I am working on this exercise but can't work out the answer to the question b.
I have solved the question (a) by decrypting the ciphertext $C = 2$ using the formula:
$$
M = C^d \bmod n = 2^{17} \bmod 21 = 11
$$

  Alice and Bob agree to communicate using the RSA cryptosystem. Alice has a private key ($n = 21$, $d = 17$) and a public key ($n = 21$, $e = 5$).

  (a) Alice receives the ciphertext $C = $2 from Bob. Decrypt this message, show your working.
  (b) Bob wishes to ensure that he sent the ciphertext to Alice. Bob sends Alice the plaintext message $M = 9$, what message should Alice send back?
  (c) Perform the calculation Bob would do to verify this returned message.

What do you guys think?

Basically $M = 9$ is a challenge. Alice will have to sign it (compute $M^d \pmod {21})$, because only she knows $d$.
As $(M^e)^d = (M^d)^e = M \pmod{21}$, it should be clear what Bob should do to verify that the reply indeed equals $M^d$, which only Alice could have produced...


Create a bijective and invertible table that are depending on the cipher key I'm creating my own symmetric-key algorithm that in many ways are similar to DES.  My key is 16 bits long and is random generated, I will encrypt blocks of 16 bit strings that are split into two 8 bit strings. My approach is to make a 4x8 table where row one is selected if the decimal representation of the key is between 0 and 15000, row two if between 15000 and 30000, and so on. The column is chosen by the 3 last binary digits of the 8 bit string that will be encrypted. So column one is chosen if the three last digits is 000 and column 8 will be chosen if the three last is 111.

This metod works for encryption but I need the same function to work for decryption too. The boxes in the table is decimal numbers. How is it possible to make this approach work for my purpose?

In the picture both left and right side are the same function and thats how I want it to work.

This is not secure, of course, but your proposal has many problems even as a bijective lookup table.

You have 16 bit keys but you use effectively only 2 bits to select one of $2^2$ rows. You have essentially only 4 distinct keys.
You have 8 bit inputs but you use effectively only 3 bits to select one of $2^3$ columns. This gives you many inputs ($2^5=32$) mapping to the same entry in the lookup table so no bijective map is possible.


Key-dependent encryption in TAHOE-LAFS TAHOE-LAFS uses a form of "key-dependent encryption", in that a private key SK is encrypted with the truncated hash of the private key:

ENC(Htrunc(SK), SK)

Where Htrunc(X) is the result of SHA256(SHA256(X)), truncated to 16 bytes.

The TAHOE-LAFS paper states:

  This somewhat unusual arrangement means that the RSA signing key is encrypted with the truncation of the secure hash of itself. This is an instance key-dependent encryption, which is not as well-studied as we would like. However, we think that it would be surprising if there were a weakness in this construction which did not imply a weakness in the underlying standard primitives – RSA, AES-128, and SHA256.

What are the practical consequences of the use of this construction? Is the paper right in saying that if the underlying primitives are secure, this scheme should be secure as well?

There are no known dangers or attacks from this construction.  I agree with the quote from the TAHOE-LFS paper.  I would find it quite surprising if this use of the key material introduced some special weakness.  I can't prove it, but based upon my professional judgement, this is probably far from the biggest risk to your security -- it is very unlikely that this is the weakest link in the system.  It is far more likely that the weakest link is something else (e.g., endpoint security, the human processes, social engineering).  So, personally I wouldn't worry about this.


Why still we are using classical key exchange rather than quantum idea Why still we are using Diffie-Hellman idea  rather than BB84 or B92 like
quantum protocols for key exchange?

Well, not everybody is willing to put an optical line from each person to another or install the hardware components to do the quantum computing, for one. You cannot just send the information over the internet protocol or even electrical wiring.

QC key distribution is commonly used by large organizations and governments that want to distribute secret keys relatively often (otherwise you could just send it by courier).

Besides, without fully functional quantum computers for analysis, DH is still considered secure, at least when the proper authentication and verification procedures are in place.

Note that QC is no panacea either; you could for instance try and retrieve information from the equipment or find other holes in the way the QC is actually implemented. More info in section 4 & 5 here.


Simplified Key Wrapping to Achieve Only Confidentiality? I'm looking for help in understanding why the algorithm described here would not deliver adequate protection of confidentiality.  We don't care about other criteria such as authenticity or integrity.  In other words, we only want to make sure our key material is secret.

Given a key $k$ that is $l$ bits long, a hashing algorithm $H$ that produces an $l$ bit digest, a password $p$ of at least $n$ bits (smaller than $l$), and a randomly generated $l$ bit salt $s$, we produce an $l$ bit wrapped key $W$ by:

$$\begin{align}
    W &:= H(s||p) \oplus k &\text{(Wrap)}
\\  k' &:= H(s||p) \oplus W' &\text{(Unwrap)}
\end{align}$$
where $W'=W,k'=k$ if the transmission has not been tampered with (nb: we do not care if it has).

We know that authenticated encryption would be better.  At this time hashing is our only tool.

Are we falling prey to a fearsome Birthday Attack?

It appears that a related question was asked before though they were more ambitious and the answer isn't clear.

Hash Based Encryption (fast & simple), how well would this compare to AES?

Update (28 Apr): As my goal is to help eliminate some of the confusion, I'd like to amplify the answer.  I'm reading that malleability refers to the relatedness of ciphertexts, vis a vis Dolev, Dwork, Naor.  Specifically, we know that a certain number of bits in the ciphertext need to be inverted to recover the key.  We're also pretty certain that that all of the bits need to be inverted thereby reducing the search space.  The relationship between malleability and the chosen-ciphertext attacks is well known.

FWIW, if AES were available there would be no reason to consider anything other than one of the established key wrapping algorithms such as the NIST AES KeyWrap.

To summarize, the intention of using a hash function in the proposed construction is to build a reversible transformation from an inherently non-reversible function.  Because of the malleability introduced by the XOR there is no number of iterations of the hash to slow the pace of a brute-force search that would compensate for the fundamental weakness of the algorithm.

Many thanks.

Your proposal is malleable, so in particular, confidentiality does not hold against a chosen-W' attack, which is the key-wrap analogue of a chosen-ciphertext attack. $\:$ Also, the fact that your

proposal concatenates s with p suggests that H can probably be evaluated too quickly.

Although that may be typical, it shouldn't be, since the time needed to try passwords

in a known way scales linearly with the time needed to evaluate the password hash.

This answer gives some better password-based key derivation functions.

The "best reason that it is better for key wrapping" is that AES is hopefully non-malleable.

(Note that AES should replace xor, rather than replacing H.)


Some confusions about Repeated Doubling Algorithm? The following repeated point doubling algorithm is taken from the book Guide to Elliptic Curve Cryptography by D. Hankerson, A. Menezes, and S. Vanstone on page#93.

Clearly, this algorithm is better than calling the point doubling procedure $m$ times. But I am having a hard time to understand the correctness of this algorithm. So, I have two questions about the use of $2Y$ instead of $Y$ coordinate after the first iteration in the body of the loop

1) How to prove that it computes the correct value of all the coordinates at the end?

2) How to prove that it computes $2Y$ for $4P$ and so on?

This algorithm is a small optimization to Algorithm 3.21 of the same book on page 91. Algorithm 3.21 is the original algorithm for computing elliptic curve doubling using Jacobian coordinates (with $a=-3$). If you have a close look at both of the algorithms, you will notice many similarities. For example, Algorithm 3.21 computes $A \leftarrow 3(X_1-Z_1^2)(X_1+Z_1^2)$, whereas Algorithm 3.23 computes $A \leftarrow 3(X^2-W)$ (note that $W=Z^4$!). Therefore I would suggestion breaking problem (1) down into two parts:

For $m=1$ prove that Algorithm 3.23 computes the same thing as Algorithm 3.21. Since we are using Jacobian coordinates, this means showing that $X_3/Z_3^2=X/Z^2$ and $Y_3/Z_3^3=(Y/2)/Z^3$ (using the notation of the respective algorithms, and of course with equal input).
Use induction to prove the result for $m>1$.

I am not sure whether I understand part (2) of your question correctly. The statement $2Y$ for $4P$ is not really well-defined. Since we are working with projective coordinates (Jacobian), what you would probably want to check is whether we are computing a $X,Y,Z$ such that $4P=(X/Z^2 : (Y/2)/Z^3: 1)$. Since the first part of your question proves that the algorithm correctly computes $2^mP$ for any $m>1$, the second statement follows by applying the definition of Jacobian coordinates to Line 4 of Algorithm 3.21.


How can CBC-MAC be secure when message length is fixed? I was doing some self-initiated knowledge gathering about digests, signatures and hmacs and I ran across the fact that you can use CBC as a MAC, but if the message size is not fixed; then it is not secure.

In layman's terms why is this so?  Lets say that Johnnyboy has sent a message to QueenElizabeth such that a being the MAC and m being message (m consists of three blocks).  If an adversary saw the transmission, the data would look like $(a,m)$ in this particular instance.

The adversary would not know the key used in the CBC-MAC algorithm (it is still unknown), but it is known that the tag which is $a$, message $m$ and the number of blocks.

How could the adversary generate another valid MAC value $a'$ for $m'$ if $m'=m_1||m_2||m_3||m_1 \oplus a||m_2||m_3$ without knowing $K$?  and how would fixed length solve this?

From what I understand, all you need to do is take $m_1 \oplus a \oplus a$ which would result in $x_1$ then concatenating the rest - $m_2 || m_3$ - would result in $a' == a$ because the last block would be the same as the output from $m_1.

Lastly, to prevent this attack, the application or system receiving the transmission should check for a specific sized message in order to prevent this existential attack, but I am also guessing this is only secure when message blocks == 1?

What you think of is called an extension attack and it turns out that this is the way to go if you would like to break the general CBC-MAC when the message length is not fixed.

All that an adversary needs to do is to mount a chosen message attack.
Suppose he asks for the tag on the message $m=m_1||m_2||...||m_l$. The resulting CBC MAC would be $MAC_k(m)=t$. But now the adversary can easily find another message with a valid tag by extending his original message $m$ by  $m_1\oplus t||m_2||...||m_l$. By looking at the CBC-MAC construction its easy to see that the tag on the new message
$m'=(m||m_1\oplus t||m_2||...||m_l)$ is also $t$, what is in fact an  existential forgery.

This is a reason why the CBC MAC is just secure when the message length is fixed. The detailed security analysis of CBC MAC and some work arounds for the case where the message length is not fixed can be found in this paper:

Mihir Bellare, Joe Kilian, Phillip Rogaway, The Security of the Cipher Block Chaining Message Authentication Code, Journal of Computer and System Sciences, Volume 61, Issue 3, December 2000, Pages 362-399 http://dx.doi.org/10.1006/jcss.1999.1694.


What's the issue with Apple's backdoor? I was reading Apple's public letter here regarding the "backdoor" that they have been asked to create.  I'm very unclear exactly what the issue is.  There was no backdoor in the encryption algorithm that was actually used on the phone and it's doesn't seem as if they are being asked to create one (and sneak it onto phones) for the future.  Instead it seems like they are being asked to remove a feature of their phones which deletes data if too many wrong attempts are made.  A couple of questions:

This seems like it has nothing to do with cryptography or with a government inserting backdoors into encryption algorithms.  Therefore the consequences aren't nearly as universal as they make it sound (in their example of a "universal key").  Is this correct or incorrect?
If the data is encrypted and they just want to be able to brute force the data , why do they need apple to create this piece of software?  Given the resources of the FBI why can't they get the data off the phone and brute force it offline,  or why can't they have their own software engineers (along with some reverse engineers) design whatever it is that apple is supposed to do?

Apple are being asked to put a backdoor, not in the encryption algorithms (which are mathematical constructs that you can't add a backdoor to after you've designed it, and tend to be designed to be free of backdoors), but in their encryption system.

Cryptography isn't just about the basic algorithms but also how you use them. Other big topics in cryptography include protocol design (how basic algorithms are combined to design secure storage and communication systems) and key management (how you generate, distribute, store and revoke keys). The particular aspect that is at stake here is rate limitation, and it is related to key management.

Consider a 4-digit PIN. Suppose that legitimate unlocking of the phone given a PIN must take no longer than 1 second. If you try all PINs (brute force attack), that'll only take a little over 3 hours at most. To make this secure, two things are needed.

The encryption key must be derived not only from the PIN, but also from some other secret component which varies from device to device. Otherwise a resourceful adversary could go through all possible 10000 PINs by trying them on multiple devices.
That secret component must be physically hard to access. You can't just store it in a flash memory. It can't be encrypted. (bootstrapping problem: with what key would you encrypt it?) Recent iPhones and iPads (since the Apple A7 processor) have what Apple calls a “secure enclave” which includes a physically protected processor with some memory for that key. There aren't much details around about the secure enclave; Apple's security guide says what they're willing to say about it.
The secret component must be programmed not to allow an outside entity to try all possible PINs to give out the data encryption key. It's programmed to impose a delay between attempts and lock itself out after too many failed attempts. The same technique is used on other types of devices that must resist physical attacks, such as smartcards (e.g. credit cards with a chip, as is the norm in Europe among other places).

Apple claims, and this is likely, that they cannot give FBI access to a locked phone. This implies that:

Their security architecture follows the idea that I described above, with a secret component in a physically protected memory (that the FBI isn't able to dump). It may not be exactly this, but something with similar properties.
They have not kept a copy of the secret component that's in each phone. (It's probably randomly generated when the device is first booted, and probably regenerated when the device is reset to factory settings.)
They have not programmed the secure enclave with a backdoor, e.g. a secret password that would make it give out either the encryption key or the secret component (from which the encryption key could be calculated for each PIN value).

Apple surely could update their software (the iOS operating system, or more precisely, in fact, I think, the software that runs in the secure enclave) to include a backdoor, e.g. a secret password that would cause the enclave to release the secrets that it stores. Their letter doesn't say so explicitly, but it implies that they could and choose not to. Of course, if such a password existed, there would be no way to limit its use to “legitimate” cases: it would be bound to leak sooner or later, and a secure enclave doesn't know whether it's getting a password from the FBI in a terrorist case, from the FBI in an unauthorized surveillance, or from the FSB, the Ministry of State Security or the Mafia.

The fact that Apple could do it in the future doesn't help for existing devices. If the device can't be started for lack of a PIN, it won't apply the firmware updates.

Note that what I described doesn't rule out the possibility of other attacks. For example, it may be possible to take out the flash memory, put in another flash memory with a different firmware image that contains an update for the secure enclave firmware, and use that to get the secure enclave to relinquish its secret component.

In summary, the answers to your questions are:

What the FBI is asking for would be a backdoor in the encryption system of iDevices. It would be a universal key for iDevices.
Unsoldering a flash chip is well within the FBI's resources. But there are techniques, such as the ones used in smartcards, that allow storing a small amount of data (typically hundreds of kB, I think) and make it much more difficult to extract that data even with relatively fancy equipment.


ECDSA with SHA256 and sepc192r1 curve: Impossible, or how to calculate $e$? I need to use ECDSA as the signing algorithm and SHA256 for hashing the message. I'm running into troubles verifying the signature calculated on two different platform (one is BouncyCastle, another one a C library for a microprocessor).

I figured out that BouncyCastle, in its ECDSASigner class, reduces the input message (which is supposed to be already the hash), in both, generateSignature() and verifySignature() using a helper function called calculateE(). In essence, this functions truncates the input message/hash to the bitlength of the curve's order $N$.

protected BigInteger calculateE(BigInteger n, byte[] message)
{
    int log2n = n.bitLength();
    int messageBitLength = message.length * 8;

    BigInteger e = new BigInteger(1, message);
    if (log2n < messageBitLength)
    {
        e = e.shiftRight(messageBitLength - log2n);
    }
    return e;
}

This reduction results from the fact that a SHA256 hash has 32 Bytes, whereas the size of $N$ is (for secp192r1) 192/8 = 24 Bytes.

What I don't understand:

Do I have to use a curve with greater size of bitlength(N) for SHA256 hashes to be signed (e.g., secp256r1 or secp521r1)?
Is the implementation in BouncyCastle wrong/imcomplete, or only applies to SHA-1 (160 b = 20 B <= 24 B)?
Where is it documented/specified, how to “reduce” a hash of greater bitlength than that of the curve domain?

NIST FIPS 186-4 at the end of section 6.4 states that:

  When the length of the output of the hash function is greater than the
  bit length of $n$, then the leftmost $n$ bits of the hash function output
  block shall be used in any calculation using the hash function output
  during the generation or verification of a digital signature.

In section 6.1 they define $n$ as the order of the generator, which makes the wording

  leftmost $n$ bits

wrong. Although it's clear they meant the bit size of $n$.

Which means:

You don't need a bigger curve
BouncyCastle implementation looks correct


Identification of Confusion Component in a Cipher Confusion is a necessary component of any encryption algorithm. S-boxes play an important role in ensuring confusion.
If an encryption algorithm does not use any S-box (rather some other Operations/technique to provide confusion), then by looking at Cipher Algorithm,  how can we identify which component is providing confusion.

You can express the output of a cipher in terms of XOR and AND gates applied to the ciphers input bits.

"Confusion" implies an increase in the degree of the equations that represent the bits of cipher output. Basically, the goal of confusion is to make the expressions that represent the bits of the cipher too complex to be able to work with, and to make it to where there is no linear expression that can be used to approximate the actual expression; A linear approximation would imply a % chance that a given set of inputs will make the expressions easy to work with.

For a boolean circuit (i.e an s-box), AND and OR gates will increase the degree of the equations. XOR and shift/rotations will not increase the degree of the equations. (They increase the number of terms in a given equation, which is helpful in making more complex expressions).

Another technique to obtain non-linearity is to interleave operations from different fields, for example mixing bitwise XOR and integer ADD operations. However, if you were to pull apart the adder circuit, you would find AND/OR gates providing the non-linearity yet again.

So look for the AND/OR gates, and you should find the source of confusion in the design.


What real life OpenPGP public key has the biggest amount of signatures on it? Have you ever seen key with dozens or 100+ signatures? Link to it will be very much appreciated.

I have read that old Zimmermann's key had a lot of signatures on it, but I was not able to find it. In fact when I search MIT key server I am not able to search for 'Zimmermann' name at all for some reason.

Over time the idea of what is a strong enough key has changed and keyservers have removed keys they consider unacceptablly weak. IIRC zimmerman moved on from pgp a long time ago and I expect all his keys have been removed from keyservers due to being weak.

I was able to find a key with 230 signatures just by educated guesswork. https://pgp.cs.uu.nl/stats/587979573442684e.html . Unfortunately while that site shows data on individual keys it doesn't seem to have any ability to search/sort keys.

Data on the relationships between all keys in the "strong set" is available in "Wot files" the WoT files can be downsloaded from https://pgp.cs.uu.nl/archive/wot-0.3/ , software for working with them is available at https://pgp.cs.uu.nl/wotsap/wotsap.html . I imagine if you really want an answer to which key has the most signatures it should be possible to write code to extract it from the WoT file.

I would note that it's easy to generate a bunch of keys with random name and cross-sign them with your main key. Number of signatures on a key alone is not really a good indication of anything useful.


Exhausting the entropy of a hash function In the case of password storage, consider the following:

I have an idea that one can exhaust the entropy of input to the MD5 function by using a 128 bit random value as the password (indeed, any hash function, using the output length as input). Is this a correct assumption, or is the entropy exhausted at 123.4 bit, this being the best attack to date? Or does this only apply to hash functions that for every value in the interval $[0, 2^{L}]$ provide another unique value in the same interval?

I hope you understand what I'm trying to ask here - I see that I have a hard time explaining it clearly. What I want to do with this idea is argue that in the case of MD5 stored passwords, there is no reason to use passwords with a higher entropy than the hash itself.

Entropy is not gas -- you do not "consume" it.

In the case of hashing passwords, entropy is a measure of what the password could have been. A password with "$n$ bits of entropy" is a password such that breaking it by dictionary attack (trying potential passwords until the right one is found) has average cost $2^{n-1}$.

It is useless to have a password entropy much beyond the output length of the employed hash function, because if you hash to $k$ bits, then trying random passwords will succeed with probability $2^{-k}$, hence average cost $2^{k}$. Thus, no need to go beyond $k+1$ bits or entropy for the password.

It is also useless to have a password entropy beyond the point where dictionary attacks are ludicrously expensive, regardless of the hash function output size. With today's technology, an 80-bit password entropy is already enough to defeat such endeavours. Actually, if the password hashing is done properly (with a slow password processing function, like bcrypt), then lower entropies are already fine (that's the point of slow hashing: to make low password entropy more tolerable).


Is the discretization of the Guassian distribution on torus still a discrete Gaussian distribution? Let $\rho_s(x) = e^{-\pi x^2/s^2}$ be the Gaussian measures, then the discrete Gaussian distribution on $\mathbb{Z}$ could be defined as $D_{\mathbb{Z},s}(x) = \rho_s(x)/\sum_{n\in \mathbb{Z}}\rho_s(n)$.
In [Regev05], the distribution $\Psi_s(r)$ on torus $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ is defined :
$$\Psi_s(r)=\sum_{k=-\infty}^{+\infty}\frac1s\cdot exp\left(-\pi \left(\frac{r-k}{s}\right)^2 \right), r\in \mathbb{T}$$
then, it can be discretized as a distribution on $\mathbb{Z}_p$ :
$$\overline{\Psi}_s(i) = \int_{(i-1/2)/p}^{(i+1/2)/p}\Psi_s(x)dx, \ \ i\in \mathbb{Z}_p$$
What I want to know is: if the $D_{\mathbb{Z},s} \mod p$ is the same as the $\overline{\Psi}_s$ on $\mathbb{Z}_p$ ?

There are two ways to discretize: rounding and conditioning.
The first discretization you use to define $D_{\mathbb Z,s}$ from $\rho_s$ is using conditionning.
The second one defining $\bar \Psi_s$ from $\Psi_s$ is using rounding (the density at integer $x$ of the former distribution is given the total density of the interval $[x-\frac 1 2, x+ \frac 12]$ of the latter distribution).
So, because of this, the two distributions are not the same. However, for large $s$, they would be very close to each other, because they would both be very close to uniform.
To summarize: the moding (ie going from R to the torus) and discretizing do commute, but only if you use the same discretization on both path.


What cryptography primitives can help me (generate unforgeable tag)? I have a read-only public bulletin board that It contains a series of information to form:
$$[(a_1,g^{a'_1 \cdot m}), (a_2,g^{a'_2 \cdot m}), \cdots ,(a_n,g^{a'_n \cdot m})] \ ,$$
where $a_i\in\{0,1\}^n$ and $a'_i, m \in \mathbb{F}^*_q$ ($a'_i$ is output a PRF on input $a_i$).

I want to produce tags that are not forgeable, and also are validated by their public information. For example, for pair $((a_i,a_j),t_1,t_2)$, first fetch $(a_i,g^{a'_i \cdot m})$ and $(a_j,g^{a'_j \cdot m})$, and then validate the tags as follows:

$$\big (g^{a'_i \cdot m} \big) ^ {t_1} \stackrel{?}{=} \big (g^{a'_j \cdot m} \big) ^ {t_2}$$

What cryptography primitives can help me?

Assuming that all the $m$ values are the same, then about the only thing to do with the precise verification procedure you specified is to set:

$$t_i = c \cdot {a'_i}^{-1}$$

for some secret constant $c$ (which needs to be the same for every tag).

This would appear to work (and any value of $c$ would work)... until some $a'_j$ value is leaked; then, the attacker could rederive $c$, and thus recover all the $a'_i$ values from the corresponding $t_i$ values.


Can padding length, and thus plaintext length, be considered public information when using aes-cbc? Right now I'm using a simple padding system that takes the plaintext, hashes it with SHA512, and appends $x$ bytes of the hash as padding where $x$ is the delta between the plaintext and nearest blocksize multiple.

Is this considered a secure method of padding the message? I am also authenticating the encrypted data using HMAC-SHA512, would this effect the security?

For AES CBC i would suggest you stick to the standards.

The PKCS7 padding scheme is pretty easy to implement and has been tested extensively now that its been out in the public for a while. I had implemented PKCS7 padding for my AES CBC cipher a few weeks ago and you can see the code here if it helps.

Note that hashing by itself does not provide you with authentication, you will need a MAC (Message Authentication Code) for that. If you like using the SHA family, you can use something like HMAC-SHA256.

Is there any particular reason why you wish to use hashed data as a pad? If you are looking for authenticated encryption, you should stick to the standards like GCM for AES.


BER or DER X9.62 for ECDSA signature The signature format for ECDSA signatures can be encoded using ASN.1 integers according to X9.62 or it can comprise of two integers with the same size as the key size.

In case the X9.62 format is used is it mandatory to use DER encoding (distinguished encoding rules) of the result, or is BER encoding (basic encoding rules) also acceptable?

Annex E of X9.62-2005 says:

  Annex E provides the syntax for elliptic curve cryptography, including domain parameters, keys and signatures, according to Abstract Syntax Notation One (ASN.1). Although it is not required that elliptic curve domain parameters, keys, and signatures, be represented with ASN.1 syntax, if they are so represented, then their syntax shall be as defined here. Though it is likely that these ASN.1 definitions will be encoded using the Distinguished Encoding Rules (DER), other encoding rules may also be used.

RFC 3279, section 2.2.3 mandates use of ASN.1 to represent signatures, but, surprisingly, says nothing about encoding rules (whereas it explicitly requires DER for public keys).

Some cryptographic libraries insist on strict DER. Project Wycheproof contains some test vectors that check that (the reason which is given is: "to limit signature malleability"). OpenSSL is one such library: after decoding the incoming signature, it reencodes it with strict DER rules and checks that it obtains the exact same sequence of bytes. Apparently, this is due to a "vulnerability" known as CVE-2014-8275, where some systems implement blacklist on certificates by fingerprint, i.e. hash of the whole certificate (and not just the internal to-be-signed). In my opinion, blacklist systems do not offer good security and it was pretty daft to use the fingerprints for that, but apparently the OpenSSL developers thought that they needed to enforce strict DER encoding of both (EC)DSA signatures, and the outer layer of the certificate itself.

Other libraries accept variants. For instance, BearSSL requires the lengths to be explicit, but not necessarily minimal (i.e. some extra leading bytes of value 0x00 are accepted for the two INTEGER values).

From these data points, it seems that non-strict-DER encodings of signatures are nominally acceptable, as per the relevant standards, but they won't be accepted everywhere. Thus, in practice, any ECDSA library should ensure that the signatures it produces follow strict DER rules.


Creating cryptographic algorithms at runtime Would it be possible to create a program with which to create a cryptographic algorithm (i.e. encryption or hash) using well-known elements of other algorithms in the same way that algorithms "reuse" systems such as Feistel's structure? That is, eventually decide to use an algorithm that combines the Rijndael KeySchedule, and the Pseudo-Hadamard Transform. All this correctly applying the concepts of diffusion and confusion of Shannon.

The objective of this would be during a communication to change cryptosystem repeatedly, so that if you want to do cryptanalysis of the messages you have to do cryptanalysis on several different algorithms. In this way a kind of PFS (Perfect Forward Secrecy) would also be obtained.

EDIT: I wasn't proposing the use of security by obscurity, in fact I thought the negotiation of the new cryptosystem as public, in the same way the negotiation of the cryptosystem in TLS is public, and only the key is confidential (being shared using a well-known key distribution algorithm, like DH or RSA). On the other hand I know the definition of Forward Secrecy, that's why I said "a kind of". I was referring to the scenario in which an attacker discovers a vulnerability in a previous algorithm, but because currently is being used another totally different, the cryptanalysis is different now, and the information transmitted before and after the broken algorithm would remain unrevealed, similar to the concept of PFS.

Regarding the use of algorithms already used (and therefore proven in theory their safety), I do not plan to create a new system that is adopted worldwide (or even on a small scale), I only played with the possibility of creating a system like this so that, for example, the AES is found to be ineffective, not all communications made since the adoption of the AES (or any other algorithm) are disclosed. I mean, I propose the possibility of not trusting a single algorithm, and given the problem of the existence of infinity of communications, the solution would be to generate infinity of algorithms.

This doesn't add new security as much as it just shifts it.

Encryption algorithms are carefully studied.  Hmm... I didn't make that emphatic enough.  Encryption algorithms are C A R E F U L L Y studied.   There. That's better.

There are all sorts of tiny nuances to be had when designing an algorithm.  A famous example were some of the  S-Boxes in DES which were developed in a classified environment.  Many thought they were a NSA backdoor.  Several years later, differential cryptoanalysis was "discovered," and suddenly we found that these S-Boxes were the thing that prevented such an attack (thus the NSA had clearly known about these attacks for some while).  This was not a "just got lucky by combining the right bits" thing.  It was carefully thought out.

So the likelihood that your mix-and-match algorithm is breakable is far greater than any of the carefully studied algorithms.  Far greater.  Its basically guaranteed that a dedicated attacker will break your algorithm.  The thing you have bought is anonymity.  By using a publicly accepted algorithm, you are using an algorithm that provides great value to attackers to break.  If they get access to your little secrets, they also get access to things like bank mainframes.

So you make yourself weaker against a reasonably determined attacker while making yourself a bit stronger against a very strong attacker like a state.  Or do you?

A final issue to deal with is that you're mixing and matching known algorithmic pieces, and from your comments the pieces you choose are know in public.  These algorithms were carefully studied, as I said before.  This also means the attacks that these algorithms had to be tuned against are also well known.  So all one needs to do is identify which basic pattern you are using, pull up a list of known attacks against it, and find out what attacks work.  Which puts you in a strange corner where an AI might actually have enough data available to it in a convenient enough form to take your encryption on.

And that would be something a highly skilled attacker would be able to do, so you didn't really solve anything.


Attack vectors introduced by compilers I have a question about attacks on the
implementation of cryptographic code that are enabled by compilation and compiler-optimisations. I am aware of this. Would
anyone be able to point me to other examples? In particular, are there examples of timing attacks that are enabled by compilation (in particular by compiler optimisations) that are not possible w.r.t. the semantics of the source language?

$\mathbf{Edit:}$ Let me illustrate what I mean by this in two ways.

First, sometimes the semantics of a programming language is given using a one-step reduction relation. In particular, the one-step reductions of equality might be specified like this.

For all values $x$: $x = x \rightarrow \mathtt{true}$.
For all values $x, y$ such that $x$ is not equal to $y$: $x = y \rightarrow \mathtt{false}$.

You can see the one step reductions as taking one unit of time, so in this model, all computations of equality take the same amount of time. But for complex data-structures like strings, lists or arrays, compilation would typically be to code that has data-dependent run-time (or power consumption or EM radiation or whatever is your favourite side-channel).

Second, I know that not all programming languages have nice, simple operational semantics like that. So another way of looking at the same problem is: if I compile a program twice, once with little/no optimisation turned on, and once with a high degree of compiler optimisation, would the latter open my executable vulnerable to attacks in ways that the former does not? I'm thinking in particular of the optimisations (tracing) JIT compilers do.

PS I don't have enough reputation to give more/better tags to my question. Please feel free to do so.

Not something I have a real life example of, just an idea.

Certain computationally intensive tasks can be done much faster using memoization. Now if the compiler manages to automatically use memoization for some piece of code that code might run much faster than what the language notation suggests. I'm not aware of any compiler actually doing this though.

In C++, for example, any optimization is allowed as long as observable behavior is preserved which includes accesses to volatile memory and calls to I/O library functions. The compiler is allowed to transform the program in any way otherwise.


What (Where) is the formal definition of Multiparty Computation? I'm just curious where we can see a (original) formal definition of MPC.
What (Where) is the formal definition of MPC?

We have a bunch of tools to build a MPC protocol.
Is oblivious transfer (or OT-extension) a part of MPC?

The wikipedia page on Multiparty Computation (MPC) would be a good start.
It gives a good introduction to the topic, and it will mention the relation with Oblivious Transfer.

I would say that, in general,

  MPC studies the development of protocols that allow a set of $n$ parties $P_1,\ldots,P_n$, where each $P_i$ has a private input $x_i$, to compute a function $(z_1,\ldots,z_n) = f(x_1,\ldots,x_n)$ of these inputs in such a way that party $P_i$ only learns the value $z_i$.

If you want a more precise definition you would have to define, among other things, the terms I have written in bold.
Some of the definitions can be found in the book Secure Multiparty Computation and Secret Sharing by Ronald Cramer, Ivan Bjerre Damgård and Jesper Buus Nielsen.
Even though this book is for a particular type of MPC, which is Information-Theoretic MPC, most of the definitions apply for the general case.

Intuitively:

A party is just some computer program running some code. It is typically formalized as a Turing machine, but it's precised by an interactive Turing machine in order to model the networking.
A protocol is just a set of rules that the parties follows.
Think of it as the source code of the program itself.
It indicates the parties what to do at what times in order to achieve the desired result
A party only learns $z_i$ if anything it has learned from the protocol can be simulated from only its input $x_i$ and the output $z_i$.
This is much harder to precise, and it is typically done via de Universal Composability framework (read the book I referenced above, for instance).

Now, Oblivious Transfer (OT) is just a particular function to be computed, and an OT protocol is simply an MPC protocol that allows for secure computation of this function.
The function can be described as $f(b,(m_0,m_1)) = (m_b,\lambda)$, where $\lambda$ simply means that the corresponding party gets no output.

Moreover, although a protocol for OT is an MPC protocol that only works for this specific function, it can be proven that you can build a general purpose MPC protocol (i.e. a protocol for any function) from an OT protocol.
Therefore, in some sense, OT and MPC are "the same" (more precisely, they are equivalent, in some specific sense).


Defining format-preserving encryption for natural language Assume we have plaintext in natural language. Can we use format-preserving encryption in such a way that the produced ciphertext cannot be distinguished from natural language?

The below is assuming a natural language is the one that has sentences from a well defined dictionary for that language (ex: oxford dictionary for english ).

We can do this with the standard approach for FPE i.e $rank-encrypt-derank$.
Build a $key-value$ pair map of all the  words in the language of preference  Where $key$ is the number and $value$ is the word. {Say from $1$ to $n$ }. $n$ being maximum number of words in dictionary.

Rank : For each word find the key which is a number
Encrypt: Apply the FPE algorithm of your choice (FF-1,2,3 OR FNR) or even simple fiestel network.
Derank the ciphertext of FPE algorithm which is a number by finding the respective word in the map. So the deranked word would be actual ciphertext

Decryption is similar .


Examples of modern, widely used ciphers that suddenly fell? RC4 and GOST are two major ciphers (defined as being widely used to encrypt large amounts of data) that fell to cryptanalysis (relatively) suddenly.  The first becoming totally broken and the second fell from $2^{256}$ bit security to $2^{99.5}$ bit security, weaker than AES-128.

Have any other modern and widely used ciphers fallen without much advance warning?

"Fallen" in this context means "become practically attackable, or close enough that use is strongly discouraged". And to limit the scope of my question, let’s please exclude antique ciphers that predate our modern understanding of cryptography.

Essentially, I am looking for one or more prominent cases where a modern cipher seemed secure and was in wide use for a substantial period of time, until suddenly it was broken (while still in wide use) and had to be abandoned due to that sudden break. One possible example of what I’m looking for would be RC4 as used in TLS, and the recent discoveries that “broke” it.

(PS: References to the cipher paper + the paper introducing the break would be a plus.)

This question is quite broad by specifying a sudden fall to cryptanalysis and therefore my answer might not be as complete as you wish it to be.

If by "become practically attackable, or close enough that use is strongly discouraged" you imply not an academic breach but assume a weaker attacker such as a single ciphertext attack, then there are quite a few ciphers that satisfies this condition. Under this assumption, modern block-ciphers are mainly vulnerable to brute force attack. Should the key length of DES be longer so we would not be able to do an exhaustive search then it would still retain a certain level of security (while its use still be strongly discouraged).

Moving to strongly used block ciphers, here are a few that have been academically broken or weakened to be considered as insecure.

FEAL (Block Cipher)

The first block-cipher that came to my mind with such characteristic is FEAL. It was design in 1987 and aimed to replace the DES by providing fast encryption capacities for 8-bit platforms. It was not widely used and (un)fortunately it was broken even before becoming a new standard in 1990.

Should you teach or would like to practice cryptanalysis, I would recommend breaking FEAL-4 (as 4 rounds) or FEAL-8. It is a great learning exercise.

Some resources :

Differential Cryptanalysis for dummies by Jon King
Differential Cryptanalysis of Feal and N-hash by Eli Biham and Adi Shamir

DES (Block Cipher)

DES is another example. Broken by differential cryptanalysis in 1990 by Eli Biham and Adi Shamir.

  In this paper we develop a new type of cryptanalytic attack which can break the reduced variant of DES with 8 rounds in a few minutes on a PC and can break any reduced variant of DES (with up to 15 rounds) in less than $2^{56}$ operations.

from their paper : Differential Cryptanalysis of DES-like Cryptosystems. I really recommend reading this article or at least the extended abstract.

Remark: To break the 16 rounds, one would need $2^{57}$ pairs. The number of cipher texts needed is twice the number of pairs.
On these pairs, only $2^5$ would be used (excluding the wrong pairs that can be easily discarded during the collection phase). Using 15 different characteristics with a probability of $2^{-56}$, 18 bits of the key could be found. Therefore this attack involves slightly more work than a brute-force attack. (Thx Jerry for pointing this out).

3 years later, Mitsuru Matsui introduced a new method to break DES.

  As a result it is possible to break a 8-round DES cipher with $2^{21}$ known-plaintexts and 16-round DES cipher with $2^{47}$ known-plaintexts, respectively. Moreover this method is applicable to an only-ciphertext attack in certain situations

from his paper: Linear Cryptanalysis Method for DES Cipher (another good reading).

A5/1 (Stream cipher)

Moving to stream cipher we have A5/1 which is responsible of the privacy of the communication between GSM and the antenna. Developed in 1987, with a key length of $64$ bits. In 1997, Golic presented an attack based on solving sets of linear equations which has a time complexity of $2^{40.16}$.
In 2000 Eli Biham and Orr Dunkelman  published an attack with a total work complexity of $2^{39.91}$ A5/1 clockings given $2^{20.8}$ bits of known plaintext. The attack requires 32 GB of data storage after a precomputation stage of $2^{38}$.
Remark: while A5/1 is completely broken (cf Snowden leaked files) it is still in use in our cell phones...

Some resources:

Real Time Cryptanalysis of A5/1 on a PC by Biryukov, Shamir and Wagner
A Real-World Attack Breaking A5/1 within Hours by Gendrullis, Novotný and Rupp (2008)
A Practical-Time Attack on the A5/3 Cryptosystem Used in Third Generation GSM Telephony by Dunkelman, Keller, and Shamir (2010)

RC4 (Stream cipher)

RC4 (as Rivest Cipher 4) is a stream cipher mainly used in SSL (1995), TLS (1999), WEP (1997) and WPA (2003/2004). It was designed in 1987 but the code was unknown until being leaked in September 1994 (security by obscurity, here I am...)

Some resources:

Weaknesses in the Key Scheduling Algorithm of RC4 by Fluhrer, Mantin and Shamir (2001)
Full Plaintext Recovery Attack on Broadcast RC4 by Isobe, Ohigashi, Watanabe, and Morii (2013)

MD5 (hash function)

Infamous hash function, designed in 1991. Five years later, Dobbertin announced a collision of the compression function of MD5.
In 2009, the complexity of the attack was in  $2^{39}$ (initial pre-image complexity is $2^{128}$.

SHA-0 (hash function)

Published in 1993, revised a few years later due to a significant flaw as SHA-1.
At CRYPTO 98, a first collision was found in $2^{61}$ (initial complexity in $2^{80}$.
In February 2005, an attack by Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu was announced which could find collisions in SHA-0 in $2^{39}$ operations. Another attack in 2008 applying the boomerang attack brought the complexity of finding collisions down to $2^{33.6}$.

SHA-1 (hash function)

Published in 1995 as a revision of SHA-0 (see above), it has been first weakened with attacks of complexities:

$2^{69}$ hashes, per Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu: Finding Collisions in the Full SHA-1, in proccedings of Crypto 2005),
$2^{63}$ hashes, per Xiaoyun Wang, Andrew C Yao, Frances Yao: Cryptanalysis on SHA-1, rump session of Crypto 2005; see also Martin Cochran: Notes on the Wang et al. $2^{63}$ SHA-1 Differential Path, in IACR eprint archives, 2007),
$2^{61}$ hashes, per Marc Stevens: New collision attacks on SHA-1 based on optimal joint local-collision analysis (in proceedings of Eurocrypt 2013, also freely available from the author's website).
$2^{57.5}$ call of the compression function, per Marc Stevens, Pierre Karpman and Thomas Peyrin:  Freestart collision for full SHA-1, 2015.
Until finally The first collision for full SHA-1 was found by Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov and published at CRYPTO 2017 (Best Paper Award) with $2^{63}$ calls to the compression function.

I'm probably missing a lot of other block ciphers, but these are the ones mainly known to my knowledge.


RSA Certificate Owner and Issuer line meanings? Apologies if this question is not in the right place.

I've recently been looking through some RSA certificates ( specifically, Android apk .rsa files) and I'm having trouble deciphering the one and two letter combinations in the Owner/Issuer lines.

ex: CN, OU, O, L, ST, C

L, ST, and C are Location, State and Country, I think, but what are the others?

CN is common name, OU is orginizational unit, O = organization.

So we could have CN="John Johnson", OU="Sales", O="Acme Corp." or something like that.

http://docs.oracle.com/javase/1.4.2/docs/tooldocs/windows/keytool.html only mentions these, but I've seen Email as well.


Finding a secret cipher given the key and known plaintext? Let $x,y,k$ be plain text, cipher text and key respectively. Also suppose $\operatorname{Enc}$ is the algorithm of encryption for block cipher with size $n$. So we have
$$\operatorname{Enc}_k(x)=y$$

We know that if $x,y$ are given finding $k$ for big $n$ is so hard. Now we change the problem:

Let $k$(with size $l$) be given and $\operatorname{Enc}$ secret. We want to find the function for $\operatorname{Enc}$. At least how many $(x,y)$ are needed to find $\operatorname{Enc}$?

As fgrieu hints at in the comments, it is not in general possible to find $\operatorname{Enc}$. Otherwise you would be able to break an arbitrary block cipher, because the key of any block cipher can be cast as part of the algorithm instead.

Even if you ignore the computational cost, there is no way to find $\operatorname{Enc}$ given values for only one $k$, even if you know all pairs $x, y$ for that key. There is of course a limited number of (distinct) $n$-bit block ciphers with $l$-bit keys, but the different keys can be completely independent.

For example, I could define AES' which works just like AES, except with the key value $42$ it performs the identity permutation instead. You could not know that difference from observing the outputs for any other keys.


Do these new insights into prime numbers affect encryption security? Quanta Magazine reports:

Two mathematicians have uncovered a simple, previously unnoticed property of prime numbers [...]. Prime numbers, it seems, have decided preferences about the final digits of the primes that immediately follow them.
Among the first billion prime numbers, for instance, a prime ending in 9 is almost 65 percent more likely to be followed by a prime ending in 1 than another prime ending in 9.

Do these insights make breaking keys based on primes more mathematically plausible in a shorter amount of time?

No, because these new insights only affect the discovery and patterns regarding finding new prime numbers.  In order to break existing encryption algorithms that rely on primes such as RSA, you'd have to have a breakthrough in discovering how to factor integers into primes.

Primes are used in encryption keys as the basis of their generation:  two large primes are multiplied together to form a very large number.  The difficulty of factoring this large number to discover its prime roots is essentially the protection the cryptosystem offers.  Since you already have the primes (the private key, essentially), you need not factor the number and can immediately decrypt it.

Since the new discovery only relates to patterns prime numbers take which may assist a search for even larger prime numbers than already known, and not in factoring multiples of prime numbers, this discovery should be inconsequential for cryptography.


Tampering with Contents Before MAC Is there a way to modify the contents of data being sent between two parties in such a way that the MAC verification algorithm will not detect the tampering?

Not if

a secure MAC is chosen (e.g., HMAC-SHA256, CBC-MAC)
the MAC is used correctly (e.g., not reusing a CBC-MAC key for encryption), and
the secret MAC key is unknown by the attacker

That's literally the entire point of a MAC.


On an EKE (Encrypted Key Exchange) what would happen if asymmetric key would be symmetric? On EKE where the user sends a password encrypted public key and receives a password encrypted and public key encrypted secret key. What would happen if these asymmetrical keys would become symmetrical?

On EKE where the user sends a password encrypted public key and receives a password encrypted and public key encrypted secret key.

That's not the original meaning of EKE (which was a password encrypted Diffie Hellman exchange), but the above modification makes sense (if perhaps a bit dangerous), and so lets consider what would happen if we replace the public key encryption with a symmetric one.

In your revised scheme, the Client (Alice) would select a random symmetric key $K$, encrypt it with the password to form $E_{password}(K)$ and send that.  Then, the Server (Bob) would decrypt the ciphertext (using his password) to recover $K$.  Bob then picks a secret key $S$, and encrypts it with both the Alice's symmetric key $K$, and the password, forming $E_{password}(E_K(S))$.  Alice then unwraps $S$, and uses it somehow, perhaps to encrypt a message to Bob.

Now, consider someone listening it; they here $E_{password}(K), E_{password}(E_K(S))$, and $E_S(\text{known text})$.

The don't know $password$, however if they have a guess of the password $password'$, they can attempt to decrypt $E_{password}(K)$ with $password'$, coming up with a value $K'$ (and $K = K'$ if his guess was correct, that is, if $password = password'$).  Then, they can attempt to decrypt $E_{password}(E_K(S))$ with $password'$ and $K'$, resulting in $S'$ (and, again, $S = S'$ if his original guess was correct).  He can then attempt to decrypt $E_S(\text{known text})$; if he original guess is correct, then he will decrypt it properly, and so it will be obvious that his guess was correct.

This is entirely passive, and hence if he has a large dictionary of potential passwords, he can run this logic on each password.  If the correct password appeared somewhere in the dictionary, he'll find it (and then be able to listen into the entire conversation).

This doesn't happen with EKE (either version); if Alice encrypts a random public key, even if the correct password would recover it, he can't use it do decrypt Bob's reply.


DLP based crypto systems with multiple independent generators One example of a DLP based crypto system (or rather DDH based crypto system) where the public key parameters include two independent generators of the subgroup, is Cramer Shoup. Since the security proof of this scheme is based on DDH, it seems at least one of the two generators has to be uniformly chosen anew for each public key, and made part of the public key, rather than made part of domain parameters that are shared between multiple key pairs.

This seems a bit impractical, assuming you want a crypto system where the public key parameters are shared between multiple key pairs, and the individual public keys contain no more information than necessary. Furthermore it is a bit discomforting that e.g. Cramer Shoup does not include a method for verifying the validity of the generator choices, even though implicit verification is entailed by the trust model - you can e.g. test that the prime parameters are indeed prime, but it is harder to test if the generators have been deliberately chosen to facilitate discrete logarithm calculation.

Does this matter in the case of Cramer Shoup? I don't know, and that's not really my primary question interest. It might be noted that the relation between the two generators $g_1, g_2$ is not retained as part of the private key, and that the owner of the private key at no point in the normal operation of the scheme gets to prove that these generators have been correctly generated, but that might be insignificant. Rather, I am asking whether other schemes exist that also make use of more than one generator, and which might include those generators in domain parameters rather than include them in the individual public key.

Just a crazy idea: Suppose, for instance, you choose a prime $p$ and a prime $q$ such that $p = 2kq + 1$ and such that the calculation of $\log_23 (\mod p)$ and $\log_32 (\mod p)$ is conjectured to be DLP-hard in $Z_p^*$. In such case the generators $g_1 = 2^{2k}(\mod p)$ and $g_2 = 3^{2k}(\mod p)$ might be deterministically generated (which has its own advantages with respect to assurance of validity) and included as part of the system parameters, provided that the security proof for the crypto system is such that it is sufficient that the relation between the generators $g_1$ and $g_2$ is DLP-hard.

Does there exist any public key crypto system for which choosing such public key parameters would make sense, i.e. one that rests on the assumption that $\log_{g_1}g_2$ and $\log_{g_2}g_1$ are DLP-hard, rather than the assumption that the $g_2$ element in $(g_1,g_2)$ is indistinguishable from random?

In order for such a crypto system to exist, the following four criteria have to be met:

To begin with, the crypto system obviously has to use certain operations, such as modular exponentiation in $Z^*_p$, and have certain parameters, such as use multiple generators for a suitable subgroup.
Finding $log_23\mod p$ and $log_32\mod p$ have to be hard problems. If $p-1$ e.g. is divisible by a smooth number, they might not be hard problems. There might be other criteria I am not aware of.
The crypto system has to be based on a hard problem that is reducible to DLP, such as REPRESENTATION. There might be other hard problems that qualify.
There has to be specific reasons, either practical reasons or security reasons, for using deterministically generated generators instead of random ones (such as storage/time/bandwidth requirements, or inclusion of the generators in domain parameters). As pointed out in one of the answers below, in some cases such reasons do not exist. That doesn't however entail that such reasons can't exist in other cases.

It's not impractical.  Choosing a random generator $g$ is easy and can be done efficiently.  It's efficient enough that it wouldn't be a problem to generate a random generator when you generate your keypair.  I think your premise (your assumption that this is a problem or that it should be discomforting) is not valid.  Consequently, I don't see the relevance of the question.
Let me elaborate a bit.  There are two kinds of values that might be floating around:

Domain parameters are parameters that are shared by many users.  For instance, in a discrete-log based cryptosystem, if the modulus $p$ is shared by everyone, then it is a domain parameter.

Individual parameters (to coin a term) are values that are used by a single party, and are generated by the same party who uses/relies upon them.  For instance, a user's private key is an individual parameter, since it is generated by that user and only used by that user.

These two different kinds of values have different security and verifiability requirements:

Domain parameters are critical and particularly sensitive, since they're generated by one person (e.g., a CA or trusted authority) but used and relied upon by everyone else.  If the CA secretly and dishonestly constructs a domain parameter in a way that introduces a backdoor (rather than following the algorithm they were supposed to use), everyone loses.  That's very bad.  The standard mitigation is to provide everyone a way to verify that the CA generated the domain parameter honestly.
In summary, domain parameters must be verifiable.

Individual parameters don't have this problem.  There's no reason for Alice to secretly embed a backdoor in her private key, since the only person's security who is harmed is Alice's (at worst others may obtain the ability to eavesdrop on messages encrypted to Alice, but a malicious Alice could always have achieved a similar effect simply by publishing all the messages she receives, and there's no way for others to verify Alice hasn't done that).  There's no way for Bob to verify that Alice has kept the messages he sends her secret.  Therefore, there's no reason why Bob would need to verify that Alice generated her private key honestly.  For instance, we don't require that RSA provide a way for Bob to verify that Alice generated her RSA secret key using the algorithm she was supposed to use; if she does something different, we say it is her tough luck.  There's no point in trying to prohibit what you can't prevent.
In summary, individual parameters do not need to be verifiable, and there's no clear value to verifiability.

This means that your question is based upon a faulty premise.  Your premise is that there's something wrong with a cryptosystem if the public key (an individual parameter) is not verifiable.  This premise is not accurate; actually, there's nothing wrong with a cryptosystem where the public and private keys are not verifiable by third parties.  We use cryptosystems like that all the time.  Therefore, the best answer to the question is to un-ask the question.
I am making numerous assumptions about what you are asking.  I confess I might not have understood what you really wanted to know, and what problem you are trying to solve; if so, my apologies.


RoR Attacks on modified Feistel Network It is known that a Feistel Network containing 3 rounds is relatively secure against Chosen Plaintext attacks. Now as a game I was given the task to find a possible attack against a Feistel Network with 3 rounds, but the first encryption with a key has no effect. (So the input in the second function is just $L \oplus R$). It should be possible to find out, with significant probability and only to Chosen Plaintexts, if the network produces the results of the chosen inputs or just a random sequence. I just can't wrap my head around it, can anyone help me there?

Thank you in advance!

If you have three rounds and the encryption in the first round has no effect, then the left side of the third round is

$$ L_3 = R_0~\oplus~F(L_0 \oplus R_0, K_2) $$

and when you exchange the left and right side of the initial block

$$ L_3' = L_0~\oplus~F(R_0 \oplus L_0, K_2) = L_0~\oplus~F(L_0 \oplus R_0, K_2) $$

So

$$ L_3~\oplus~L_3' = R_0~\oplus~L_0 $$

This property lets you distinguish the output of the Feistel network from random.


CP-ABE (Bethencourt): How KeyGen computes $D=g^{(\alpha+r)/\beta}$? I have one doubt from CP-ABE KeyGen algorithm (paper).

In Setup, master key is $MK=(\beta, g^\alpha)$.

In KeyGen(MK, S), they say generate random number $r$ and compute $D=g^{(\alpha+r)/\beta}$.

How one calculates $D$ from $g^\alpha$ ? ($\alpha$ is not part of $MK$).

Does he calculate $1/\beta$ and computes $D$ as below?

$\qquad D = {(g^\alpha.g^r)}^{1/\beta}$

I am not sure I did this the right way? Am I missing something here. Please help me understand.

Thanks.

Does he calculate $1/\beta$ and computes $D$ as below?

  $\qquad D = {(g^\alpha \cdot g^r)}^{1/\beta}$

Yes, that is what he does; as you know, ${(g^\alpha \cdot g^r)}^{1/\beta} = {(g^{\alpha+r})}^{1/\beta} = g^{(\alpha+r)/\beta}$.

He computes $1/\beta$ modulo $p$ (the order of $g$); this can be done by either the extended Euclidean method, or (because $p$ is prime) by using $1/\beta = \beta ^ {p-2}$


How to use a secret to allow the generation of public keys, where the private keys can be calculated later Alice has a secret S and publishes some public information P, about S which is insufficient to recreate S.

Is there a way that Bob can use P, and an arbitrary integer I to create an (EC?) public key for which Alice can subsequently calculate the private key, given I?

Does this requirement already have a name?

Bob was a bad name.  Bob is anyone other than Alice.  Alice knows nothing of specific Bobs.

The point of the question is that I want all the Bobs of the world to be able to generate public keys, for which Alice can later calculate the corresponding private key, given the identifying integer I.  (Where I could be a random 256bit integer, if it's more secure.)

This is Alice saying to the world: 'Here's some information P, now all of you can make different public keys, for which I can later calculate the private keys, if and when I need to'.

The requirement is to get around the issue that Alice might be offline when a Bob requests a public key from her.  I do not what the world to know which public keys are owned by Alice, so she can't just publish 100 public keys for general use.

This problem would be solved if P could be an array of 2^256 public keys (for which she has stored the 2^256 private keys that were used to generate the public keys) but this is not feasible for computational and storage reasons.  I'm looking for something possible which will achieve the same ends.

To expand on Ricky's comment, assuming Alice and Bob are the only participants, they can use an identity-based encryption scheme where Alice also acts as the trusted third-party ("Private Key Generator" in the Wikipedia article). Namely:

Alice puts on her PKG hat, and generates the public parameters of the system and a secret which will be used later.
Alice removes her PKG hat, she broadcats the public parameters and says: anybody who wishes to send me messages, just use any string you want as your public key and send it to me along with your ciphertexts.
All the Bobs of the world encrypt messages using their chosen public keys and send the ciphertexts and the public keys to Alice.
When Alice wants to decrypt a message, she puts on her PKG hat and obtains the private key associated with the public key which was used to encrypt the message.
Alice removes her PKG hat and uses the private key to decrypt the message. Optionally, she may store the private key so that she does not have to do step 4 again if she receives another message encrypted with the same public key.

The only requirement is that when Alice wants to decrypt a message, she must know which public key it was encrypted with. There is no requirement on the public keys themselves, including how or by whom they are generated. In any case, Alice is the only one who can decrypt since she is the only one who knows the secret. Matching a specific Bob to a specific public key seems to make it more or less equivalent to a regular cryptosystem.


Is the SILC protocol still used? I'm looking into implementing a private SILC server for friends (and possibly their friends).

And after visiting the Wikipedia entry for SILC protocol, it seems all the official pages linked at the bottom are dead with only a few anon servers here and there.

Is it still being used nowadays?
And if it is ... where(online) are more resources (howto's and/or daemon software)?

And if it isn't used anymore... are there any security reasons involved?

Is the security model or the used cryptographic protocols and algorithms flawed thanks to exploit XYZ?

A complementary question would be: are there any more current alternatives available now?

another complimentary question would be:are there any public and/or anon servers still online ?

and ..does it use much system ressources on a server let's say for 50 concurrent users ?
(this is just a complimentary question if you feel you can answer :)

Yes, SILC is still used daily by a few of us die hards. :-)

I, too, noticed the other day that the official source repos are dead. Perhaps we can get them up on Github or other hosting site.

I haven't heard of any flaws discovered in the protocol itself, but I haven't heard of anyone reviewing it lately either.


A discrete-log-like problem, with matrices: given $A^k x$, find $k$ Let $p$ be a large prime; we will work in $GF(p)$.  Let $A$ be a $n\times n$ matrix.  Also, let $x$ be a $n$-vector and $k$ a positive integer.

Suppose we are given $p$, $A$, $x$, and $y$.  The goal is to find a $k$ that satisfies $A^k x = y$.  Is there an efficient algorithm that solves this problem?  You can assume you are promised that at least one solution exists, if you want.

More generally, what is the complexity of this problem?  How does its hardness relate to the hardness of the standard discrete log problem modulo $p$?  I'm pretty sure the answer will depend upon the matrix $A$.  Can we classify for which matrices $A$ this is as hard as the standard discrete log problem, for which it is harder, for which it is easier, for which it can be solved in polynomial time?

The answer appears to be similar to one that I asked on cstheory.SE about Discrete log in GL(2,p) (i.e., given $A,B$, find $k$ such that $A^k=B$).  In this question we are given less information, but similar techniques should still apply.

Start by putting $A$ into Jordan normal form, i.e., write $A=PJP^{-1}$ where $J$ is the Jordan normal form and $P$ is a suitably chosen invertible matrix.  Then $A^k = PJ^k P^{-1}$, so without loss of generality I only need to consider possibilities for $A$ that are already in Jordan normal form.  This means that $A$ can be expressed as a concatenation of Jordan blocks:
$$A = \begin{pmatrix} J_1 \\&\ddots\\ &&J_n\end{pmatrix}.$$

Each Jordan block gives us an independent system of equations, so let me look at a single Jordan block at a time.  We can break this down into cases, based upon the size of the Jordan block $J$:

A size-1 Jordan block. Suppose $J$ is a $1\times 1$ Jordan block, i.e.,
$$J=\begin{pmatrix} \lambda \end{pmatrix}.$$
Then it is easy to see that the problem is exactly as hard as the discrete log to base $\lambda$ (unless $x=0$ in this component, in which case it is unsolvable for information-theoretic reasons).
A size-2 Jordan block. Suppose $J$ is a $2\times 2$ Jordan block, i.e.,
$$J = \begin{pmatrix} \lambda &1\\ 0 &\lambda \end{pmatrix}$$
where $\lambda \ne 0$.  A simple induction shows that
$$J^k = \begin{pmatrix} \lambda^k &k\lambda^{k-1}\\ 0 &\lambda^k \end{pmatrix}.$$
Let $x=(x_1, x_2)$ and $y=(y_1, y_2)$.  Then we obtain the linear equations
\begin{align*}
\lambda^k x_1 + k\lambda^{k-1} x_2 &= y_1\\
\lambda^k x_2 &= y_2
\end{align*}
which has the solution
$$k = \lambda (y_1 - x_1 y_2/x_2)/x_2.$$
We see that as long as $x_2 \ne 0$, the problem is easy and we can solve for $k$ with a little bit of arithmetic (no discrete log needed).  If $x_2=0$, I'd conjecture that this case is hard.
A larger Jordan block. If we have a larger Jordan block, say $m \times m$, basically the same thing happens.  The top row of $J^k$ is $(\lambda^k, k \lambda^{k-1}, {k \choose 2} \lambda^{k-2}, \dots)$, and each subsequent row is a right-shift of the one before it.  Then, as long as $(x_2,x_3,\dots,x_m) \ne (0,0,\dots,0)$, we can solve for $k$ easily as in the $2\times 2$ case.

So, each Jordan block gives us a chance to solve for $k$.  If any of the Jordan blocks are easy, we learn $k$.  If all of the Jordan blocks are hard, learning $k$ is hard.

In summary: If the Jordan normal form of $A$ is diagonal, and at least one of the diagonal elements is such that discrete log to that base is hard, then this problem is as hard as the discrete log.  On the other hand, if the Jordan normal form is not diagonal---i.e., if it has at least one Jordan block of size $>1$---then the problem is easy (except in corner cases where the wrong components of $x$ happens to be zero).


How can I show RSA OAEP IND-CPA secure How can I show, that RSA with OAEP is IND-CPA secure by using G,H one way function?

RSA-OAEP
Recall that RSA-OAEP is defined as follows (with $m$ being the message to encrypt, $G$ and $H$ being random oracles and $(e, N)$ being a standard RSA public key):
$Encode$:

Select a random $k$-bit integer $r$.
Pad out $m$ with $0$s to length $l = |N| - k$.
Compute $X = G(r) \oplus m_{padded}$
Compute $Y = r \oplus H(X)$
Return $X || Y$

$Decode$

Compute $r = Y \oplus H(X)$
Compute $m_{padded} = X \oplus G(r)$
Strip off the $0$s from $m_{padded}$ to recover $m$

IND-CPA Game
The IND-CPA game in this case is as follows:

The adversary selects two messages $m_0, m_1$ and submits them to the an encryption oracle.
The encryption oracle samples $b \in \{0, 1\}$ and computes $c = \text{RSA-OAEP}(m_b)$.
The adversary is free to perform more encryptions. To conclude, the adversary must guess $b$ corresponding to the message that was encrypted.

If the adversary can guess $b$ with non-negligible advantage the scheme is not IND-CPA.
Sketch of proof that RSA-OAEP is IND-CPA
The basic idea of the proof is that in order to recover $m_b$ from $c$ the adversary must be able to recover the entirety of $X$ and $Y$ from $c$ (recall that $c = \text{RSA-OAEP}(m_b) = \text{RSA}(X||Y)$). This is because to recover $m$ we must be able to compute $r = Y \oplus H(X)$. If we are missing even one bit of $X$ then $H(X)$ will give us a uniform random value (remember $H$ is a random oracle), and our $r$ value will be totally wrong (i.e. we learn nothing of the true value of $r$). The same is true of $Y$, if we fail to recover even one bit of $Y$ we will compute $r$ incorrectly, and as $G$ is also a random oracle  $m_{padded} = X \oplus G(r)$ will again give us a uniform random value, revealing nothing about the actual value of $m$. Therefore adversary must be able to recover all of $X||Y$ to learn anything about $m$ which under the assumed hardness of the RSA Problem is not considered computationally feasible. Thus the adversary has no better chance than guessing $b$ and has negligible advantage, making the scheme IND-CPA.