Show that there is an efficient zero knowledge proof for any language $L \in NP$ Let $(P,V)$ be an efficient zero-knowledge interactive proof for some language $A \in NP$ that is $(T,\epsilon)-\text{sound}$ and $(T,\epsilon)-\text{ZK}$.
I want to show that for every language $L$ that is reducible to $A$ there is also such an efficient zero-knowledge interactive proof $(P_2, V_2)$ which is also $(T,\epsilon)-\text{sound}$ and $(T,\epsilon)-\text{ZK}$.
Well, I am not sure how exactly to start to describe such $(P_2, V_2)$, but maybe I don't understand this completely since it seems there is only one straightforward way.
Since $L$ is reducible to $A$, then there is a Levin reduction from $L$ to $A$. Namely, there is a polynomial algorithm $R$ such that $R(x) \in A \leftrightarrow x \in A$, and there is a polynomial algorithm $W$ that maps a witness $w$ for $x \in L$ to the witness $W(x,w)$ for $R(x) \in A$.
My idea was to take the proof system $(P,V)$ and for the input $x$ apply $R(x)$ to simulate the original zero-knowledge proof for $A$.
However, it seems too trivial to me. Moreover, in this way I only get $(T-|R|,\epsilon)-\text{sound}$ and $(T-|R|,\epsilon)-\text{ZK}$, since I need to run the algorithm $R$.
Help Would be appreciated.

Your idea is correct. Although the running times of the honest prover and verifier do increase by the running time of $R$, this (somewhat counterintuitively) does not affect the concrete bounds for soundness and ZK (at least how they are usually defined).
Note that $T$-soundness does not really make sense for a proof system, since it is sound against even unbounded cheating provers. However, it does make sense for an argument system, and here we don’t really “lose” the reduction $R$’s runtime: any $T$-time cheating prover $P_2^*$ for some instance $x \notin L$ is itself a $T$-time cheating prover for the instance $R(x) \notin A$, because it fools the verifier $V$ (for language $A$) without doing any additional computation. The latter does not exist by assumption, so neither does the former.
Similar reasoning holds for ZK: a $T$-time cheating verifier $V_2^*$ for some instance $x\in L$ is itself a $T$-time cheating verifier for $R(x) \in A$, because it plays the role of $V$ in talking to $P$. So, we don’t need any additional computation to “gain knowledge” from an interaction with $P$ about $R(x)$.


Can I publish the accumulator trapdoor and still keep it secure? I'm implementing the Camenish-Lysyanskaya dynamic accumulator. It seems to me that the accumulator is provably secure because the trapdoor is unknown to the attacker.

The risks should be the fact that, given the Euler theorem, I can forge an element that is was not accumulated but still passes the test, namely:

$v^x\equiv v^{x\mod\phi}\mod n$

where $v$ is the accumulator without $x$, $\phi$ is the Euler function, and

$x\mod\phi\equiv x_f$

so we have a forged $x$ that passes the test.

What if I don't care about the factorization of n and I even publish $\phi$, but I just require that an acceptable integer $x_{acc}$ must be $A<x_{acc}<A+\phi$ with $A<\phi$.

This means that if, for example my input is the string "user1" this string will be hashed into an integer in the accepted interval.

If $\phi$ is large enough, I still can defy collisions and stop caring about keeping $\phi$ secret. All the possibly forged inputs fall automatically out of the specified interval so they will be discarded immediately. In other words there is no valid integer congruent to integer that maps the input "user1"

What do you think? Is this feasible? Or am I missing something obvious?
I understand I may have skipped something important, I am not in the field, please ask for clarifications.

I guess you are missing something.

If you know that the accumulator value is $a=v^{\prod_i x_i} \bmod n$ to a set of values $x_i$ and you know the factorization of $n$, then it is easy to for any arbitrary $y$ relatively prime to $n$ (in RSA accumulators you accumulate primes) a value $k$ such that $y\cdot k \equiv 1 \pmod{\varphi(n)}$ as the value $\varphi(n)$ is public. So anyone can pretend that any arbitrary value $y$ has been accumulated using $a^k$ as the membership witness and note that the verification $a\equiv (a^k)^y \bmod n$ holds.  I guess that you would not like to have that "feature".

So either you make the factorization not public (use a trusted setup) or if this is not possible you can go with trapdoor free RSA accumulators (basically by computing an RSA modulus in a way that the factorization is unknown to anybody).


Most efficient way to break md5? if you know the result of a hash, for this example the resulting hash is: ec664d1d65fd8a58c59b337b11c37a4d

And you also know the hash has been made like this:

const salt = "asdjbsdhal"
const password = unknown; // only thing we don't know
const hash = md5(salt + password);

So we know that md5(salt + password) == "ec664d1d65fd8a58c59b337b11c37a4d".

Is there a more efficient way to break this password than brute-force?
The brute-force I'm trying right now is this:

const md5 = require("md5");

const expectedHash = "ec664d1d65fd8a58c59b337b11c37a4d";
const salt = "asdjbsdhal";
let nonce = 0;
let result = "";

while (result != expectedHash) {
  nonce++;
  result = md5(salt + nonce);
}

console.log("Password: ", nonce);

Searching for the hash on Google sometimes instantly gives the plaintext. However, that only works for some common hash values.

Other than that, there is no more efficient way than brute force. Even so, you can optimize the brute force algorithm to make it faster. Hashcat can run the attack on GPU's, making it possible to perform many hash calculations in parallel.


Symmetric vs. Asymmetric cryptographic approaches to data security I know the basic differences between Symmetric vs. Asymmetric cryptography, but I'd love to know more details:

Exactly why is the asymmetric approach slower than the symmetric?
Why does it make use of longer keys?
Why does it require more processing power, etc, etc?
In what ways does it trump the symmetric approach?

Thanks, in anticipation, for your answers - I'm writing a BSC project on this issue.

The simple answer to "why are asymmetric algorithms more costly than symmetric algorithms" is because we have more requirements for asymmetric algorithms, and those additional requirements cost something to satisfy.

The requirement for (say) a symmetric encryption algorithm is "if you encrypt a message with the key, then someone without the key cannot infer anything about the message (apart from the length), but someone with the key can recover the exact message".

Now, asymmetric algorithms also meet this requirement. If we replace "key" with "the public and private keys", then we can encrypt messages (with the public key portion), and no one without the private key portion can deduce anything about the encrypted message.

On the other hand, we place additional requirements on asymmetric algorithms; someone with the public key still cannot decrypt messages, even though they can encrypt.  This implies that the public key and the private key must be related (because they are, in some sense, inverses of each other), but it can't be in an obvious way.

This means that the efficient constructions we use for symmetric algorithms (xor'ing in a keystream, Feistel networks, or SP-networks) just won't work, because those are easily invertable (given the key) by construction.  For symmetric operations, we can pick operations rather arbitrary, limited only by their efficiency, and how well they are disguised by a secret key.  Instead, we also need to limit ourselves to operations which have nonobvious relationships; these mathematical constructions (which is where we find this nonobviousness) are considerably less efficient.

As for when asymmetric operations "trump" asymmetric ones; the rule is simple: if you need the additional properties that asymmetric operations provide, they're better; if you don't, then they're not needed.


What is adaptive zero-knowledge? In this paper on pg. 1241 the authors discuss bullet point on Adaptive Zero-Knowledge :

I am new to Zero-Knowledge and I am having trouble understanding what they are saying.

I think they are saying the probability an adversary A in the real world wins and the probability an adversary in the ideal world wins are close (negligible). But I don't know what the difference is between S and S' or what $S^{crs}$ or $S^{proof}$ are.

Also, when they use notation like $A^{S'(crs,trap,.,.)}$ is really confusing - I have no idea what this means.

I'm not looking for a complete breakdown of what this means - but if someone could even summarize what the importance of adaptive zero-knowledge that would be great.

Ok, here we are speaking of non-interactive zero-knowledge proof systems for some language $L\in NP$. We there have a pair $\sf (P,V)$ of
probabilistic polynomial time algorithms (called the prover and the verifier) where both have input $x\in L$ and $\sf P$ additionally
holds a secret witness $w$ for membership of $x$ in $L$ and wants to convince a verifier $\sf V$ of this fact without revealing $w$.

One requires (a bit informal):

correctness: for $x\in L$ all proofs generated by $\sf P$ will always be accepted by $\sf V$
soundness: for $x\notin L$ proofs generated by by $\sf P$ will only be accepted with negligible probability by $\sf V$
zero-knowledge: for $x\in L$ the view of a verifier can be efficiently simulated without
the knowledge of $w$. Actually, the definitions you provide are in the common reference string (CRS) model, i.e., there is a $crs$ to which all entities
have access to. For zero-knowledge one requires that $(crs,x,\pi)$ with $\pi \leftarrow {\sf P}(crs,x,w) $ and $(crs,x,\pi)$ with $(crs,\pi) \leftarrow {\cal S}(x)$,
where $\cal S$ is the so called simulator, are computationally indistinguishable.

Now, adaptive zero-knowledge means, that soundness and zero-knowledge are with respect to adaptive adversaries. For soundness this
means that an adversary $\cal A$ is allowed to choose $x\notin L$ after seeing the $crs$. For zero-knowledge one requires from
the simulator $\cal S$, that $\cal S$ has to output $crs$ first and afterwards produce the simulated proof $\pi$. These two steps of the
simulator are denoted as ${\cal S}^{crs}$ and ${\cal S}^{proof}$ respectively. Note that these two definitons
are stronger definitions than in the static setting (described in the beginning).

Since the authors are talking about zero-knowledge proofs of knowledge for some $NP$ relation $\cal R$, they additionally require a property known as knowledge extraction.
Basically this means that the witness $w$ can be extracted from the proof transcript (this extractor is the algorithm $E$).

They also use a common reference string $crs$ with a trapdoor $trap$ which is required in order for ${\cal S}^{proof}$ to simulate a
proof without knowing the secret witness (you may look for instance at Groth-Sahai NIZK proof system for examples).

The notation ${\cal A}^{S'(crs,trap,\cdot,\cdot)}$ means that the adversary $\cal A$ has oracle access to the algorithm $S'$ where the inputs
 $crs$ and $trap$ are fixed and the latter two input arguments (indicated by $\cdot$) can be arbitrarily chosen by $\cal A$. Hope that helps a bit.


Default mode of operation in TLS cipher suites I've been trying to evaluate the security of a list of cipher suites and I've come across cipher suites, not explicitly featuring a mode of operation.

Form this list (openvpn --show-tls), one of such cipher suites would be:

DH-RSA-AES256-SHA256

As the cipher suites are provided by the underlying SSL library (OpenSSL 1.0.2g), I assume there must be a default mode, if not explicitly defined.

What mode would be used in this case?

If you look at the official list, you'll see that the official cipher suite name always has the mode explicitly stated; each AES-based transform is explicitly called out to be CBC, GCM or CCM.

Going through the OpenSSL source code, we find that the ciphersuite you cited has the value 0x00, 0x37, that is, TLS_DH_RSA_WITH_AES_256_CBC_SHA.  Hence, CBC is the mode being implicit.  I suspect this is implicit because OpenSSL predates TLS 1.2; in TLS 1.1 and prior, CBC was the only block cipher mode allowed (and hence there was no need to call it out); once the started supporting TLS 1.2, they didn't feel like they should go back and modify the name strings they used for existing ciphersuites.


Key Confirmation Attack [Key Distribution Center (KDC)] Okay this is how I understood it according to this:

Alice $A$ establishes a connection to $KDC$ and prepares for session key Exchange $k_{ses}$
$A$ encrypts the request with her key $k_A(A, B)$ meaning "need a session key to communicate with Bob $B$"
$KDC$ decrypts the message, genereates $k_A(k_{ses}, k_B(A, k_{ses}))$ and sends it to $A$
$A$ decrypts the messages and got now $k_{ses}$ the session key and the other part $k_B(A, k_{ses})$ she cannot decrypt (only $B$ kan due to $k_B$).
$A$ forwards the $k_B(A, k_{ses})$ message to $B$
$B$ decrypts $kB(A, k_{ses})$ and now knows he is talking to $A$ over the key $k_{ses}$

In my slides there is an attack described - the Key Confirmation Attack - which does look like this:

The thing here is now that I am not sure how this is supposed to work. This could only work if $RQST(ID_A, ID_B)$ (I'm sorry for the diverse notation) was not encrypted. This attack cannot work if the request was encrypted by Alice in the first place.

So, are there a few things mixed up or what am I missing?

Oscar cannot produce $k_A(A, O)$ – the requesting message to generate a session key for communication $A$ to $O$ – since he does not have the key of Alice.

$ID_a, ID_b, ID_o$ are public information

Oscar sends to $KDC$ a legitimate (encrypted) request to communicate with Alice: $RQST(ID_o,ID_a)$
Oscar gets $Y_o, Y_a$
Oscar sends $Y_a, Y_o$ back to Alice.

Alice cannot tell if she got $Y_b$ or $Y_o$, that's the problem. So, I would say the order of $ID_o$ and $ID_a$ are mixed up in the slide. It would be clearer if it was $RQST(ID_o, ID_a)$ instead of $RQST(ID_a, ID_o)$.


Factoring RSA-129 with a personal computer today I have read the history of the RSA-129 challenge, and now I would like to know if it would be possible to factor RSA-129 with a single "average" personal computer, today. Has someone tried to do this particular factoring?

From what I can gather it took about 2.5 months to factor a 512 bit RSA key on a personal computer from 2009 with a dual-core athlon64.

https://www.cemetech.net/projects/uti/viewtopic.php?t=8888

A typical desktop of today has about twice as many cores and twice the clockspeed. So that would cut it down to about two and a half weeks.

Furthermore modern processors have better IPC and your key is less than 512 bits.

So clearly doable but probablly not instant.


Could RDRAND (Intel) compromise entropy? I was recently discussing the issue of RDRAND in Intel chips and the whole issue about how NSA could potentially be influencing Intel to weaken or create backdoors in their design.

This petition was posted asking Linus Torvalds to ignore RDRAND and not include it as a source of entropy in /dev/random/. You can see Linus' response here.

My main question is, would using RDRAND as one source of entropy (amongst many others) potentially compromise the 'randomness' of /dev/random by adding some predictability? Or is he correct in saying that It really does not make any difference as long as its not the only thing entropy is generated from?

First of all, there is a difference between writing to /dev/random and/or /dev/urandom and increasing the entropy count maintained in the Kernel.

This is the reasony why, by default, /dev/random is world-writable - any input will only augment, but never replace the internal state of the RNG; if you write completely predictable data, you're doing no good, but no harm either.

If, on the other hand, you write to /dev/random using a special ioctl (and that does require superuser privileges), you can actually increase the entropy estimate.

If you are able to do that (and if you are, you could as easily replace /dev/random with /dev/notsorandom and be done with it), /dev/random degenerates to the behavior of /dev/urandom: Usually, reads from random are supposed to block until at least as many bits of entropy have been written to the internal pool than are requrested, while urandom returns as much "randomness" as requested.)

If you manage to write predictable bits to the pool, but tell the kernel to credit them as unpredictable data, the next reader(s) of /dev/random will receive random numbers that only deterministically depend on the current internal state of the entropy pools, and not on "truly random" events like disk seek times and keyboard inputs.

However, unless you are able to perform that attack from the very installation of the operating system, you don't actually know that internal state! Predicting it from /dev/random outputs is at least as hard as reversing SHA-1 (and that's perceived to be very difficult). This is also why it can be reasoned that, for the exception of directly after a fresh OS install, urandom can be considered to be "random enough" for all purposes, cryptographic or not.

Now let's have a look at the actual implementation of RdRand in drivers/char/random.c:

The only place the possibly malicious RdRand instruction is ever used is in the output functions of the random devices. It is XORed with the "actual" output of the "classical" Linux RNG right before that output is returned to the caller.

Since information theory tells us that when we XOR a chosen string with an unknown string, we can't predict anything about how the resulting string will look after the transformation, there is nothing to be gained from subverting the RdRand instruction, at least the way it is currently used in Linux.

Update:
Some suggest that a very clever CPU might interpret calls to RdRand as a trigger for a backdor that, for example, replaces the subsequent XOR with a MOV.

I'd say that's theoretically possible, but exponentially harder to implement than to just skew the output of RdRand directly, e.g. by returning the keystream of AES-CTR under a key known only to the adversary as "random numbers".

There would have to be checks for the specific code sequence used in the Kernel; if that ever changes (e.g. by surrounding the RdRand call with some dummy XOR operations), a microcode update to adapt the heuristic would have to be widely deployed or people would get suspicious very soon.

Treating the RdRand instruction (or an equivalent on a different architecture) as just another entropy input (without increasing the estimated entropy, to be safe), would probably make the RNG even harder to subvert.

Second update:
The issue has been discussed on the kernel mailing list twice: Once in 2011, started by a patch submitted by an Intel engineer and followed by a lot of discussion about security, and once again in 2012, which eventually lead to a patch implementing the current approach. Even the concerns about triggering a backdoor that changes the behavior of some instructions (e.g. XOR or MOV) has been mentioned. As far as the XOR construction is concerned: The Linux folks claim that the XOR approach is supposedly more secure than hashing the RdRand output into the entropy pool, though some of us here are not really persuaded about that.


How is the root certificate transmitted to pc? i understand that the purpose of root certificates and CA's is to ensure that the communication parties are who they say they are.

But how is the root certificate acquired? Is it not possible that during the acquisition someone is pretending to be the CA and i get a fake root certificate?

Thanks!

You are correct that getting the root certificate to the end user is a problem. There are two usual ways to solve this:

Out of Band: The root cert is carried by USB stick, or is placed on the system during install, or is pushed by an IT management tool, or by some other non-internet method.
Certificate Pinning: As an example, Firefox includes in its source code the root certs of all the publicly trusted SSL CAs. When you connect to an HTTPS site, Firefox checks that the root issuing cert matches one of the ~50 that are hard-coded into its source code. If Firefox wants to add / remove / modify one of the pinned root certs, it has to push a security patch to everyone. Since the binaries for Firefox are signed, it is difficult (though I'm sure not impossible) to plant a fake root cert in the list.


Should I use distinct MACs for each user, or should I use a *direction* flag when communicating? Alice and Bob want to communicate using a stream cipher. At the beggining, they create a session key $K_s$ and exchange it via some secure channel (using some asymmetric algorithm). After every message, they want to append a MAC value to verify their identity.

The question is this:

Should I have a direction flag $D_a$ and send

$$ C:=Enc(D_a, M) || MAC_{K_S}$$

or generate a new key $K_a$ for each participant (for a total of 3 keys in my example) and send

$$ C:=Enc(M) || MAC_{K_a}$$

The second scheme looks more solid to me, assuming static direction flags. Intuitively I believe the two schemes are equivalent if the flags change after each message. Is this correct?

Notes:

When I say they exchange a key what I mean is they agree on some seed and use it to generate a pseudo-random stream using a PRF. For a long enough seed (32 bytes) and periodic re-seedings, I do not see anything wrong with this but any comments would be appreciated.
The encryption method is $C_i:=S_i \oplus M_i$ for some stream $S$.
For two participants generating the same stream, one uses every odd $S_i$ and the other every even $S_i$.

Either method is fine.  They're both secure.  You can use whichever feels more convenient, given your application setting.

Better yet -- don't try to design this kind of thing yourself.  Instead, use an existing scheme for providing a secure channel abstraction (e.g., TLS).


Using the same symmetric key in both directions? A simple symmetric encryption scheme uses the same key, derived from a password, for both directions of the communication.  Is this bad practice, and if so what should be done about it?  Is it 'good enough' for many things?

It can be safe, but using the same key in both directions adds several things you need to be careful about:

One thing you need to make sure is not a problem is if an attacker takes a message from Alice to Bob, and sends it back to Alice as if it were from Bob.  Since Bob to Alice communications use the same key, Alice might decrypt the message, and act as if it came from Bob.  There are several possible defenses against this; the easiest (if you include a Message Authentication Code, which you really ought) is to include a direction flag within the authentication data; that way, a wrong way message would be rejected.
If you use a nonce-based encryption method (such as Counter Mode or GCM), you need to make sure that both sides don't use the same nonce.  This can be as easy as telling Alice to use even nonces, and Bob to use odd ones.  However, if you are going to use the same password (and hence the same keys) for multiple sessions, this would indicate that a nonce-based encryption method is probably the Wrong Answer; something like CBC mode + HMAC would make rather more sense.

However, even though it can be done safely, I would suggest you avoid the issue entirely.  Instead, when you send your password to the KDF, ask the KDF for twice the key length (say, 256 bits instead of 128), and use the first 128 bits for Alice to Bob messages, and the second half for Bob to Alice messages.


DCT Steganography - Where to embed the data Just a quick question about DCT Steganography. Do you embed the data before or after you send the 8*8 block through the quantization table?

The quantization table is part of the compression or decompression stage in JPEG, but for using steganography you should not compress/decompress the image, because these operations modify the DCT coefficients.

The usual process to hide a message in JPEG files is:

Read DCT coefficients from the JPEG file.
Modify the DCT coefficients to hide the message.
Write the DCT coefficients into the JPEG file.

So, the compression needs to be done before you hide the message. And if you decompress and compress the image again you could destroy the message.


Turing's (still?) classified inference engine algorithm? Does anyone know the algorithm used by Turing's Colossus inference engine, so highly classified that the Brits kept it secret for decades after WW II?

Indeed, it may still be classified.  Several years ago a colleague of mine, the late Robert Johnson, sent me an email response to my announcement about the Hutter Prize for Lossless Compression of Human Knowledge.  Bob was the guy who designed the Burroughs zero address architecture used for so many years in banking (and incidentally invented magnetic ink used on checks).  He certainly had a lot of background he didn't advertise, including classified work.

  Computerdom does not have a lot of art in inference engines (making
  predictions).  The most effective inference engine that I know of is
  the software done for Colossus, Turing's code breaking "computer" of
  WWII.  The Brits still treat that software as classified even though
  the hardware has been declassified for years.  So far as I know,
  nobody outside of  UK knows the details of that software.  My point
  here is that drawing understanding from natural languages is a
  relatively small art practiced mostly by cryptoanalysts.  And my
  further point is that the natural language of interest (be it English,
  Chinese, Mayan or ...) has a major influence on how one (person or
  program) goes about doing analyses and making inferences.   From a
  practical perspective, the Hutter challenge would be much more
  tractable for at least me if I could do it in Chinese.  My first PhD
  student was Jun Gu who is currently Chief Information Scientist for
  PRC.  His thesis was on efficient compression technologies.   If you
  wish, you can share these thoughts with whomever you please.

  Bob Johnson Prof. Emeritus Computer Science Univ. of Utah

This doesn't answer your question, but you may find clues in two wartime papers of Alan Turing which were formerly classified were declassified and published in the UK National Archives in 2015, and are now available on the arXiv:

  Alan M. Turing, ‘The Applications of Probability to Cryptography’, UK National Archives HW 25/37, 1942, arXiv:1505.04714.

  Alan M. Turing, ‘Paper on Statistics of Repetitions’, UK National Archives HW 25/38, 1942, arXiv:1505.04715.

It may be possible to reconstruct, from the principles enumerated therein, what algorithm Turing would have implemented in the Colossus to perform the feats it is known to have been able to perform.


Encryption Algorithms in Verilog code Can we implement Encryption Algorithms like RC4,AES and DES in Verilog? if no what are the limitations?

Verilog is Turing complete, so you can implement any algorithm in Verilog, if you really want to.


Will hashing over and over eventually give the same hash? There are many cases in maths where doing the same thing over and over again will bring you closer to a value. Derivation of polynomials is the striking example: no matter what you start with, you end up with 0. In a series expansion, the longer you continue the sequence the closer you get to the real value.

This concept applies in areas other than math (Wikipedia's everything-leads-to-philosophy phenomenon, for example). It's a little unrelated but it just proves the concept.

Hashing algorithms are just special math. Following logically, hash entropy supposedly decreases the more you hash a value. So is there a point at which any input value will give the same hash as any other?

(Let me just specify that we're not re-injecting any new data every time we hash, as if we're trying to increase the security of the hash by salting and re-hashing. It's strictly a matter of md5(md5(md5(... if that's the algorithm we're using.

I can see some problems with this already. Algorithms like md5 are designed to change their output radically when the input changes only by one bit of information. So even if a common hash for two values appears along the way, it itself will start changing. But then, does the fact that the output appears to be very different actually mean the possibilities are still many?

In general, collisions in a hash function are a bad thing: if you have different $M_1$ and $M_2$ for which $hash(M_1)=hash(M_2)$, the situation will require special handling.

In cryptography, hash functions can be seen as "summary" functions, that reduce a message of arbitrary length to messages of fixed length. Since the message space (all the possible messages) is usually way larger than the hash space (all the possible hashes), you are bound to have collisions.

There are several ways for an attacker to violate a hash function, but for this scenario, let us take a random value $H_1$ in the hash space. It could be a hashed password you retrieved from a server, for instance. What matters is that it is fixed.

In most cases, like the hashed password, the attacker does not need to know the original password. He only needs to know a random password $P$ such that $hash(P)=H_1$. That is definitely undesirable, and that is why cryptographic hashing functions are designed to be collision resistant. That means that, for an attacker with the most efficient polynomial algorithm to attack the hash function, it would take ages (a longer time than the time of existence of humanity) to find a collision.

All that said, what you want to find is some $M$ for which $H(H(H(...H(m)...)))$ some amount of times, gives again $H(M)$. That is mathematically possible (and certain to obtain), but your lineage will probably not live to see it.

As a final note: the password example is clearly flawed, since there are more specific attacks against it (like dictionary attacks and rainbow tables), but it is enough for the sake of your scenario.


What is the difference between cfb and cfb1 and cfb8 ? ( like openssl's aria-128-cfb & aria-128-cfb1 & aria-128-cfb8 ) What is the difference between cfb and cfb1 and cfb8 ? like openssl's aria-128-cfb and aria-128-cfb1  and aria-128-cfb8

edit: interestingly enough, there's also references to a cfb128 (example)

(title says it all but CSE won't let me post a question without a message body)

What is the difference between cfb and cfb1 and cfb8?

Well, first of all, we need examine what CFB is.  Here is what the encryption process is:

Take the previous $n$ bits of ciphertext (where $n$ is the block size of the cipher, for Aria, $n=128$
Send it through the block cipher in encryption mode
Extract $k$ bits of the result, exclusive-or that with the next $k$ bits of block text, and make that the next $k$ bits of ciphertext.

That's it.  Each iteration of the loop encrypts $k$ bits of plaintext, generating $k$ bits of ciphertext, and performs one block cipher operation.

And, to answer your question:

For cfb1, $k=1$
For cfb8, $k=8$
For cfb, $k=n$ (or 128 for Aria)

Of course, you might ask "why in the world would anyone use cfb1?  To encrypt 128 bits, it runs Aria 128 times, that's dreadfully inefficient"

The answer is "in case the ciphertext might be accidentally corrupted by bit insert or deletions".  The original idea was that CFB was targeted toward encrypting traffic going over serial interfaces, such as RS-232 or Bisync.  Now, RS-232 has the property that, due to line noise, an additional character might be received, or a transmitted character might be dropped (Bisync might have that same property with bits; I've never worked with Bisync, so I'm not certain).  Now, if we consider using CBC mode to encrypt the traffic, well, after such a character insert/delete error, the blocks used by the encryptor and decryptor will not match up, and so the decryptor will get gibberish (and it will continue to get gibberish long after the error).  In contrast, with CFB8, the next 16 characters will be decrypted incorrectly; then, as long as no further errors occurred, the decryption will proceed correctly.  CFB1 has the advantage that it can do with individual bits being inserted or deleted.

Of course, all that is historical.  Today, we generally are more sensitive to the issues that an adversary can cause by deliberately introducing error.  Because of that, we generally want to discard traffic which might be decrypted incorrectly, rather than passing it on (and so the error nonpropogation properties of CFB as not as attractive).


Deletion complexity in a RSA accumulator My question is about the existence of a dynamic RSA accumulator with deletion of an element in O(1) time.

Do you know some practical implementation?

Given the trapdoor, one would delete an element from RSA accumulator in constant time. In particular, produce an inverse to the element with extended Euclid algorithm and power-to accumulator to the inverse. The element in question would cancel-out from accumulator this way.


Advanced Electronic Signature: PKCS#7 to PFX Conversion I am a user requiring a legal signature to be installed on a SAP/R3 application.  For the past few years a service provider provided a X.509 advanced signature certificate that could be exported as a .pfx file and installed on SAP.
A new service provider supplied a dongle with PKCS#7 and a separate private key is required to create a .pfx file.  As far as I understand the private key is encrypted on the dongle.  They also informed me that they are not allowed to provide the private key.
Is there a way to create a .pfx file using this dongle?
If not, how do I correctly specify the requirement of a X.509 advanced signature that can be used to create the .pfx file?

A PFX file is better known as a PKCS#12, the "Personal Information Exchange Syntax".  It is used either as a trusted certificate store or as a key store. When it is used as a (private) key store it generally contains entries with a private key and the certificate chain associated with it (leaf certificate, CA certificates and root certificate usually).
If your key is in a hardware token then generally you cannot extract it. So your software needs to reference it some way or other. For this another standard from the PKCS range is commonly used, namely PKCS#11. PKCS#11 is also known as Cryptoki. Microsoft unfortunately has a bad track record when it comes to keeping to standards and uses a CSP (Cryptographic Service Provider). PKCS#11 libraries and CSP's are token specific and should be available from the vendor.
To use the device your software should support a PKCS#11 interface or it should use the Microsoft Cryptography API in a generic way (it is possible to use the "managed" classes, but then you'll be stuck with a software-only implementation). OpenSSL also has a PKCS#11 engine if that's your poison.

PKCS#7 is the "Cryptographic Message Syntax". It is used to sign / encrypt data. However, because it can also carry certificates it is sometimes used as a certificate store as well. It is not a key store, so the private key won't or shouldn't be in it.

X.509 is a standard of certificates and CRL's. It can specify a lot of things, but it cannot be used to specify where the private key is stored. As such the last part of the question is unclear and cannot be answered in my opinion.


Are really, really long passwords any more secure than short ones? Just for fun, I want to encrypt a message that will take about 10 or so years to decrypt. My idea is to encrypt a message with AES-512 with a password one million decimal digits long.

Knowing not much about cryptography, is this any more difficult to decrypt than a shorter password? (I'm trying to prevent brute-forcing, until computing power becomes so high that it is irrelevant).

There is no AES-512; AES takes keys of 128, 192 or 256 bits.

When encrypting with a password, there are two steps: first the password is converted into a key for the symmetric encryption, then the encryption is applied. Brute force can be applied either on the password (enumerating all possible passwords until a match is found) or on the key itself (enumerating all possible keys until a match is found).

A 128-bit key is large enough to defeat brute force for long period of times. You can use a larger key for display purposes (larger figures impress managers, and some people apparently believe that key length correlates with manhood -- in the same way as big cars).

The same applies to a password with 128 bits of entropy -- which is a way of saying that there are 2128 possible passwords, and you chose one at random among them. You can lower the entropy requirements on the password by using a slow hashing process; roughly speaking, if the function which converts the password into a key has the cost of 220 elementary encryption operations (that's about one million, and will be done in a fraction of a second with a basic PC) then you can be content with 108 bits of password entropy.

If your passwords are random sequences of alphanumeric characters (uppercase letters, lowercase letters, digits), then 19 characters are enough (because you use 62 distinct signs, and 6219 is greater than 2108). More characters are useless. Note that "random" is an important word: I am certainly not talking about choosing the password with your head ! Human brains are definitely bad at randomness. Use a coin, dice, or a computer with /dev/urandom.

All of the above is about making sure that the message will not be decrypted within the next 10 years. A much harder problem is to also ensure that the message will be more or less easily decrypted in year 2022, but not before. I suggest entrusting the key to a notary, with instructions to reveal it at a specific future date.


1 round Feistel with birthday attack This is a reprise of an earlier question of mine, and I'm sorry if it's repetitious; I'm going at it with a different strategy.

In an exercise I was given a 1-round Feistel network which uses $H(k \oplus x)$ as a round function. The key is 128 bits and the block length 256 bits, but we're asked to find the key in roughly $2^{64}$ work.

My intuition is the following. Since the hash takes inputs and outputs of size 128 bits, it seems likely that a collision resistant hash would be roughly 1-1, so we could expect that if we find $H(x) = H(x')$ then we would probably have $x = x'$. In roughly $2^{64}$ time, if I query the hash $2^{64}$ times on random inputs $x_i$ and query the round function $F(x) = H(k \oplus x)$ $2^{64}$ times on random inputs $y_i$, then I expect to have a collision in the hash owing to the "birthday attack" results, where $H(x_i) = F(y_j)$. But then by the earlier hash property, we expect $H(x_i) = H(k \oplus y_j)$ $ \implies x_i = k \oplus y_j$. This (probably) gives us the key, in $O(2^{64})$ time.

Am I correct? Is there a better analysis that makes more sense?

Assuming the Hash function is "good" (say it obeys the random oracle model, for concreteness) its restriction to 128 bit inputs should behave as like a random function.

This means that it will "miss" roughly a fraction $(1-e^{-1})$ of the $2^{128}$ binary strings in its range. Also, it will, with high probability have a point $y$ in its range (see, e.g., Mitzenmacher's Probability and Computing book), such that $$|H^{-1}(y)|\approx \frac{\log n}{\log\log n}:=M,$$
where $n=2^{128}.$

In fact, iterating this argument, since the remaining points in the range can be considered to come from a random function on $2^{n}-M$ points which would then have a point in its range with inverse image size $$\approx \frac{\log (n-M)}{\log\log (n-M)}$$ and so on.

This is probably not "almost one to one", but it looks like your attack may work with some fixed probability bounded away from zero, if you use multiple P/C pairs to deduce intersections of possible key sets corresponding to the clustered points in the range.


Noise of ciphertexts in LWE/RLWE based FHE Often times $[\langle \textbf{c}, \textbf{s} \rangle]_q$ is referred to as the noise associated to the ciphertext $\textbf{c}$, and that decryption is correct when the norm of the noise is $< q/2$. But shouldn't $\langle \textbf{c}, \textbf{s} \rangle$ be the noise instead of $[\langle \textbf{c}, \textbf{s} \rangle]_q$, since $[\langle \textbf{c}, \textbf{s} \rangle]_q$ means the reduction mod $q$ already happened and so the norm of $[\langle \textbf{c}, \textbf{s} \rangle]_q$ is always $< q/2$?

This is because of the decryption equation: If two ciphertexts differ ($\mathbb{Z}$-component-wise..., not homomorphically) in a multiple of $q$, they both decrypt to the same thing because of the modular reduction. Therefore, upon reception of a 'big' ciphertext, it makes sense to take modular reduction of this ciphertext and then look at its noise. Conversely, to cheat silly attackers one could add 'false noise' in this fashion (severely augmenting ciphertext size, however)


collision resistance with added permutation Suppose we have an $n$ bit ciphertext $c$ protected by a $k$ bit $MAC$, with $k < n$.
Generally, we expect collisions after $O(2^{k/2})$ ciphertext/MAC pairs are seen.
Consider the following modifcation:

Adversary chooses $m \in \{0, 1\}^n$ and
sends to oracle.
Oracle sends back $\sigma((c) || MAC(c))$, where $c=E(m)$ is a randomized encryption, and $\sigma$ is a permutation on $n+k$ bits. $\sigma$ remains unknown to the adversary.

Suppose $\sigma$ stays constant. It seems that we either attack the MAC/Encryption, or figure out the permutation. If the MAC and Encryption are perfect, then I don't see how we can find the MAC bits: any k element subset of the n+k bits will have the same birthday paradox probability of collisions. In fact, if we take $2^k + 1$ messages, the pigeonhole principle gives collisions to all subsets.
It seems our only help is if the MAC/Encryption has statistical biases that we can detect among the $O(2^{k/2})$ messages, but this seems that we must analyze all message k bit projections, which may be huge. Can we do better?
If we can't do better, what is the drawback of such a scheme? Is it impractical to have the hidden permutation be a shared secret? What about a set of such permutations?
Thanks

If the permutation is a shared secret, I don't see how that's different from normal HMAC; in the sense that you can't find a collision unless you know the key, the amount of permutations would be too many to calculate; but HMAC has those same cryptographic properties, even for a less-than-ideal hashing algorithm.
Update:
Here I explain the details of the number of possible permutations of the input bits (fun fact: this calculation actually comes into play when designing block ciphers). The issue is, while the number of ways you could permute the bits is extraordinarily high, the number of possible states will be upper-bounded at $2^n$ for $n$ bits. For an $m P n$ case (you select $n$ bits from set of bits $M$) you will be bounded by the number of possible $M$, as well as the possible $N$, making $2^n$ still your upper limit.
You cannot exceed the security provided by a normal $2^n$ bit hash, you can only match it with more permutation. Since any decent hashing algorithm already does this (and more), you end up with no change in your level of security. We're comparing internal states with input/output possibilities, and the input/output possibilities will always cap your security level. For this reason, I fail to see how it is different from a normal cryptographic hash.


Expanding truly random key into printable password for successive hashing The STUN network protocol defines its client authorization in the terms of message-integrity check employing the following scheme [RFC5389, section 10.2]:

$$
  \DeclareMathOperator{\HMAC}{HMAC}
  \DeclareMathOperator*{\SHA}{SHA1}
  \DeclareMathOperator{\MD}{MD5}
  \mathrm{MessageIntegrity} = \HMAC_{\SHA}(\MD(k), m),
$$
where the key $k$ is defined as the following string concatenation:
$$
  k = \mathrm{username} :\mathrm{realm}:\mathrm{password}
$$
In the above expression both username and realm may be treated as constant ASCII strings known to both the server and client (or any traffic eyedropper). The password, however, is a shared secret and never transmitted in plaintext.

I'm not particularly happy about this scheme, but it's that we have now. What I want is to generate a reliable enough password with as large entropy as possible.

Given that the password may contain only printable ASCII text, what password length would be enough to get a reasonable level of security if each password character is chosen at random?
Let's assume there are only $N$ bits of entropy available to generate the password, $N \approx 80...120$. Is it okay to seed these bits into a PRNG and generate a longer password? What would be the required password length in this case? Is it a good idea to generate a really long password in this case?

Q1.
 Each printable ASCII character gives you $\log_2 M$ bits of security where $M$ is the number of printable characters, assuming uniformity and independence between the characters [the second assumption does not hold in natural language].

For ASCII $M=106,$ which gives approximately $6.74$ bits/character, but this is likely to be a massive overestimate of security unless a good randomness source is used to
generate the passwords.

Q2. If you want to use limited entropy to generate astronger password you should consider generating a key using a KDF (Key Derivation Function). Have a look at this question and other linked questions from there. Some such schemes are used to derive different passwords/keys for different sites, where the sitename seems to correspond to the message in your case [i.e., it is variable].


Understanding a faulty Needam-Schroeder protocol Give this mutual-authentication protocol (along with the attack) in which Alice wants to communicate with Bob, I can't understand how the attack works.

A chooses $N$ (nonce) and sends to C (trusted server): $A, B, N$
C chooses $K$ and sends to A: $Kac(N, K, B, Kbc(K,A))$
Now Trudy acts in place of Alice
A decodes, checks $N$ and $B$, and sends to B: $Kbc(K,A)$
T (as A) replays to B: $Kbc(K',A)$, where $K'$ is an older session key
B decodes, chooses nonce $N'$ and sends to A: $K'(this is B, N')$
B sends to T (not to A): $K'$ (this is $B, N'$)
A sends to B, $K$ (this is $A, N'-1$)

If $Kbc$ is the shared secret key between Bob and the trusted server C, how is it possible for Trudy compute $Kbc(K',A)$? Trudy does not have $Kbc$…

The trick here is that Trudy does not need to know $K_{bc}$ (as you mentioned, it's not public).

However, what Trudy really needs to do is observe (by just monitoring the network) and store a previous "$K_{bc}(K,A)$" value that A has sent to B (publicly) beforehand (step 4).

So now in any future protocol sessions. Given that $K_{bc}$ is going to be the same, Trudy has the previous value it needs to preform the replay attack.


Is this constant-time comparison secure? I was thinking about constant-time comparison and how it differs from "==", when I thought of a simple way that's could be constant-time. Being a beginner in cryptography, I'd like to know if my method is secure. This method is probably insecure, but I'd like to know where it's weak. It's really simple.

Take the two strings to compare, convert them each to a list of numbers (0-255)
Set totalDifference = 0
Take the first number from the first list and subtract it from the first number in the second list. Take this difference and add it to totalDifference.
Do 4. for each character/number in both list.
If totalDifference is 0 after going through each number, then both strings are equal.

Example:
 [1,3,5,9,7,8]
-[1,3,5,5,7,8]
--------------
  0,0,0,4,0,0

0+0+0+4+0+0!=0, so strings not equal

Are there any problems with this constant-time comparison scheme?

Are there any problems with this constant-time comparison scheme?

One obvious issue is that it'll claim the strings "AB" and "BA" are the same; during the first character, it'll see 'A'-'B' = -1, for the second character, it'll see 'B'-'A' = 1; those two sum to 0.
On the other hand, that's actually fairly close to the standard way to do constant-time compare of equal strings, but instead of summing the differences, we bit-wise or them, as in:
total_difference = 0;
for (i=0; i<len_strings; i++) {
    int this_difference = a[i] - b[i];
    total_difference = total_difference | this_difference;
          /* | is the bit-wise or operator */
}
if (total_difference == 0) {
    /* The strings are the same */
}

The idea here is that the 'or' operation can set bits in total_difference, but never clear them.  Hence, the only way total_difference is 0 at the end is if in every iteration, this_difference was always 0, that that happens if each character of string a was the same as the character in string b.
Often, you'll see this_difference being computed by the bitwise-xor rather than subtraction; the algorithm works the same either way.


How can prime factor of $q-1$ divide prime $q$? In this paper - "A Subexponential Algorithm for the Discrete Logarithm Problem", author mentions (page 56),

For each $p_l^{e_l} | q$ proceed....

$p_l^{e_l}$  is one of the prime factors of $q-1$, and $q$ is a prime.
How can any number divide prime? Am I missing something here?
Edit1: $q$ is prime, so we can't get any non-trivial factor of $q$. Keeping this in mind, can anyone explain how to proceed with the steps mentioned in the paper. One thing to keep in mind is that $q$ has to be prime to be used in Diffie-Hellman system.

For arbitrary positive integer $n$ we have:

  $$\gcd(n,n+1)=1$$

So $q-1$ and $q$ haven't any nontrivial common factor.


secure login procedure I am considering two login procedures, both via HTTPS GET API:

procedure A:

Reuqest:

https://host/login?id={identity}&time={client_timestamp}&nonce={ramdon_string}&sign={signature}

Response:

{"stat": 0, "token": "token_string"}

Where:

id: identity of the request client, which is public (a hardware identity printed on label)
time: unix timestamp of the client, which must be in-sync with server clock (with allowed error about +/- 5 minutes). This is added to prevent replay attack.
sign: an hmac-sha256 of nonce+time+<shared-secret>.  nonce is saved at server-side for a period of time, within which re-use of same nonce is not allowed.

procedure B:

Request:

https://host/login?id={identity}

Response:

{"stat": 0, "token": "encrypted&base64 encoded token"}

In this scheme:

server will generate a token (if id is valid), encrypt <token><salt> with shared-secret using AES cipher.
server will lookup cache to prevent re-encrypt of same token. The cache will be valid for a period of time to save server CPU resource.
client will decrypt the token using shared-secret and use the first N byte as token (token length is pre-defined).

My question is, considering that the channel is HTTPS, encryption key is pre-shared, which procedure is considered more secure, and why?  Thanks.

They're equally safe. HTTPS is designed against most MITM-related attacks, including replay attacks, so the only thing you have to ensure is that your client has the pre-shared key.

For the first method, it is ensured by the HMAC hash. For the second one it is ensured because only the client can decrypt the token.

However, storing keys reversibly on a server is not recommended because your server might be hacked. This can be solved by storing the hash of your client key on your server with some secure password hashing algorithm(bcrypt, PBKDF2, etc).


libSTARK TinyRAM private inputs (Zero-knowledge proofs) I am looking into libSTARK and specifically TinyRAM and I cannot find out how to provide private inputs in a TinyRAM program. As private input I mean a variable that only the prover knows; i.e. the verifier has zero-knowledge of it.

In the DNA profile match (DPM) example that is described in "Scalable, transparent, and post-quantum secure computational
integrity", both the DNA fingerprint database and the suspect's fingerprint are supposed private. However, the DPM example is not implemented in TinyRAM and there is no TinyRAM example with private inputs. Also, by looking at the code, I could not find a command or a way to "hide" the value of a specific variable from the verifier.

I would like to thank Jonathan Bootle who helped me answer my question.

TinyRAM has two tapes, the primary and the auxiliary. The Primary Input Tape is used for public inputs while the Auxiliary Input Tape is used to provide private inputs.


S-box design criteria and random sboxes What are the disadvantages of using random s-boxes?
In AES, the s-boxes had to obey certain mathematical rules, which? And why?
What security does using hidden s-boxes (GOST) or generating them from the key (Khufu) add?, and how do these secret and generated s-boxes defend against differential and linear cryptanalysis or other unknown attacks?

What are the disadvantages of using random s-boxes?

This relates to the "why" behind some of the rules for s-boxes. AES, for example, requires an invertible s-box. A random s-box will not necessarily be invertible. In an s-box we also want non-linearity to thwart linear and differential cryptanalysis. This might not be the case with a random s-box.

  In AES, the s-boxes had to obey certain mathematical rules, which? And why?

According to "The Design of Rijndael" the design criteria was 1) non-linearity, specifically "the maximum input-output correlation amplitude must be as small as possible" and "the maximum difference propagation probability must be as small as possible". This is to prevent linear and differential cryptanalysis. And 2) algebraic complexity. This was to prevent algebraic attacks.

They achieve 1) by choosing an s-box that was studied in Differentially uniform mappings for cryptography. This particular s-box however is algebraically simple. Thus, the AES designers added an affine transformation which would be easy to describe yet algebraically complex.

One additional restriction they placed was that there were no fixed points and no opposite fixed points.

  What security does using hidden s-boxes (GOST) or generating them from the key (Khufu) add?, and how do these secret and generated s-boxes defend against differential and linear cryptanalysis or other unknown attacks?

Full disclosure, I'm not too familiar with these ciphers. From what I saw on wikipedia, the s-box in GOST can but doesn't have to be kept secret. The effect of this is an increase in the key size. Secret s-boxes would have to have properties similar to those of AES's s-box in order to thwart differential and linear cryptanalysis.

Generated s-boxes, I'm assuming must have some algorithm to setup an s-box using keying material that still meets the necessary properties. I'm guessing this is why Khufu has an expensive setup operation.


How does quantum encryption work? There has been a lot of buzz about quantum computing especially with D-Wave breaking the limits each month. I have basic knowledge about cryptography with an introductory course in quantum computing.

So, how does quantum encryption work? and how is it different in principle from the current practices adopted?

There are a few key distinctions to make
Quantum cryptanalysis
This is what you hear all the buzzing about. Specifically, there is something called Shor's algorithm, that when used to break modern crypto, can be devastating. If you've encrypted a zip file and told someone the key you're quite safe. But things like PGP and SSL, where you have to agree to a key online, are vulnerable; quantum algorithms have about an impact of O(n/2) on symmetric crypto decrease the effective key size by half for symmetric crypto. That means AES-256 will be as strong as a pre-quantum AES-128. RSA will be much worse off:

Shor’s Algorithm, which can only be executed on a quantum computer, can factor large numbers in $\log(n)^3$ time, which is drastically better than the best classical attack.  [Normally RSA2048] takes about $10^{41}$ units of time ...  Using Shor’s algorithm, the same problem only $10^3$

This is not something D-Wave can do yet. As far as we know.

Geordie (chief technology officer of D-Wave) on June 2, 2011, at 3:59 pm
said:
We do have a factoring algorithm that I’m going to do a series of blog posts on (the working title is “Better than Shor” :-) ).

-- https://dwave.wordpress.com/2011/05/11/learning-to-program-the-d-wave-one/
After that they never mentioned this again. Either he was wrong or
someone told him to shut up about it.

Quantum Key Distribution
This is what the other answer mentions, and this is something we can do today, and because of that, there's some hype about it. What it comes down to is that you have a guarantee that the code has not been intercepted in transit, because any observation would affect the quantum state. But it's really slow for now.
Post-quantum cryptography
These are simply crypto schemes designed to withstand algorithms like Shor's. An implementation is McElieces'; some fascinating work based on the hardness of breaking linear error-correcting codes. Other asymmetric implementations are based on lattices.


Minimizing size of signed message with discrete-log scheme How can we sign a small message with a discrete-log scheme so as to minimize the size of the whole signed message?

Detailed objectives, notation:

It is of paramount importance to minimize the total bit size $c$ of the cryptogram $C$ carrying the whole signed message $M$, e.g. because $C$ will be keyed-in (appropriately transformed to characters). $M$ is an arbitrary bitstring of $m$ bits, for some parameter $m$ with $32\le m\le256$.
We restrict to asymmetric signature algorithms loosely based on the discrete logarithm problem in some group (we note $q$ its order), e.g. because some directive only allows that or integer factorization which is inappropriate given 1; schemes using pairing-based cryptography are out. We have unrestricted choice of symmetric primitives likes hashes.
It must be arguable that a competent adversary using public knowledge and classical computers is unlikely to exhibit a forged signature (in a chosen-messages setup) with $2^w$ work for some parameter $w\approx80$, in a sense such that $w=67$ represents the work reported for the factorization of RSA-768:

  Our computation required more than 1020 operations. With the equivalent of almost 2000 years of computing on a single core 2.2GHz AMD Opteron, on the order of 267 instructions were carried out.

Each signature generation and verification must be feasible with $2^{32}$ work, but performance is otherwise non-critical, as well as key size (public and private).

Questions:

Are there better schemes than DSA and ECDSA variants with message recovery (see bibliography in this question), and which one(s) can we choose? What is the corresponding maximum capacity (that is, the largest $m$ such that we have full message recovery, and larger messages start to require increasing $c$)?
Are we better using group $\mathbb Z_p^*$ with $q$ a prime factor of $p-1$ as in plain DSA, or an Elliptic-Curve group, or..?
What parameters is it reasonable to use (for DSA variants: size of $p$ and $q$; for ECDSA variants: curve..), and what's the $c$ achieved?

Update: I now realize that the Schnorr signature scheme of 1989 yields $c=m+3w$-bit (for at most $2^{w/2}$ signatures). That's a candidate (related question).

Extras:

In (EC)DSA, we can trim a few bits from $C$ (reducing $c$ by $z_s+z_v$), by having the signer iterate signing until $z_s$ prescribed bits are (say) all set; and the verifier iterates verification with incremental values of $z_v$ other prescribed bits, until finding a signature that verifies. We can increase $z_s$ and $z_v$ within the limits set by requirement 4, with almost no reduction of security. Can we better leverage that leeway? E.g. by increasing $p$ in DSA, or somewhat using an entropy-stretching KDF (PBKDF2, Argon2..)? [for the DSA aspect of that, see this question]
Does things appreciably change, allowing lower $c$, if we relax security requirement 3 to distinguish between total breaks that allow the adversary to recover the private key or otherwise sign any $M$ at low cost, and those that would be unprofitable to an adversary if each forgery requires $2^{w'}$ work with $w'\approx w-16$?

This only answers part of the question, but here goes:

Classical Schnorr signatures start (in my notation, which I think will be helpful here) with a field $\mathbb F$, a linear map $f: \mathcal W \to \mathcal V$ over $\mathbb F$-vector spaces and a hash $H$ with codomain in $\mathbb F$. For simplicity let's take $\mathcal W = \mathbb F$. I'll use capital letters for elements of $\mathcal V$ and small ones for field elements. Intuitively, elements of $\mathcal V$ take more bits to represent than field elements.

The finite field implementation is to take primes $p, q = (p-1)/2$ and set $\mathbb F = \mathbb Z_q$,  $\mathcal V$ is an order-$q$ subgroup of $\mathbb Z_p$ generated by some $g$, vector addition is $v \oplus w := v \cdot w \pmod{p}$ and scalar multiplication (that makes the whole thing into a vector space) is $(x, V) \mapsto V^x \pmod{p}$. The linear function is $f(x) := g^x \pmod{p}$ for vanilla Schnorr.

For elliptic curve implementations (DSA, ECDSA, EdDSA) $\mathbb F$ is a finite field and $\mathcal V$ is a group defined over an appropriate elliptic curve, with point addition serving as vector addition and scalar multiplication of $x$ with $V$ is point-adding $V$ to itself $x$ times.

In both cases,

A keypair is a pair $(x, Y = f(x)) \in \mathbb F \times \mathcal V$.
To sign $M$ (which can be any bitstring), you pick a random $r \in \mathbb F$, set $A = f(r)$, $c = H(Y, A, M)$ and $s = r + cx$.
The "$4w$" version of the signature is $(A, s) \in \mathcal V \times \mathbb F$ whereas the "hash compressed" or "$3w$" version is $(c, s) \in \mathbb F \times \mathbb F$, since field elements are smaller than $\mathcal V$ elements.
The verification equations in both cases are $c = H(Y, A, M)$ and $f(s) = A + c \cdot Y$.

Which brings me to two recommendations.

In the hash-compressed version, the signature consists only of field elements, so it should not matter for signature size if you choose a finite-field or EC implementation: the size of keys (field elements) is the same for both at the same security level on keylength.com. What EC buys you is shorter $\mathcal V$ elements, which is irrelevant here. I'd personally go with Ed25519 just because I like it.
The probability of forging a proof is commonly given as $1/|\mathbb F|$ but really it's the inverse of the size of the codomain of the hash. While $s$ has to be a full field element, you can truncate the hash value $c$ to any smaller number $k$ of bits as long as you're happy with a lower soundness factor of $2^{-k}$.

EDIT: You can also do the $z_s + z_v$ bits thing here of course, but it seems like it doesn't buy you much. I thought for a bit how I'd prove the security of the version where the verifier iterates over $z_v$ "omitted" bits and the best I could come up with is a union bound, so by omitting $z_v$ bits you lose $z_v$ bits of security and force the verifier to do $2^{z_v}$ times the work, in exchange for transmitting $z_v$ fewer bits. Shortening the hash output by $z$ bits also loses you $z$ bits of security, but doesn't cause anyone more work.
(If you can prove that you can fix or omit some bits without losing that many bits of security, then of course this option becomes attractive again.)


Using Tweets as a Random seed I would like to start by saying I know nothing about Cryptography and was reading up on how to choose a random seed and this link is something that I found. What I basically understood that the seed has to be sufficiently random that guessing the seed would be hard.

So the question is would the hash of a Tweet, at any given time, be a good candidate for a random seed? This is mainly because the content of a Tweet can be practically anything as it's being generated by a huge percentage of the world population.

That said, I understand it is possible to game it by mass tweeting a specific string continuously from multiple accounts flooding the tweet stream with predictable seeds. So if this can be mitigated by blacklisting the bad usernames, is using tweets for seeds a viable option?

The other answers provide very good lists of reasons not to use Twitter as an entropy source.  What follows is the flip side of your question:-

Why would you want to?

Tweets are typically read on tablets, PCs and phones. All of those have access to hardware entropy sources that can produce oodles of truly random bits for seeding anything. The zeitgeist is that you aim for 128 or 256 bits of entropy and then seed a cryptographically secure pseudo random number generator. That will meet all of your common random number needs.

You have seeding sources such as:-

The RdRand instruction built into  most modern CPUs.
/dev/*random as part of the various favours of *nix.
Microsoft's Cryptography API.
The cameras built into phones and tablets.

There's not a lot of merit in pursuing Tweety entropy, other than for academic purposes.


What rule(s) for a good S-box is this one violating and how does it relate to non-linearity etc.? I generated this single-cycle substitution box and I want to post it as an example for understanding what a good S-box would be like. I get the feeling that this particular one is weak. Here it is (upper four bits of input are matched with the row and the lower four bits are match with the column:

AC 17 FB CB 60 93 35 50 F7 83 DF B3 8B 66 25 05
9B 16 0E 96 04 2A 95 62 FD 43 BE 37 4D 38 D9 07
E7 9C 80 3F D2 8E BA 1E 2F 36 F4 2E 2B AF A8 5A
9E 4C C0 19 82 3B 30 E9 4E DE 01 C8 15 8D 20 0B
39 CA E6 D0 F6 E3 57 D6 A3 1B 03 69 81 CE 22 AD
31 5E 57 34 70 A8 68 09 F2 B9 EA 6A 02 3E 21 78
C6 86 2C 85 6F D3 5C 2D 24 FF 92 D4 CF 18 4F B7
C5 12 FE 51 B1 B4 1C A1 97 40 C4 2F 47 F1 0A DA
F3 A2 8A 29 EE 10 32 F0 3D 48 D7 E8 6D A4 26 DC
B8 FC 91 DB A7 49 0C 5B 9F 13 F8 76 6C 11 73 58
B0 67 CD 88 44 27 75 D5 FA 8C 58 AE 14 7F 0F BB
B5 B6 46 E2 89 A6 63 08 E1 5F 1F 9D F9 98 64 79
4B 1A 42 AC D1 59 61 41 87 EB 77 A0 C2 DD CC 74
45 7D B2 8F C1 E5 99 C7 7E 3A 7B E4 F9 6E A5 7A
1D 53 56 ED 0D EC C9 71 C3 65 AB 06 EF 3C A7 5D
E0 7C 90 9A D8 06 23 A9 54 33 4A BF BD 72 84 6B

I'm noticing several things:

There are a few places where the upper four bits of the output match the upper four bits of the byte right above or below it in the table. There are also ones where it is the lower four bits that match.
There are a few places where the output's lower four bits match the lower four bits of the output to the left or right of it in the table. Same goes for the upper four bits.

I'm not well-versed in the art of S-box construction, but I'm getting the feeling that this one is a poor one.

What I'd like to know is: what rule for a good S-box is this one violating here and how it relates to non-linearity and all that?

Update #1

Richie Frame has pointed out that the S-box above is not bijective. Here is the correct one:

AC 17 FB CB 60 93 35 50 F7 83 DF B3 8B 66 25 05
9B 16 0E 96 04 2A 95 62 FD 43 BE 37 4D 38 D9 07
E7 9C 80 3F D2 8E BA 1E 2F 36 F4 2E 2B AF 55 5A
9E 4C C0 19 82 3B 30 E9 4E DE 01 C8 15 8D 20 0B
39 CA E6 D0 F6 E3 52 D6 A3 1B 03 69 81 CE 22 AD
31 5E 57 34 70 A8 68 09 F2 B9 EA 6A 02 3E 21 78
C6 86 2C 85 6F D3 5C 2D 24 FF 92 D4 CF 18 4F B7
C5 12 FE 51 B1 B4 1C A1 97 40 C4 28 47 F1 0A DA
F3 A2 8A 29 EE 10 32 F0 3D 48 D7 E8 6D A4 26 DC
B8 FC 91 DB A7 49 0C 5B 9F 13 F8 76 6C 11 73 AA
B0 67 CD 88 44 27 75 D5 FA 8C 58 AE 14 7F 0F BB
B5 B6 46 E2 89 A6 63 08 E1 5F 1F 9D F9 98 64 79
4B 1A 42 00 D1 59 61 41 87 EB 77 A0 C2 DD CC 74
45 7D B2 8F C1 E5 99 C7 7E 3A 7B E4 BC 6E A5 7A
1D 53 56 ED 0D EC C9 71 C3 65 AB F5 EF 3C 94 5D
E0 7C 90 9A D8 06 23 A9 54 33 4A BF BD 72 84 6B

It still has the same problems I noted before.

I have a software tool for analyzing basic differential and linear properties of s-boxes.
Submitting your s-box to my tool yields the following output:

The most probable differential characteristic(s):
1 -> 215 with probability 10/256 (xor -> xor) (weight 1 -> 6)
Linearity: 18.0 ((166, 166))

Differential probability
So we can see that the most likely difference is that a difference of 1 will output a difference of 215 with probability 10/256. The type of difference used was xor, it is possible to use other functions such as addition to attempt to find other differentials. A probability 10/256 differential is not horrible, but it could be better; For reference, the AES s-box has a max differential probability of 4/256.
Linearity
Linear cryptanalysis is analogous to differential cryptanalysis, but to many it may slightly more complex to reason about. The "linearity" value shows the distance to the nearest linear function. The more closely that the s-box approximates a linear function, the more easily it can be attacked. Again, the value for the s-box you presented is moderately good, but is again not as good as the AES s-box, which has a linearity value of 16.0.
Further Understanding
For a true understanding of the above, I recommend this resource for studying differential and linear cryptanalysis. It is a relatively gentle introduction compared to an actual paper on the subject. I developed my software for analyzing s-boxes while following these tutorials.


Cracking affine cipher with plaintext Alice and Bob decide to use the prime $p = 601$ for their affine cipher. The value of $p$ is public knowledge, and Eve intercepts the ciphertexts $c_1 = 324$ and $c_2 = 381$ and also manages to find out that the corresponding plaintexts are $m_1 = 387$ and $m_2 = 491$. Determine the private key and then use it to encrypt the message $m_3 = 173$.

Since the encryption and decryption functions are defined as $$e_k(m)=k_1\cdot m + k_2 (\mod p)$$ and $$d_k(c) = k_1'\cdot (c-k_2) (\mod p), \quad k_1' = \text{inverse of k1 modulo p)}$$
I began by setting up the system
$$387k_1 + k_2 (\mod 601) = 324$$
$$491k_1 + k_2(\mod 601) = 381$$

But I can't figure out how to solve for $(k_1, k_2)$

Remember when you solved systems of linear equations in school? This is essentially the same. You just swap out $K=\mathbb R$ for $K=\mathbb F_{601}$ which allows you to essentially do the same things as with $\mathbb R$, even if it is a little bit less inttuitive.

First too $\mathbb F_{601}$, as $p=601$ is prime, this is what is called a field. Essentially instead of doing normal addition, you do normal addition first and then reduce the result $\bmod p$ (ie take the remainder after integer division by $p$), same for subtraction and multiplication. Exponentiation works the same (as it is just repeated multiplication) and you can use the identity $1/a:=a^{p-2}\bmod p$. Now you can view your problem to solve the following equation over this field:

$$\begin{pmatrix}
m_1&1\\
m_2&1
\end{pmatrix}
\cdot
\begin{pmatrix}
k_1\\k_2
\end{pmatrix}
=
\begin{pmatrix}
c_1\\c_2
\end{pmatrix}$$

Obviously you will bring the matrix into triangle form (by subtracting the first line from the second) resulting in
$$\begin{pmatrix}
m_1&1\\
m_2-m_1&0
\end{pmatrix}
\cdot
\begin{pmatrix}
k_1\\k_2
\end{pmatrix}
=
\begin{pmatrix}
c_1\\c_2-c_1
\end{pmatrix}$$

Implying that $k_1=\frac{c_2-c_1}{m_2-m_1}$, which is indeed expected if we consider the cipher to be a linear function like those you learned in school. Now it immediately follows that $k_1\cdot m_1+k_2=c_1\iff k_2=c_1-k_1\cdot m_1$ and you have thus successfully recovered the full key $\begin{pmatrix}
k_1\\k_2
\end{pmatrix}$.

I'll leave it as an exercise to plug-in the numbers and recover the concrete values using a calculator or some online tool.


what kind of hash function can provide a short hash and be collision resistant? When you try to connect via SSH, you see a signature which is short but I heard it is even stronger than sha256. It is perhaps stronger because it uses more rounds. Is there a hash function or a method on current hash functions that use more rounds or something like that to somehow prevent collision attacks and provide a very strong hash that is not crackable, however with a hash value that is short enough to be easily read? I ask because a 32 or 64 character hash is too long and people don't like to read and compare something like that, for example when we put hash value of our software to download ...

if such a thing exists, please provide a javascript implimentation of it

Answer's plan:

re-stating the problem;
explaining its conventional solution, using a hash published in hexadecimal, usually of 32 to 64 characters;
explaining a better (perhaps novel) solution, combining two established cryptographic primitives (a hash and a function originally designed for Password Based Key Derivation), plus a slightly better formatting than hexadecimal, giving a 16-character cryptogram with security comparable to existing practice.

I take the question as: how short can a cryptogram be when used to verify integrity of some data, in the common situation where:

we trust the party that computes the cryptogram from the original data;
an adversary knows everything we or the trusted party knows;
we trust the channel by which we obtain the cryptogram;
an adversary is assumed to be able to alter the data in transit;
perhaps: we trust that the adversary could not inject anything in the original data in order to facilitate later alteration.

The traditional approach to that problem is to have the trusted party hash the data, and publish the hash in hexadecimal. For 128-bit security (that is, resisting an adversary able to perform about $2^{128}$ hash operations), if we do NOT assume 5, it is used a 256-bit (64 hex characters) collision-resistant and (second-)preimage-resistant hash.

One temptation is to just assume 5. Then, we no longer need a collision-resistant hash, and can use a 128-bit hash (or a 256-bit hash truncated to 128 bits). However, that would be unwise in some circumstances. For example, in the distribution of some software, the adversary could be introduced enough in the development team to plant an innocent-looking file, say aardvark.c. With a 128-bit Merkle–Damgård hash, and assuming the adversary knows every bit of data before aardvark.c in the archive of the distribution, she can craft that aardvark.c and a completely different version thereof such that substitution will leave the overall hash of the archive unchanged, with effort comparable to $2^{64}$ hashes; which is a lot of effort, but feasible. Notice that using a 256-bit hash truncated to 128 bits fools that aardvark attack, but not one where the adversary knows all the data except the final zymurgy.c that she injects. This is why standard (and good) security advice is to use a full 256-bit hash.

Can we have a shorter cryptogram without giving-up security? YES!!

I propose to:

hash the data using a traditional hash;
transform that hash into a shorter cryptogram using a random-like function that is purposely slow and costly to compute, similar in design to those used for the purpose of key stretching;
express that hash into a slightly more human-engineered form than hexadecimal.

We could use SHA-256 as the hash; Scrypt with the hash as the P/key/password input, a version identifier "1" as the S/salt input, a 10-byte output, other parameters (to be determined) so as to require 4 seconds of computation on a Raspberry Pi model A, but allow parallelization on a system with 16 cores and 16 times as much available memory; and format the 80-bit output as a 16-characters cryptogram using base-32 encoding with the 23456789ABCDEFGHJKLMNPQRSTUVWXYZ characters.

Assuming 5, an attack is expected to require computing power equivalent to $2^{81}$ seconds of the CPU time of our Raspberry Pi, which is perhaps $2^{100}$ hashes on that hardware (assuming 0.5 million hashes/second), and cost equivalent to $2^{116}$ hashes on dedicated hardware (assumed to beat the BCM2835 CPU of the Raspberry Pi by a factor of $2^{16}$ in price/performance ratio when hashing, thanks to massive parallelization and not having to pay the price of a fair fraction of 256 MB of RAM per instance). Thus we have arguably 101 and perhaps up to 117 bits of security for the size of 80, at the cost of 4 seconds of extra computation per use (or less on more capable hardware).

Without assuming 5, a practical attack is possible with in-advance knowledge of the original data (except for the malleable portion), and computing power equivalent to about $2^{43}$ seconds of the CPU time of our Raspberry Pi (which allows computing cryptograms for $2^{40}$ acceptable and $2^{40}$ rogue versions of the data, among which an exploitable collision has a fair probability); with the same hypothesis as above we have arguably 62 and perhaps up to 78 bits of security. Notice that in-advance knowledge of the original data is a very hard requirement for an adversary, and each unknown bit makes the attack twice as unlikely to succeed.

Addition: A quick search did not locate an earlier suggestion of using a deliberately slow transformation in order to shorten a hash while keeping a good fraction of its security. If I am in a position to name the technique, let that be a condensate, obtained by hash condensation.


Regarding application of ring signatures The wikipedia page of Ring Signature states:

Another application, also described in the original paper, is for
deniable signatures. Here the sender and the recipient of a message
form a group for the ring signature, then the signature is valid to
the recipient, but anyone else will be unsure whether the recipient or
the sender was the actual signer. Thus, such a signature is
convincing, but cannot be transferred beyond its intended recipient.

Can someone please explain the practical application of this concept? I can not make any sense of it? In what scenario it could be useful?

To understand the application, it is useful to contrast this with the use of regular signatures.
Imagine Alice sends a message $m$ to Bob together with a signature $\sigma$ of $m$ under her own public key $\mathsf{pk}_A$. A regular signature scheme now has two important properties:

It's publicly verifiable, i.e., anyone can verify that the $\sigma$ is a valid signature of $m$ under $\mathsf{pk}_A$.
It's unforgeable, i.e., only someone in possession of the corresponding signing key $\mathsf{sk}_A$ could have produced a valid $\sigma$.

The combination of the two, together with the assumption that Alice has a strong incentive to keep her signing key secret¹, leads to a property called non-repudiation. This means that the recipient can prove to a third party that the Alice really did send $m$ simply by producing $(m,\sigma)$.
Now, say $m$ is something legally or morally incriminating. Then, among other things, this opens Alice up to blackmail. Bob can threaten to release $(m,\sigma)$ which would prove to the public or some third party that Alice said $m$.
Alice understandably would like to prevent that. So this is where ring signatures come in. If we replace the signature scheme above with a ring signature scheme, then Alice would be sending $m$ together with a ring signature $\sigma$ of $m$ under the set² of her own public key and Bob's public key $\{\mathsf{pk}_A,\mathsf{pk}_B\}$.
A ring signature is still publicly verifiable, however the unforgeability now only guarantees that the signer must have known one of $\mathsf{pk}_A$ or $\mathsf{pk}_B$. This means that Bob can no longer prove to a third party that Alice sent $m$, since Bob himself could have simply computed $\sigma$ himself.
He can of course still try to blackmail Alice, but he can no longer rely on the security of the signature scheme to do so.

¹ This is where this argument could break down in practice.
² Sometimes also called ring, even though the name ring signature actually comes from the way the first such scheme computed it's signatures.


What are the security implications of knowing the private polynomial $\mathcal{F}$ First, affine transformations $S,T$ are defined by $S=A_1+v_s, T=A_2+v_t$. Let the private polynomial function $\mathcal{F}$ be known. The short description of the public key map is $P(X) = T \circ \mathcal{F} \circ S(X)$. Recall that common multivariate schemes are based on the security assumption of IP2, this is, the Isomorphism Of Polynomials with two secrets.

It results that only applying transformations $T$ and $S=I_n$ (the identity) makes the scheme vulnerable by linear algebra attacks. We can recover the transformation matrix $T$ since we already know that it transformed $\mathcal{F}$ to the public key matrix.

In addition, using $T=I_n$ and $S$ an arbitrary invertible affine function, the problem now is equivalent to IP1, which can be stated from the so called Polynomial Affine Equivalence problem (PAE) (see [1] section $2.3$ and $3$). Given $\mathcal{F}(x)$ and $\mathcal{F}(S(x))$ find $S$. Schemes based on IP1 can be vulnerable to attacks if not designed with care, see [2].

Then we are restricted to IP2 if we want to mantain security from this point. Recall that including abritrary invertible affine transformations $S,T$ would make the input-output of $\mathcal{F}$ unknown, even knowing $\mathcal{F}$. Then as $T$ transforms an unknown input, we learn nothing from here nor from the view of PAE or IP1, as we only know one set of quadratic equations $B$ but the set $A$ remains hidden by the transformation $T$.

In the previous description I tried to demonstrate that the knowledge of the private polynomial $\mathcal{F}$ has no effect when the scheme is based on the assumptions of IP2.

However, is there any complication if the private polynomial $\mathcal{F}$ is publicly known from other perspective?

My intiution says that recovering $T$ is fatal as $\mathcal{F}(X), \mathcal{F^{-1}}(X)$ are known the attacker obtains $F^{-1}(Y)=S(X)$. Then to solve IP1 he must establish an affine equivalence function $S$ between $\mathcal{F}(X)$ and $\mathcal{F}(S(X))$

If the attacker doesn't possess $\mathcal{F}$ knowing $T$ will yield $F \circ S(X)$ but yet he doesn't know $\mathcal{F}(X)$, thus IP1 cannot be followed from here.

Let's answer my question after revisiting the research. Start by quoting the following text from [2]. Note that I've changed the variables names to fit my description. Here $P(X) = T \circ F \circ S(X)$.

  An open question is to know whether or not these schemes remain secure
  if the set of polynomials $\mathcal{F}$ is public. In this situation,
  the security of these schemes relies not only on the difficulty of
  finding a common zero of a system of non linear equations but also on
  the difficulty of $\mathcal{IP}$ (Isomorphism of Polynomials) problem
  (when $\mathcal{F}$ and $\mathcal{P}$ are given, the problem is to recover the
  pairs $(A_1,v_s)$ and $(A_2,v_t)$).

In this post the private polynomial $\mathcal{F}$ is public, moreover described methods reduce IP2 to IP1 if $T$ is known, and IP1 is totally insecure [2]. In the other hand, if $S$ is known $T$ is recovered by basic linear algebra.

Then I conclude that a cryptosystem where $\mathcal{F}$ is known depends on the IP2 assumption (finding $(S,T))$ and the $\mathcal{MQ}$ problem implicitly. You can follow up from [2] section $6.2$

EDIT: Moreover, it results that IP1 is totally broken when the private polynomial is known. However if the polynomial $\mathcal{F}$ is unknown, having access to an oracle then querying for canonical vectors as a plaintext will reveal $S$ too. A secure cryptosystem based on MPKC must satisfy the IP2 assumption from design, between others.


Is there a cryptographic solution to provide a “proof of exclusion”? I would like a proof that accomplishes the following:

$N$ strings are part of a set $S$.  There is a do_proof function on set $S$ that produces a succinct witness statement $P$.

$$P = \text{do_proof}(S)$$

For some new string $X$ that is not part of set $S$, I have some proof

$$\text{prove_not_a_member}(X, P) = \text{True}$$

that proves that $X$ is not a member of $S$. Assume that $S$ is large and $P$ is constrained in size.

I was thinking about aggregate signatures but I'm not sure. Basically I am looking for a way to succinctly prove non-membership.  It does not have to be zero-knowledge.

Is there a cryptographic solution to provide a “proof of exclusion”?

As shown recently$^1$ in [BBF], this can be carried out using universal accumulators [BdM].
Their construction is in the discrete-log setting in groups of unknown order (e.g., RSA group or class groups) and the size of both proofs of membership and non-membership is independent of the size of the set committed to. The security proof is in the generic group model under an "adaptive root" assumption. The main components of their construction is a hash function $H$ that maps strings to primes and a proof of exponentiation [W]. A long overview can be found in this blog-post. A shorter overview is given below.
Overview of the construction. Let's fix a group $G$ of prime order $p$ with a generator $g$. Loosely speaking, the value of the accumulator for a set $S$ is
$$\pi:=g^{\Pi_{s\in S}H(s)}.$$
To prove membership of an element $s^*$ in $S$, the prover gives out the co-factor, i.e., the product of all elements in $S$ except $s^*$:
$$\pi^*:=g^{\Pi_{s\in S\setminus\{s^*\}}H(s)}.$$
Given $\pi$ and $\pi^*$, the verifier simply checks whether $\pi=(\pi^*)^{H(s)}$.
Proving non-membership of an element $s^*$ in $S$ is trickier and requires an application of Bézout's identity that is due to Shamir [S]. Since $H$ maps elements to primes, with high probability $h^*=H(s^*)$ and $h=\Pi_{s\in S}H(s)$ will be co-prime and therefore there exists two numbers $a,b\in\mathbb{N}$ such that $ah^*+bh=1$. The proof now is $\pi^*:=(g^a,b)$ and the verifier checks whether
$$(g^a)^{h^*}\cdot\pi^b=g.$$
$^1$ The ideas were probably known before, but I couldn't find an earlier reference.
[BBF]: Boneh, Bünz and Fisch, Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains, Crypto 19
[BdM]: Benaloh and de Mare, One-way Accumulators: A Decentralized Alternative to Digital  Signatures, Eurocrypt 93
[S]: Shamir, On the generation of cryptographically strong pseudorandom sequences., TOCS 83
[W]: Wesolowski, Efficient verifiable delay functions, Eurocrypt 19


Weaker alternative to Ed25519? For me, the main advantages of Ed25519 are that it avoids patents (by computing in one dimension) and that it is fast.

However, the 128bit security of Ed25519 is sometimes too strong to comply with export regulations.

So I wonder if there are any weaker curves of the same type (i.e. also patent-free and fast) that I can use instead? (or should I go deeper into ECC and try to determine myself the parameters of such a curve?)

You could try the 112-bit secp112r1 cited in [1].

Before you do this, the problem with that paper is they actually show how to break the discrete log problem on this curve! And this was back in 2012. So any export-strength implementation of ECC is definitely breakable by governments, research groups and sufficiently determined/resourceful commercial adversaries.

So you'd be selling crypto that, while safely exportable, is known to be breakable and you're competing against other crypto libraries that don't have this "feature". I'm skeptical whether this is a sensible idea.

EDIT: oops, I forgot to check the key point - that it's patent-free. But the problem remains that any 112-bit curve, patented or not, is small enough that one can feasibly if not easily take discrete logs.

EDIT2: on my machine, openssl ecparam -list_curves includes secp112r1 and according to [2] sun wrote the OpenSSL ECC package "precisely to avoid any patented method". To me it looks like you should be fine with that curve as long as you don't re-implement it using any of the patented implementation techniques. This is not legal advice of course.

[1] http://lacal.epfl.ch/files/content/sites/lacal/files/papers/noan112.pdf

[2] https://security.stackexchange.com/questions/3519/can-ecc-be-used-without-infringing-on-patents


What are requirements for this grille? I'm trying to program a Cardan grille, but I can't find requirements for grille. In my case, grille is square matrix A with $N$ x $N$ size, and elements are $0$ or $1$ (where $1$ means that it is hole).

I realized that if $N$ is odd, central element of matrix can not be $1$.

But what are the other requirements?

UPD 30.09.13

Wiki article in russian describes that, if matrix is square, it can be rotated four times around the center.

For example (If I understand correctly):
HELLO and matrix 3x3 with two holes

  1 0 0 | H 0 0 0 0 0 | 0 0 0 0 1 0 | 0 E 0

  0 0 1 | H 0 L 1 0 0 | L 0 0 0 0 0 | 0 E 0

  0 1 0 | H O L 0 0 0 | L 0 0 0 0 1 | 0 E 0

  0 0 0 0 0 1 1 0 0

In this expamle three rotations are enough.

As result we have matrix

  H O L L 0 0 0 E 0

And 0 will be replaced by the symbols A-Z.
It isn't Cardan grille? What it is name of these method?

If we have central element 1, that symbol well be replaced by other.

  1 0 0 | H 0 0  0 1 0 | 0 E 0  0 0 0 | 0 0 0

  0 0 1 | H 0 L  0 1 0 | 0 L 0  0 0 0 | 0 0 0

  ...

So, matrix has some requirements, which I'm trying to find.

I don't know where you get that the central element can not be $1$, because the Cardan grille does not have any special "requirements" as you're implying. In the original version, a piece of cardboard has several holes cut in it (= the grille) and when it is placed over an innocent looking message, the holes cover all but specific letters spelling out the secret message.

Simpler put: the holes you are cutting, identify the letters of the secret message. The other parts (which are covered) are the text to be ignored.

Let me give you a hint by providing you with a practical example…

The harmless looking, to-be-transmitted message could read:

ALL THOSE TEENIES ARE CRAZY KIDS!

and (taking your boolean $1$ and $0$ approach) the grille could look like this:

100010000010000000100010000010001

then the hidden message would be readable by applying the grille like this:

ALL THOSE TEENIES ARE CRAZY KIDS!
100010000010000000100010000010001
A...T.....T.......A...C.....K...!

ATTACK!

That's all that's to it. So, there are no other requirements but the obvious one: if someone puts the grille on your text, only the hidden message should be readable…

In other words (and to answer your question by the letter): the only requirement of the grille is to have "holes" where the hidden message's letters, numbers, and/or symbols are located, so that when the grille is applied to a harmless looking message (like a letter or book page), the hidden message is the only thing that remains visible because everything else is covered by the grille.

You might want to check Wikipedia's related article if you need another, more classical example.

EDIT

Looking at your edit, it becomes obvious that there's an additional step you're talking about... meaning we're indeed not talking about a pure "Cardan grille". A pure "Cardan grille" would not touch/change the text the grille is applied to. It's just a paper with holes showing you what letters of the plaintext are the secret message.

The rotating matrix your latest edit shows is something completely different. It could be called a grille cipher, but it's definitely not a Cardan grille… it could be a derived Fleissner grille (also known as "turning grille"), but I would need to be able to check the article you've been reading (see my link-request). It could well be that the article you've been reading talks about multiple grille cyphers; maybe even a combination of them. Until I've read that article , I can only guess… Fleissner grille.

If it's a Fleissner grille (or derivate), you might want to look at this related PDF which explains them (as well as attacks on it). Besides that, this website practically explains the Methods of Transposition as used in the Turning grille, including the center symbol thing you've noticed and are asking about.

You'll notice this image of a turning grille in action also has that 3x3 matrix in it's inner ring.

As for the 3x3 matrix itself, it's logical that if you rotate it around the middle, the symbol at the center will not move/change. Yet, I expect that what your edit shows is just part of multiple steps of remixing the 3x3 matrix. Otherwise, you're indeed correct - the non-changing center symbol would be one of the weakest parts of the matrix-mixing process.

As for the requirements of mixing, rotating and shifting a matrix… that is defined by the individual cipher implementation, not via generalized rules that apply to every cipher.


Use curve25519 for ElGamal crypto DJB described curve25519 in his paper which can be found here (PDF). It seems that the main purpose was for Diffie-Hellman key exchange. I think this means that Discrete Log is supposed to be hard on curve25519.

My questions is whether DDH (Decisional Diffie-Hellman) assumption is conjectured to hold on curve25519 too so that we can use it for building an ElGamal encryption scheme. Some quick investigation shows that DDH are assumed to be hard on elliptic curves with large embedding degree (Wikipedia – Decisional Diffie–Hellman assumption) and it seems that most elliptic curves have large embedding degree except those constructed for pairing based crypto.

So, I guess the answer should be “yes”. But still I would like to get some expert knowledge to confirm that one can securely build ElGamal encryption on this curve.

Curve25519 was supposed to be mainly used for Diffie-Hellman key-exchange and it provides ~128bit security and should fulfill all standard security assumptions on elliptic curves (and even some more).

Now to answer the question is: yes.
ElGamal can be used securely with Curve25519, as ElGamal is simply a Diffie-Hellman key-exchange ($\delta= m*g^{\alpha k}$) using some message-specific private key $k$ which is transmitted via $\gamma = g^k$.This means one either has to break the Diffie-Hellman problem (which is hard on Curve25519) or break the discrete-logarithm problem on Curve25519, which is equally hard (as it would enable you to break the Diffie-Hellman problem)

However I'd strongly recommend against using plain (or even padded) ElGamal in production use. If you intend to use elliptic curves for message encryption and signature I strongly recommend you to either use EdDSA or ECIES.


Security of RSA Keys in OpenSSL So when genrating a private key / or key pair in OpenSSL ther is the -nodes tag to deactivate the encryption of the private key . i looked it up and It means "no DES" . So no DES is used . Why is DES used for encrypting such secret information even tho it is not considered secure any more and OpenSSL is one of the most widely used tools for generating rsa keys

Mostly because when the command was created DES was the thing, and "no des" meant "don't encrypt".  Now the default is different:

$ openssl req -new -newkey rsa:1024 -keyout rsa.enc.p8 -out rsa.enc.p8.csr
Generating a 1024 bit RSA private key
...................................++++++
...........++++++
writing new private key to 'rsa.enc.p8'
Enter PEM pass phrase:
Verifying - Enter PEM pass phrase:
<snip />

$ openssl asn1parse -i -dump < rsa.enc.p8
    0:d=0  hl=4 l= 710 cons: SEQUENCE
    4:d=1  hl=2 l=  64 cons:  SEQUENCE
    6:d=2  hl=2 l=   9 prim:   OBJECT            :PBES2
   17:d=2  hl=2 l=  51 cons:   SEQUENCE
   19:d=3  hl=2 l=  27 cons:    SEQUENCE
   21:d=4  hl=2 l=   9 prim:     OBJECT            :PBKDF2
   32:d=4  hl=2 l=  14 cons:     SEQUENCE
   34:d=5  hl=2 l=   8 prim:      OCTET STRING
      0000 - e9 37 68 99 cb 9c 4f 10-                          .7h...O.
   44:d=5  hl=2 l=   2 prim:      INTEGER           :0800
   48:d=3  hl=2 l=  20 cons:    SEQUENCE
   50:d=4  hl=2 l=   8 prim:     OBJECT            :des-ede3-cbc
   60:d=4  hl=2 l=   8 prim:     OCTET STRING
      0000 - 16 ad ce 41 47 e8 ba 85-                          ...AG...
   70:d=1  hl=4 l= 640 prim:  OCTET STRING
<snip />

The algorithm that it actually used was des-ede3-cbc, aka 3DES-CBC.  While AES has almost entirely supplanted 3DES, 3DES isn't considered insecure.

NIST SP 800-57 Revision 4, Table 2, says that 3DES has 112 bits of security, putting it on par with RSA 2048.  Table 4 then says that 112 bits of security is good through 2030.


Proving a secret is known without revealing it Let's say Alice wants to prove to Bob that she knows a secret S that Bob is also supposed to know. Alice can't be sure Bob is really who he pretends to be, so she needs to make sure Bob can't deduce S from their interaction. Additionally, S could be weak (e.g. "abc123"), so she can't simply send a hash of S to Bob, or any f(S) really since that could be brute-forced.

What are your thoughts on this? Is this even possible?

What you want is the https://en.wikipedia.org/wiki/Socialist_millionaires
Problem.
This problem is orignally phrased as two people want to verify if they have the same amount of money without revealing anything more.
Alice has a value $A$ and Bob has value $B$ and they want to verify $A =? B$
without either side revealing anything more than the result of the check.
See the wiki page for algorithm description.