Security service level agreements (SSLAs) provide a systematic way for end users at home or in the office to guarantee sufficient security level when doing business or exchanging sensitive personal or organizational data with an online service. In this paper, we propose an SSLA negotiation protocol that implements non-repudiation with cryptographic identities and digital signatures and includes features that make it resistant to denial of service attacks. The basic version of the protocol does not rely on the use of a trusted third party, and it can be used for all kinds of simple negotiations. For the negotiation about SSLAs, the protocol provides an option to use an external knowledge base that may help the user in the selection of suitable security measures. We have implemented a prototype of the system, which uses JSON Web Signature for the message exchange and made some performance tests with it. The results show that the computational effort required by the cryptographic operations of the negotiation protocol remains at a reasonable level.