Napredna pretraga

Pregled bibliografske jedinice broj: 617925

Bounded memory Dolev-Yao adversaries in collaborative systems

Kanovich, Max; Ban Kirigin, Tajana; Nigam, Vivek; Scedrov, Andre
Bounded memory Dolev-Yao adversaries in collaborative systems // Information and computation, Special issue on Security and Rewriting Techniques, 238 (2014), 233-261 doi:10.1016/j.ic.2014.07.011 (međunarodna recenzija, članak, znanstveni)

Bounded memory Dolev-Yao adversaries in collaborative systems

Kanovich, Max ; Ban Kirigin, Tajana ; Nigam, Vivek ; Scedrov, Andre

Information and computation, Special issue on Security and Rewriting Techniques (0890-5401) 238 (2014); 233-261

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
Collaborative systems; protocol security; complexity results

This paper extends existing models for collaborative systems. We investigate how much damage can be done by insiders alone, without collusion with an outside adversary. In contrast to traditional intruder models, such as in protocol security, all the players inside our system, including potential adversaries, have similar capabilities. They have bounded storage capacity, that is, they can only remember at any moment a bounded number of symbols. This is technically imposed by only allowing balanced actions, that is, actions that have the same number of facts in their pre- and post-conditions, and bounding the size of facts, that is, the number of symbols they contain. On the other hand, the adversaries inside our system have many capabilities of the standard Dolev-Yao intruder, namely, they are able, within their bounded storage capacity, to compose, decompose, overhear, and intercept messages as well as create fresh values. We investigate the complexity of the decision problem of whether or not an adversary is able to discover secret data. We show that this problem is PSPACE-complete when the size of messages is an input bound and when all actions are balanced and can possibly create fresh values. As an application, we turn to security protocol analysis and demonstrate that many protocol anomalies, such as the Lowe anomaly in the Needham-Schroeder public key exchange protocol, can also occur when the intruder is one of the insiders with bounded memory.

Izvorni jezik

Znanstvena područja

Extended version of the FAST 2010 paper.Special Issue on Security and Rewriting Techniques.


Projekt / tema
009-0091328-0941 - Logika i stvarnost (Majda Trobok, )
120-1203164-3074 - Matematička logika i primjene (Zvonimir Šikić, )

Filozofski fakultet, Rijeka,
Fakultet strojarstva i brodogradnje, Zagreb,
Sveučilište u Rijeci - Odjel za matematiku

Autor s matičnim brojem:
Tajana Ban-Kirigin, (229313)

Časopis indeksira:

  • Current Contents Connect (CCC)
  • Web of Science Core Collection (WoSCC)
    • Science Citation Index Expanded (SCI-EXP)
    • SCI-EXP, SSCI i/ili A&HCI
  • Scopus

Uključenost u ostale bibliografske baze podataka:

  • CA Search (Chemical Abstracts)
  • Compu-Math Citation Index
  • EMBASE (Excerpta Medica)
  • Zentrallblatt für Mathematik/Mathematical Abstracts
  • Scopus
  • ACM Guide to Computing Literature
  • Science Abstracts
  • Research Alert