Pat CahalanMay 15, 2006 4:14 PM

Here's my question about PKI-based notary systems.

Someone dark and sinister gets their hands on the key. All signed documents using the key could now be suspect, as they could be replaced with forgeries. So you have to revoke the key.

What do you do for those thousands of documents that are signed? Do those people get them re-signed for free? Do you charge them? What's the legal standing of a document with a revoked signature?

David DonahueMay 15, 2006 4:25 PM

Pat, I would imagine that the system simply does not cover this condition.

The existing notary system does not and it's not considered a failure that someone could steal / forge a notary stamp.

In the case of a claim involving a stolen or forged signature by a digital notary, the records of that notary could be subpoenaed to validate that he really signed it, just the way it is done with a claim of a forged paper and stamp notary signature.

If the exploit of stolen digital notary secret key becomes commonplace or a major problem then the system could be changed but until then "good enough" is probably fine.

Besides I would hope that digital notary secret keys are protected by tokens and long pass-phrases or biometrics on secure PCs, making an expert attack more likely to be needed than a large scale virus/spy-ware attack.

TobiasMay 15, 2006 4:53 PM

Pat, I agree with David, that it it just not covered. As the eWeek article and the linked application PDF says, the notary must *download* (maybe they are created on-the-fly in the browser, but they are still "just" files) the key which is valid for one year.

Personally, I would enclose such a critical private key in a temper-proof device (like a crypto smartcard, where - once uploaded - it is impossible to extract the private key), but I'm doubtful if that case is even considered in the programs that are used for that purpose. With this you could even think of a scheme were the smart card would generate signatures with an increasing counter, so you could revoke all documents where the counter is higher then a specific number.

Saqib AliMay 15, 2006 5:39 PM

Why not wrap the secret with the Storage Root Key and store it on a TPM, with bio-metric authentication. This should address any secret key theft issues....No???

Pat CahalanMay 15, 2006 7:02 PM

@ Tobias, David

That was sort of my point :)

If you're going to get rid of paper and move to electronic signing, you're enabling a whole class of previously "don't scale well" problems to suddenly come crawing like mad out of the woodwork. Now notary fraud graduates from a relatively minor problem to an event that can cause a major headache to correct.

I've seen lots of digital signing programs, all of which center around the idea that getting rid of paper is a big efficiency. Very few of them consider the drawbacks...

RogerMay 15, 2006 8:13 PM


Actually this has been studied extensively in cryptographic theory, and there is at least one known solution. The Bellcore researchers who developed it have been offering it as a commercial service since before the 'net went point-and-click.

I don't recall the exact protocol but it involves chains of hashes of timestamped signatures. It renders it impossible to insert or delete any signature into the sequence after they are made, and possible to efficiently verify that any signature is not only a valid signature but also that its timestamp falls in the correct position in the sequence. The overall effect is that even if an adversary steals the notary's private key, all he has to do is revoke it and issue an new one; all existing signatures remain sound as it is not possible to forge an old signature.

Mike O'DellMay 15, 2006 9:47 PM

the answer to the temporal zipper is "Digital Timestamping" - developed originally at Bellcore and commercialized by Surety. if a signing key is revoked at some point in the future, the veracity established *at a specific point in time* can tell you that the document was signed before the revocation and how long before. the great thing about Digital Timestamping is that it was designed assuming that the operators of the infrastructure were corrupt and the veracity of a timestamp can be established indepenently by any third party from publicly-available information.

Davi OttenheimerMay 15, 2006 10:53 PM

If the operators of the infrastructure are corrupt, then how do you establish a reasonable point of revocation? I imagine a case where the breach is discovered after a long period of mixed good and bad signatures have been issued might have a hard time establishing when the bad stuff started, perhaps making the timestamp useless. Another control method, or at least principle, seems to be missing.

Filias CupioMay 15, 2006 11:55 PM

Here's a few attacks and countermeasures I've thought of:
* Cracker owns notary's computer, copies private key, signs stuff on their own computer
-> Harden notary's computer
-> Don't ever connect notary's computer to network
-> Use a physical encryption device
* Cracker owns notary's computer with physical encryption device. Remotely transmits documents to the computer and gets them signed
-> Physical device needs extra step (e.g. push a button) for every file signed.
-> A hash of each signed document recorded by non-computerized means (e.g. a written log.) The log is checked if a dispute arises.
* Physical key is stolen
-> Use of a hash log (as above) means this is insufficient by itself
-> Biometric or pass-phrase activation of key
-> Secure time-stamping included as part of the signing protocol (This is desirable for other reasons also.)
* One of the parties to a contract provides a corrupted copy for signing (e.g. the difference between "not" and "now" could dramatically change a contract, but be hard to spot.)
-> Notary receives the file separately from all parties, and only signs if all copies are the same.
-> Notary provides a copy of the signed file to all parties, who at least now have the opportunity to find the corruption sooner rather than later.
* A file presented for signing is a trojan, exploiting a buffer overflow (or something) to own the notary's computer
-> Notary never opens files which are being signed
-> Notary's computer has no writable file system. (Ideally implemented at hardware rather than OS level.)
* Impersonation
-> Existing paper notarization protocols operate here. (Possibly inadequately, but we're no worse off than we were before.)

Imagine the following box: small, simple, cheap computer, securely tamper-evidently sealed with crypto hardware, video output, keyboard, mouse, OS and applications on non-writable medium (at least without opening the box, which would be evident), fingerprint scanner to recognize notary's thumb print (required once per file), USB port and optical drive for reading/writing signed documents.

For efficiency, the box can share keyboard, mouse and screen with a computer - switchable for which box currently has them.

More realistically, a crypto-device with fingerprint scanner attaches by USB to an existing computer. Not quite as good, but cheaper.

EuripidesMay 16, 2006 1:02 AM

In Austria all notarys sign the documents digitally with a key stored on a chipcard. The documents are also stored in a common electronic archive. When the federal administration needs access to certain documents, they get them directly from this archive.

I'm sure, an attacker could somehow tamper with this system, but it's much harder than forging a stamp. It works since 2000, an I never heard about any major problems.

TimMay 16, 2006 1:58 AM

Wow, we in Switzerland have not even established the digital signature in a practicle way and you guys already have digital notarization!

Sure revocation is a problem. But a public digital notary with state acredition would have to undergoe even more special training and official scrutiny than their paper counterparts. I presume the privatre keys would be changed regularly and the old ones thrown away. In addition stringent audit trails of all activity would have to be kept.

Paper systems can be compromized if extensive procedures and checks are not
implemented. And remember, compromised paper notarizations cannot be revoked easily. Digitial ones can.

DigSigMay 16, 2006 9:19 AM

I agree with Filias. Having many years experience working with PKI and digital signatures, there are many vulnerabilities present when creating digital signatures in a general PC environment, the least of which is the security of the private key. The only way to ensure digital signatures have any value is to use a trusted, sealed, and verifiable computing device to create the digital signature.

There were not a lot of details on how the digital signature will be created, other than perhaps Adobe Acrobat might be used given the presence of the Adobe fellow.

When creating a digital signature, perhaps more important than access to the private key is knowing what data is actually included in the encrypted message digest (aka the digital signature) and what is actually displayed to the user as part of the application presentation and the operating system GUI.

For example, in many applications, when creating a digital signature, all the bits in the document are typically not included in the digital signature. It has been a version or so since I looked at Acrobat, but as I recall, the digital signature process only includes specific internal data objects when creating the message digest.

Also, the presentation of the document to be signed and the representation of the digital signature is also a tricky problem to solve, especially for applications that try to maintain multiple signatures on the same document or digital signatures on multiple versions in the same document.

For example, with paper documents, one typically can see the entire document being signed and for legal documents, each visible page is signed (or initialled). For electronic documents, depending on the computer display, the signer may not see the entire page they are signing, nor do they sign or initial each page, so one could argue about how they can know that what they are actually signing is what they saw on the display? They have to trust the computer and the application to "do the right thing" (assuming the computer or the signing application has not been compromised).

It will be interesting to see what happens when the first legal cases involving these digitally signed documents come up in court.

Pat CahalanMay 16, 2006 10:59 AM

@ Roger

> I don't recall the exact protocol but it involves chains of hashes of
> timestamped signatures.

Oh, I'm sure you can establish procedures that can minimize or eliminate the revocation problem. I could think of a few workarounds myself, all of which require some sort of authoritative something additional to the protocol (which doesn't really eliminate the problem, just reduce it).

However, I would wager a non-insubstantial sum that the first N iterations of digital notary would not include such procedures.

Remember, the motivations behind digital signatures/notaries are: make it fast, make it cheap, make it accessible. As an afterthought, make it secure.

Filias has a couple of good ideas, all of which would drastically increase cost vs. "run this software on the notary's computer and have him/her use a USB key to store his/her signature" or some other quarter-assed implementation.

KevinMay 16, 2006 12:37 PM

Good points DigSig. It almost seems the state should establish a non-proprietary open format for documents. It would seem to be all too easy to write a Word document that appears differently on different desktops, which could be put to a wide variety of nefarious uses. If the state limitted its eNotarizing to simple mark-up text documents and/or non-proprietary image formats, this type of problem could be avoided.

AlaricMay 16, 2006 12:54 PM

It seems to me a good deal of these issues were addressed in the digital signing for installs.

For example, requiring an extra step for signing, you must enter the password for the private key. However, this is better done with a smartcard, and the smartcard further hardens the private keys security, allowing it only to be in 1 place at a time and much more.

Revoked and expired keys are handled by checking the signatures timestamp, to see if the key was valid at the time of signing.

External signatures, like PGP, solves all the issues of proprietary formats for digital signatures.

But my thought is, how much use is a digital notarization when you can get a class 3 or 4 certificate?

Eric NormanMay 16, 2006 3:11 PM

What's with all this crypto-weenie stuff?

David Donahue mentioned the best approach way up there. Just consult the records!

It's a business process thing, not a crypto thing.

There are way too many people that think "Applied Cryptography" contains the magic answer to everything. Sorry, Bruce; I still treasure my copy, though.

Pat CahalanMay 16, 2006 3:22 PM

> It's a business process thing, not a crypto thing.

I quote myself: "Remember, the motivations behind digital signatures/notaries are: make it fast, make it cheap, make it accessible. As an afterthought, make it secure."

Taking a business process thing and trying to turn it into a crypto-enabled business process thing means thinking about the technology ahead of time, or packing bandanges and crutches for when you shoot yourself in the foot.

ThomasMay 16, 2006 7:33 PM

"""There are way too many people that think "Applied Cryptography" contains the magic answer to everything."""

They probably haven't read the part about how cryptography is increadibly difficult and frustrating to get right, but it's still the "easy" part.

RogerMay 16, 2006 9:20 PM

@Pat Cahalan:

First I should point out that digital notaries have a significant difference to traditional notaries: they *only* securely time stamp documents. Actual notaries public have a variety of other legal duties, most of which are practically impossible with the current internet (e.g. lack of reliable personal authentication framework). For example, notaries may be required to notarise a statutory declaration. A digital notary can prove that the declaration was made at a certain time and not subsequently altered, but affirming the identity of the person making the declaration is "an exercise left to the reader".

> all of which require some sort of authoritative something additional to the protocol (which doesn't really eliminate the problem, just reduce it).

I'm not sure what you mean by "authoritative" in this sense, but what the protocol actually involves is periodically publishing a short list of hashes. The only assumptions required to in fact provably eliminate the problem are that a massively diversified database is hard to completely redact (a property sometimes described as "information wants to be free"), and that the opponent cannot calculate preimages of your hash.

The state of the art in preimage calculation is that we still can't even do MD4, and even the Church of Scientology's army of lawyers hasn't managed to redact usenet.

> However, I would wager a non-insubstantial sum that the first N iterations of digital notary would not include such procedures.

Unless N = 0, you'd lose your substantial sum, as the *first* such commercial system of which I am aware already included it, more than a decade ago. (Of course that doesn't necessarily mean that later ones do, and I have no idea if the new system in Pennsylvania does.)

> Remember, the motivations behind digital signatures/notaries are: make it fast, make it cheap, make it accessible. As an afterthought, make it secure.

It is often prudent to be somewhat cynical, but in this case I believe you have overdone it. Looking at a digital notary's requirements from a business perspective, we see that speed and cheapness are not particularly significant (it is already orders of magnitude faster and cheaper than the alternative); whereas security is absolutely critical because as a notary, trustworthiness IS your product.

And yes, it also needs to be at least sufficiently accessible for lawyers and business people to operate the verification process. However there is no particular reason for this to impact security.

@Eric Norman:
> What's with all this crypto-weenie stuff?

It's true that many people get overawed with cryptography and think of it as a panacea, which it certainly is not. However for this particular problem there is a very good reason why cryptography is not only an answer, but the best answer. The reason is that we are talking about purely digital documents, which may not necessarily (and usually do not) have any paper based representation. Cryptographic techniques are the *only* known method for reliably making a purely digital document unalterable.

Additionally they can be made far more resistant to forgery than any paper-based system of remotely comparable cost. In fact, nowdays some of the best ways to make a paper document forgery resistant also involve cryptography.

> David Donahue mentioned the best approach way up there. Just consult the records!

That's effectively what the hash chaining system *does* do. Except that it does it every time a document is verified instead of only when there is a dispute, the "records" are themselves unforgeably notarised, and it is all designed to do this as efficiently as possible with the minimum communication overhead.

> It's a business process thing, not a crypto thing.

No, it's a business crypto process thing. Much of modern crypto is concerned with analysing the security of protocols, that is, algorithms involving more than one entity. Stuff like, for example, business processes.

For example we could do the same process without hash chains but it is not difficult to show that that makes it less secure in several ways (and would also massively increase network and storage overhead).

VanceMay 16, 2006 11:00 PM

"While alteration of paper documents is always detectable, tampering with digital documents is remarkably easy, inexpensive and undetectable without some means of freezing the original document or rendering it tamper-evident," said [National Notary Association President Milt] Valera, emphasizing that the ENS Program provides that solution.

I'm not sure I buy his first premise.

DigSigMay 17, 2006 12:34 AM

"If the state limitted its eNotarizing to simple mark-up text documents..."

Actually, mark-up document formats make matters worse. The problem is that document formats like XML or HTML rely on the application to determine how to render and present the document to the user.

For example, with HTML, increasing the width of the browser window can cause the text to wrap in different places. So, even with a perfectly valid digital signature, you can end up with the problem that the document can look completely different to the person verifying the digital signature if using a computer and application (i.e. browser) different from that which was used to sign the document.

This is the problem when the document rendering and presentation is too separated from the data that is actually digital signed. Ideally, the digital signature will be created on the *presentation* form of the document. This is where Adobe Acrobat actually helps, however, since there are no open standards for creating Adobe Acrobat digital signatures, one has to trust that Adobe is "doing the right thing" when it comes to creating and verifying digital signatures.

What is really needed is a trusted, sealed, and verifiable device, perhaps something like a stripped down UMPC with a bare-bones OS, whose sole function is to render and present, digitally sign, and verify documents. This device would have a single standardized GUI application for presenting documents, digitally signing them, and verifying them. The application "sealed" into this device can certainly be standardized as well as the document formats used. There could be readers available on general PCs for the document format, however, the documents digital signature could only be created and verified on this dedicated device.

ThomasMay 17, 2006 1:00 AM


"""External signatures, like PGP, solves all the issues of proprietary formats for digital signatures."""

No they don't.

If the digitally signed document is in a secret proprietary format, it may be unchanged but may still contain some macro like
if (date > 2010) search-and-replace "$5000" with "$50,000"

Even easier.... you could use something like OLE to automatically import parts of your document. Digitally sign the original and change the imported bits whenever you feel like it.

Unless you can trust the viewer (which means trusting the format) you can't trust the document which makes the signature worthless.

(also see Kevin's remark).

EuripidesMay 17, 2006 1:14 AM

@Thomas: You could use any format, if you have a standardized viewer, that disables any "active" components as OLE or Javascript and shows the Document in a standardized way. Of course you'd have to trust the viewer. But not the format.

Pat CahalanMay 17, 2006 11:46 AM

@ Roger

> It is often prudent to be somewhat cynical, but in this case I believe you have overdone it.

That's highly possible. My sleep frequency has gone waaay down in the last week, increasing overall grumpiness :)

ScottMay 18, 2006 10:09 AM

Certainly there are ways of specifying the technical, procedural and personnel security requirements that go into establishing a level of assurance in your PKI - as many readers here will know it's called a certificate policy and there's a framework for such docs standardized in RFC 3647. I can't find any evidence that a CP exists for this PA project though.

There's also a long term archival and notary services IETF working group that has a few I-Ds out there - interested folks should review those I-Ds and provide comment.

jiayinteMay 19, 2006 5:23 AM

We are the language bridge, which help you understand China.
Beijing Giant Company is a professionaltanslation company , which has devoted itself for the industry for about ten years. We offer professional service of document ltanslation and l interpretation , aiming at serving of economy & culture between China and all over the world

By our work you get the first step to entering into Chinese market and acquainting yourself with Chinese culture. At present, our company has been ranked ahead in the Chinese translation company
for its convenient service to the clients in China and abroad. Gianttranslation company
is able to carry on 70 kinds of languages including English, Russian, French, German, Spanish, Japanese, Arabic, Korean, Thai and Italian etc. if you have any question, don’t hesitate to contact us as soon as possible.
Welcome to China

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc..