Re: Trusted timestamping
On 5 Oct 2009, at 16:04, Ian G wrote: My view is that there is no demand for this as a service. The apparent need for it is more a paper requirement that came out of PKI world's search for a perfect product than any business need. E.g., if you think you want it, you might be better rewarded by re- examining your assumptions as to why it is needed, than building it... http://www.itconsult.co.uk/stamper.htm Has been around since ~1995 and just works whenever I have used it, albeit some time ago. It publishes time stamp info on Usenet, comp.security.pgp.announce which shows the last activity was in 2002... http://groups.google.com/group/comp.security.pgp.announce/browse_thread/thread/d25667d87c1740f6# Which seems to support your viewpoint. f - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Re: Trusted timestamping
On Mon, Oct 5, 2009 at 8:42 AM, Alex Pankratov wrote: > Does anyone know what's the state of affairs in this area ? > > This is probably slightly off-topic, but I can't think of > a better place to ask about this sort of thing. > > I have spent a couple of days looking around the Internet, > and things appear to be .. erm .. hectic and disorganized. > > There is for example timestamp.verisign.com, but there is > no documentation or description of it whatsoever. Even the > website itself is broken. However it is used by Microsoft's > code signing tool that embeds Verisign's timestamp into > Authenticode signature of signed executable files. > > There is also a way to timestamp signed PDFs, but the there > appears to be nothing _trusted_ about available Trusted > Timestamping Authorities. Just a bunch of random companies > that call themselves that way and provide no indication why > they should actually be *trusted*. No audit practicies, not > even a simple description of their backend setup. The same > goes for the companies providing timestamping services for > arbitrary documents, either using online interfaces or a > downloadable software. > > There are also Digital Poststamps, which is a very strange > version of a timestamping service, because their providers > insist on NOT releasing the actual timestamp to the customer > and then charging for each timestamp verification request. > > I guess my main confusion at the moment is why large CAs of > Verisign's size not offering any standalone timestamping > services. > > Any thoughts or comments ? I have no useful comments other than to point you to a timestamping service you may or may not have seen (I didn't see you mention it: http://www.itconsult.co.uk/stamper/stampinf.htm), form what I've noticed (just in passing) this seems to be the most popular stamping service. > Thanks, > Alex -- noon silky http://www.mirios.com.au/ http://skillsforvilla.tumblr.com/ - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Re: Question about Shamir secret sharing scheme
On Sun, Oct 04, 2009 at 05:44:37PM -0600, Matt Ball wrote: > > The question that a colleague and I have is there any cryptographic > > purpose of computing the independent coefficients over the finite > > field, Zp ? > > Here is a concrete example of information leakage when not using Zp. > When using a finite subset of a totally ordered coefficient field (such as Q) whose "+" operator is order preserving (a < b => a + c < b + c for all c), we always see some outputs leaking more information than others. This covers any subsets of Z as Z is a subset of Q. A finite subset of such a field always has a minimal element. For example, if all the coefficients happen to be equal to the least possible coefficient, the person with share "1" easily concludes that he has the least possible sum, and recovers the secret coefficients. Using infinite subsets means unbounded storage requirements for the coefficients, and necessarily a non-uniform distribution of coefficients, with some polynomials more probable than others, so again data leakage. Leaking no information is only possible in a finite field, of which the Z_p are the "simplest", but (as pointed out upthread) Galois extensions of Z_2 are typically more convenient computationally. -- /"\ ASCII RIBBON NOTICE: If received in error, \ / CAMPAIGN Victor Duchovni please destroy and notify X AGAINST IT Security, sender. Sender does not waive / \ HTML MAILMorgan Stanley confidentiality or privilege, and use is prohibited. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Re: Trusted timestamping
Alex Pankratov wrote: Does anyone know what's the state of affairs in this area ? This is probably slightly off-topic, but I can't think of a better place to ask about this sort of thing. I have spent a couple of days looking around the Internet, and things appear to be .. erm .. hectic and disorganized. There is for example timestamp.verisign.com, but there is no documentation or description of it whatsoever. Even the website itself is broken. However it is used by Microsoft's code signing tool that embeds Verisign's timestamp into Authenticode signature of signed executable files. There is also a way to timestamp signed PDFs, but the there appears to be nothing _trusted_ about available Trusted Timestamping Authorities. Just a bunch of random companies that call themselves that way and provide no indication why they should actually be *trusted*. No audit practicies, not even a simple description of their backend setup. The same goes for the companies providing timestamping services for arbitrary documents, either using online interfaces or a downloadable software. There are also Digital Poststamps, which is a very strange version of a timestamping service, because their providers insist on NOT releasing the actual timestamp to the customer and then charging for each timestamp verification request. I guess my main confusion at the moment is why large CAs of Verisign's size not offering any standalone timestamping services. Any thoughts or comments ? I answer your question by two questions: Trusted timestamping service is like a specialized form of non-repudiation service. You may wonder if there is any fielded usage of genuine non-repudiation service, i.e. extending to an arbitration function that would support evidence management in some litigation forum. Fraud prevention in payment systems is not based on a genuine non-repudiation scheme. Are you aware of the current state of genuine non-repudiation service? Another approach to your question is that timestamping service has to be sold before being fielded and used. Who is(are) the real beneficiary(ies) in a trusted timestamping service, and how do you sell the service to them so that it makes economic sense? Regards, - Thierry Moreau - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Re: Question about Shamir secret sharing scheme
On Sat, 3 Oct 2009, Kevin W. Wall wrote: Hi list...I have a question about Shamir's secret sharing. According to the _Handbook of Applied Cryptography_ Shamir’s secret sharing (t,n) threshold scheme works as follows: SUMMARY: a trusted party distributes shares of a secret S to n users. RESULT: any group of t users which pool their shares can recover S. The trusted party T begins with a secret integer S ≥ 0 it wishes to distribute among n users. (a) T chooses a prime p > max(S, n), and defines a0 = S. (b) T selects t−1 random, independent coefficients defining the random polynomial over Zp. (c) T computes Si = f(i) mod p, 1 ≤ i ≤ n (or for any n distinct points i, 1 ≤ i ≤ p − 1), and securely transfers the share Si to user Pi , along with public index i. The secret S can then be computed by finding f(0) more or less by using Lagrangian interpolation on the t shares, the points (i, Si). The question that a colleague and I have is there any cryptographic purpose of computing the independent coefficients over the finite field, Zp ? Just to add two comments to what others have already said: - You can use any finite field. In particular, if your secret is a bit string of length k you can use the field GF(2^k) to get share size equal to secret size. (Whereas if you work mod p you lose a bit.) - As you describe the scheme above, note that you actually leak an upper-bound on the size of the secret (namely, it is at most p). The setup for Shamir secret sharing (and any other scheme, for that matter) assumes the range of the secret is public knowledge already.
RE: Trusted timestamping
> -Original Message- > On Sunday, October 04, 2009 5:42 PM > Alex Pankratov wrote: > > Does anyone know what's the state of affairs in this area ? I think there are two factors. 1) This is complex problem and 2) Where it might have really been required (i.e. the courts) it has not; the courts accept unsigned, text log files as reasonable evidence. >From a local (as in US) perspective I would look into some of the services provided by NIST (http://tf.nist.gov/service/its.htm). Even their "authenticated" offerings appear to be very limited, and use static, symmetric keys (which can only be obtained by snail-mail!) I've always liked the saying: "A man with two watches never knows what time it is." As long as there is more than one accepted internet time source and the courts accept uncertified timestamps in log files, I don't see any clear solution to (or reason to pursue) obtaining "signed time". -Piers -- Piers Bowness RSA - The Security Division of EMC - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Re: Trusted timestamping
On 04/10/2009 23:42, Alex Pankratov wrote: I guess my main confusion at the moment is why large CAs of Verisign's size not offering any standalone timestamping services. My view is that there is no demand for this as a service. The apparent need for it is more a paper requirement that came out of PKI world's search for a perfect product than any business need. E.g., if you think you want it, you might be better rewarded by re-examining your assumptions as to why it is needed, than building it... iang - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Re: Trusted timestamping
On Sun, 04 Oct 2009 23:42:22 +0200 Alex Pankratov wrote: >There is for example timestamp.verisign.com, but there is >no documentation or description of it whatsoever. >From European world plagued with qualified electronic signature disease - timestamp servers usually are compatible with RFC 3161 "Time-Stamp Protocol (TSP)" that works over HTTP, but since they don't want to provide free timestamping for anyone they're using various techniques to limit usage of this service. I've seen two techniques to do this. One was allowing only TSP request encapsulated in *signed* CMS (RFC 3369). So if you're signing a document using qualified signature AND timestamp you've got to enter PIN twice - one for document signature, one for TSP transport signature. The other server was not requiring signed CMS, but instead silently discarded signature requests from clients other that their own software. It had something to do with TSP options probably, but I didn't investigate any deeper. -- Pawe Krawczyk http://ipsec.pl - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
BusinessWeek article on IBM Research's Fully Homomorphic Encryption
Good read: http://www.businessweek.com/technology/content/sep2009/tc20090930_463595.htm For more info: http://www-03.ibm.com/press/us/en/pressrelease/27840.wss http://portal.acm.org/citation.cfm?id=1536414.1536440 This is just a proof of possibility, not (yet) feasibility. saqib http://enterprise20.squarespace.com - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Re: New Technology to Make Digital Data Disappear, on Purpose
a good article about the technology and its implications: http://www.physorg.com/news173556803.html [Moderator's note: old news (we already had announcements on Vanish here weeks ago), but in the last few days Ed Felten announced attacks on Vanish: http://www.freedom-to-tinker.com/blog/felten/breaking-vanish-story-security-research-action so I thought I'd let this through as a way of mentioning that... --Perry] saqib http://replaycall.com - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Trusted timestamping
Does anyone know what's the state of affairs in this area ? This is probably slightly off-topic, but I can't think of a better place to ask about this sort of thing. I have spent a couple of days looking around the Internet, and things appear to be .. erm .. hectic and disorganized. There is for example timestamp.verisign.com, but there is no documentation or description of it whatsoever. Even the website itself is broken. However it is used by Microsoft's code signing tool that embeds Verisign's timestamp into Authenticode signature of signed executable files. There is also a way to timestamp signed PDFs, but the there appears to be nothing _trusted_ about available Trusted Timestamping Authorities. Just a bunch of random companies that call themselves that way and provide no indication why they should actually be *trusted*. No audit practicies, not even a simple description of their backend setup. The same goes for the companies providing timestamping services for arbitrary documents, either using online interfaces or a downloadable software. There are also Digital Poststamps, which is a very strange version of a timestamping service, because their providers insist on NOT releasing the actual timestamp to the customer and then charging for each timestamp verification request. I guess my main confusion at the moment is why large CAs of Verisign's size not offering any standalone timestamping services. Any thoughts or comments ? Thanks, Alex - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Re: Question about Shamir secret sharing scheme
On Sat, Oct 3, 2009 at 12:42 AM, Kevin W. Wall wrote:
>
> The question that a colleague and I have is there any cryptographic
> purpose of computing the independent coefficients over the finite
> field, Zp ?
Here is a concrete example of information leakage when not using Zp.
Assume that the secret and each additional coefficient is a positive
integer less than 3 (intentionally picking a very small range to keep
the math simple). Assume there are two shares and that both shares
are needed to recover the secret. a0 = the secret and a1 is randomly
chosen in the same range.
q(x) = a0 + a1*x
We can make a table of all possible coefficients (a0, a1) and share
values (q(1), q(2)):
(a0, a1, q(1), q(2)) = {
(0, 0, 0, 0)
(0, 1, 1, 2)
(0, 2, 2, 4)
(1, 0, 1, 1)
(1, 1, 2, 3)
(1, 2, 3, 5)
(2, 0, 2, 2)
(2, 1, 3, 4)
(2, 2, 4, 6)
}
>From this table, it is possible to deduce a0 (the secret) knowing only
q(2), assuming that q(2) is not 4 or 2. Even then, you know that the
secret is not odd. Knowing only q(1) leaks a little less information,
but you can still fully determine the secret if q(1) = 0 or 4, and
partially determine the secret if q(1) is 1 or 3.
Intuitively, the information leakage occurs because the range of q(x)
is larger than the range of the secret a0.
Conversely, when using the set of integers mod 3, the table looks like this:
(a0, a1, q(1) mod 3, q(2) mod 3) = {
(0, 0, 0, 0)
(0, 1, 1, 2)
(0, 2, 2, 1)
(1, 0, 1, 1)
(1, 1, 2, 0)
(1, 2, 0, 2)
(2, 0, 2, 2)
(2, 1, 0, 1)
(2, 2, 1, 0)
}
It's easy to confirm by visual inspection that knowledge of q(1) or
q(2) alone does not reveal any information about the secret a0.
>
> The only reason that we can see to doing this is to
> keep the sizes of the shares Si bounded within some reasonable range
> and it seems as though one could just do something like allowing T
> choose random coefficients from a sufficient # of bytes and just
> do all the calculations without the 'mod p' stuff.
In any real implementation, you'd want to use a binary finite field,
such as GF(2^8) or GF(2^16). This is way faster than using a
non-binary finite field. The 'mod p' stuff would be optimized into a
series of fast table lookups.
For example, if you want to generate shares for a 512-bit ECC Key, you
would first divide it into 64 bytes (each of which fits inside
GF(2^8)), and then compute 64 independent shares. Each multiply would
be a couple table look-ups and your done.
Conversely, If you were using a non-binary finite field, your best bet
is probably using 2^521-1 (a.k.a., P-521 or the 13th Mersenne prime).
However, this is way slower than 64 GF(2^8) operations because the
time required to multiply two large integers grows with the square of
the size n. (Technically you can do it in n log n operations by using
Fourier Transforms, but this is only useful with really big integers
and you have to watch for rounding errors). The modulo computation
with P-521 would just be a couple BIGNUM subtractions.
Even worse, if you used the set of integers (Z), the evaluated points
on the polynomial would require about d*64 bytes of storage, where d
is the degree of your polynomial (i.e., the threshold number of shares
needed to recover the secret). The time required to do all these
multiples would roughly grow quadratically with the threshold (or
rather n log n because at this point, using Fourier transforms starts
to become appealing).
This is all moot, though, because using Z is not secure.
>
> We thought perhaps
> Shamir did the calculations of Zp because things like Java's BigInteger
> or BigDecimal weren't widely available when came up with this
> scheme back in 1979.
>
Even today, I don't see why anyone would use BigInteger or BigDecimal
for Shamir's Secret Sharing. As I mentioned above, the time required
for a BigInteger operation grows faster than linearly with the size of
the secret (either n log n or n^2), as opposed to linear growth with a
binary field.
You might argue that BigInteger and BigDecimal are 'easy to use', but
when considering the substantially slower execution time and the extra
burden of dealing with very large shares, it's really not a net
savings. Besides, there are many useful implementations of Shamir
Secret sharing that you could import into Java with much less work
required than reimplementing the algorithm from scratch.
Cheers,
-Matt
Matt Ball, Chair, IEEE P1619 Security in Storage Working Group
Staff Engineer, Sun Microsystems, Inc.
500 Eldorado Blvd, Bldg #5 BRM05-212, Broomfield, CO 80021
Work: 303-272-7580, Cell: 303-717-2717
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
