The number of login options on websites has increased since the introduction of web single sign-on (SSO) protocols. Web SSO services allow users to grant websites or relying parties (RPs) access to their personal profile information from identity provider (IdP) accounts. Many RP sites fail to provide sufficient privacy-related information to allow users to make informed login decisions. Moreover, privacy differences in permission requests across login options are largely hidden from users and are time-consuming to manually extract and compare. In this article, we present an empirical analysis of popular RP implementations supporting three major IdP login options (Facebook, Google, and Apple) and categorize RPs in the top 500 sites into four client-side code patterns. Informed by these RP patterns, we design and implement SSOPrivateEye (SPEye), a browser extension prototype that extracts and displays to users permission request information from SSO login options in RPs covering the three IdPs.

Academic research has highlighted the failure of many Internet of Things (IoT) product manufacturers to follow accepted practices, while IoT security best practices have recently attracted considerable attention worldwide from industry and governments. Given current examples of security advice, confusion is evident from guidelines that conflate desired outcomes with security practices to achieve those outcomes. We explore a surprising lack of clarity, and void in the literature, on what (generically) best practice means, independent of identifying specific individual practices or highlighting failure to follow best practices. We consider categories of security advice, and analyze how they apply over the lifecycle of IoT devices. For concreteness in discussion, we use iterative inductive coding to code and systematically analyze a set of 1,013 IoT security best practices, recommendations, and guidelines collated from industrial, government, and academic sources. Among our findings, of all analyzed items, 68% fail to meet our definition of an (actionable) practice, and 73% of all actionable advice relates to the software development lifecycle phase, highlighting the critical position of manufacturers and developers. We hope that our work provides a basis for the community to better understand best practices, identify and reach consensus on specific practices, and find ways to motivate relevant stakeholders to follow them.

Password-authenticated key exchange (PAKE) is a major area of cryptographic protocol research and practice. Many PAKE proposals have emerged in the 30 years following the original 1992 Encrypted Key Exchange (EKE), some accompanied by new theoretical models to support rigorous analysis. To reduce confusion and encourage practical development, major standards bodies including IEEE, ISO/IEC and the IETF have worked towards standardizing PAKE schemes, with mixed results. Challenges have included contrasts between heuristic protocols and schemes with security proofs, and subtleties in the assumptions of such proofs rendering some schemes unsuitable for practice. Despite initial difficulty identifying suitable use cases, the past decade has seen PAKE adoption in numerous large-scale applications such as Wi-Fi, Apple's iCloud, browser synchronization, e-passports, and the Thread network protocol for Internet of Things devices. Given this backdrop, we consolidate three decades of knowledge on PAKE protocols, integrating theory, practice, standardization and real-world experience. We provide a thorough and systematic review of the field, a summary of the state-of-the-art, a taxonomy to categorize existing protocols, and a comparative analysis of protocol performance using representative schemes from each taxonomy category. We also review real-world applications, summarize lessons learned, and highlight open research problems related to PAKE protocols.

Many password alternatives for web authentication proposed over the years, despite having different designs and objectives, all predominantly rely on the knowledge of some secret. This motivates us, herein, to provide the first detailed exploration of the integration of a fundamentally different element of defense into the design of web authentication schemes: a mimicry-resistance dimension. We analyze web authentication mechanisms with respect to new usability and security properties related to mimicry-resistance (augmenting the UDS framework), and in particular evaluate invisible techniques (those requiring neither user actions, nor awareness) that provide some mimicry-resistance (unlike those relying solely on static secrets), including device fingerprinting schemes, PUFs (physically unclonable functions), and a subset of Internet geolocation mechanisms.

Many recent proposals to increase the resilience of the Web PKI against misbehaving CAs face significant obstacles to deployment. These hurdles include (1) the requirement of drastic changes to the existing PKI players and their interactions, (2) the lack of signaling mechanisms to protect against downgrade attacks, (3) the lack of an incremental deployment strategy, and (4) the use of inflexible mechanisms that hinder recovery from misconfiguration or from the loss or compromise of private keys. As a result, few of these proposals have seen widespread deployment, despite their promise of a more secure Web PKI. To address these roadblocks, we propose Certificates with Automated Policies and Signaling (CAPS), a system that leverages the infrastructure of the existing Web PKI to overcome the aforementioned hurdles. CAPS offers a seamless and secure transition away from today’s insecure Web PKI and towards present and future proposals to improve the Web PKI. Crucially, with CAPS, domains can take simple steps to protect themselves from MITM attacks in the presence of one or more misbehaving CAs, and yet the interaction between domains and CAs remains fundamentally the same. We implement CAPS and show that it adds at most 5% to connection establishment latency.

The Internet of Things (IoT) is a rapidly growing subset of our modern computing architecture, and as such, provides significant new attack surface. The history of IoT has provided a substantial body of topics to look back on: IoT's evolution, products, and major security incidents including the largest botnet ever witnessed. Unique to IoT, its architecture, interaction design, and scale make its many issues distinct from those in the Internet of Computers (IoC). Its perceptions, understandings, and definitions have evolved over time, thus requiring an updated focus from the perspective of security and cyberphysical safety. We take a fresh look at challenges and opportunities in IoT security, the characteristics that uniquely distinguish it from the IoC, and identify security-related questions that they raise. Our aim is to provide an up-to-date view of the IoT security landscape and technical security issues to help guide both existing and especially new researchers looking for challenging open problems that remain largely unaddressed.

The vast number of in-use Internet of Things (IoT) devices is by consensus, expected to continue rapid growth. These devices are subject to an expanding list of attacks that exploit both software vulnerabilities and design choices. This highlights the importance of architectural design of management for cryptographic keys involved in both initial configuration (onboarding) and secure, automatic update of device software and firmware. Low-level IoT devices with constrained processors and smaller registers and caches are computationally challenged to carry out desktop- and server-type public-key cryptographic operations, e.g., as needed for key establishment and authentication of software updates. To this end, we design and prototype an architecture for onboarding and secure software update of low-level IoT devices (8-bit). It uses elliptic curve cryptography (Curve25519), authenticated key establishment, and a known continuity-based key-locking mechanism that uses a public key embedded in a current software image to verify the signature on a software update. We also provide an informal security analysis. The design addresses the scenario of a transfer of update authority, e.g., when a manufacturer ceases to provide ongoing software updates upon going out of business.

This panel will explore how security topics are integrated into academic programs and future directions for improvements. It will address how early in time security should be introduced in programs like computer science and software engineering; and identify the critical takeaways that each graduating student should learn. We will try to separate out the important, practical concepts from the purely academic ones. We will also consider how well security programs translate to industry-focused needs: do students emerge with an understanding that is both deep and broad enough to be useful? In general, we will try to identify the pitfalls of current security education and how we can move forward as an academic community, in tandem with industry and government.

We introduce the first known mechanism providing realtime server location verification. Its uses include enhancing server authentication by enabling browsers to automatically interpret server location information. We describe the design of this new measurement-based technique, Server Location Verification (SLV), and evaluate it using PlanetLab. We explain how SLV is compatible with the increasing trends of geographically distributed content dissemination over the Internet, without causing any new interoperability conflicts. Additionally, we introduce the notion of (verifiable)server location pinning(conceptually similar to certificate pinning) to support SLV, and evaluate their combined impact using a server-authentication evaluation framework. The results affirm the addition of new security benefits to the existing TLS-based authentication mechanisms. We implement SLV through a location verification service, the simplest version of which requires no server-side changes. We also implement a simple browser extension that interacts seamlessly with the verification infrastructure to obtain realtime server location-verification results.

Delay-based Internet geolocation techniques are repeatedly positioned as well suited for security-sensitive applications, e.g., location-based access control, and credit-card verification. We present new strategies enabling adversaries to accurately control the forged location. Evaluation showed that using the new strategies, adversaries could misrepresent their true locations by over 15000km, and in some cases within 100km of an intended geographic location. This work significantly improves the adversary's control in misrepresenting its location, directly refuting the appropriateness of current techniques for security-sensitive applications. We finally discuss countermeasures to mitigate such strategies.

The past ten years has seen increasing calls to make security research more “scientific”. On the surface, most agree that this is desirable, given universal recognition of “science” as a positive force. However, we find that there is little clarity on what “scientific” means in the context of computer security research, or consensus on what a “Science of Security” should look like. We selectively review work in the history and philosophy of science and more recent work under the label “Science of Security”. We explore what has been done under the theme of relating science and security, put this in context with historical science, and offer observations and insights we hope may motivate further exploration and guidance. Among our findings are that practices on which the rest of science has reached consensus appear little used or recognized in security, and a pattern of methodological errors continues unaddressed.

Existing CAPTCHA solutions are a major source of user frustration on the Internet today, frequently forcing companies to lose customers and business. Game CAPTCHAs are a promising approach which may make CAPTCHA solving a fun activity for the user. One category of such CAPTCHAs – called Dynamic Cognitive Game (DCG) CAPTCHA – challenges the user to perform a game-like cognitive (or recognition) task interacting with a series of dynamic images. Specifically, it takes the form of many objects floating around within the images, and the user’s task is to match the objects corresponding to specific target(s), and drag/drop them to the target region(s). In this paper, we pursue a comprehensive analysis of DCG CAPTCHAs. We design and implement such CAPTCHAs, and dissect them across four broad but overlapping dimensions: (1) usability, (2) fully automated attacks, (3) human-solving relay attacks, and (4) hybrid attacks that combine the strengths of automated and relay attacks. Our study shows that DCG CAPTCHAs are highly usable, even on mobile devices and offer some resilience to relay attacks, but they are vulnerable to our proposed automated and hybrid attacks.

The number of location-aware services over the Internet continues growing. Some of these require the client's geographic location for security-sensitive applications. Examples include location-aware authentication, location-aware access policies, fraud prevention, complying with media licensing, and regulating online gambling/voting. An adversary can evade existing geolocation techniques, e.g., by faking GPS coordinates or employing a non-local IP address through proxy and virtual private networks. We devise Client Presence Verification (CPV), a delay-based verification technique designed to verify an assertion about a device's presence inside a prescribed geographic region. CPV does not identify devices by their IP addresses. Rather, the device's location is corroborated in a novel way by leveraging geometric properties of triangles, which prevents an adversary from manipulating measured delays. To achieve high accuracy, CPV mitigates Internet path asymmetry using a novel method to deduce one-way application-layer delays to/from the client's participating device, and mines these delays for evidence supporting/refuting the asserted location. We evaluate CPV through detailed experiments on PlanetLab, exploring various factors that affect its efficacy, including the granularity of the verified location, and the verification time. Results highlight the potential of CPV for practical adoption.

Mobile browsers are increasingly being relied upon to perform security sensitive operations. Like their desktop counterparts, these applications can enable SSL/TLS to provide strong security guarantees for communications over the web. However, the drastic reduction in screen size and the accompanying reorganization of screen real-estate significantly changes the use and consistency of the security indicators and certificate information that alert users of site identity and the presence of strong cryptographic algorithms. In this paper, we perform the first measurement of the state of critical security indicators in mobile browsers. We evaluate ten mobile and two tablet browsers, representing over 90% of the market share, against the recommended guidelines for web user interface to convey security set forth by the World Wide Web Consortium (W3C). While desktop browsers follow the majority of guidelines, our analysis shows that mobile browsers fall significantly short. We also observe notable inconsistencies across mobile browsers when such mechanisms actually are implemented. We show where and how these failures on mobile browsers eliminate clues previously designed for, and still present in, desktop browsers to detect attacks such as phishing and man-in-the-middle. Finally, we offer advice on where current standards are unclear or incomplete.

Existing captcha solutions on the Internet are a major source of user frustration. Game captchas are an interesting and, to date, little-studied approach claiming to make captcha solving a fun activity for the users. One broad form of such captchas -- called Dynamic Cognitive Game (DCG) captchas -- challenge the user to perform a game-like cognitive task interacting with a series of dynamic images. We pursue a comprehensive analysis of a representative category of DCG captchas. We formalize, design and implement such captchas, and dissect them across: (1) fully automated attacks, (2) human-solver relay attacks, and (3) usability. Our results suggest that the studied DCG captchas exhibit high usability and, unlike other known captchas, offer some resistance to relay attacks, but they are also vulnerable to our novel dictionary-based automated attack.

Android's trust-on-first-use application signing model associates developers with a fixed code signing certificate, but lacks a mechanism to enable transparent key updates or certificate renewals. The model allows application updates to be recognized as authorized by a party with access to the original signing key. However, changing keys or certificates requires that end users manually uninstall/reinstall apps, losing all non-backed up user data. In this paper, we show that with appropriate OS support, developers can securely and without user intervention transfer signing authority to a new signing key. Our proposal, Baton, modifies Android's app installation framework enabling key agility while preserving backwards compatibility with current apps and current Android releases. Baton is designed to work consistently with current UID sharing and signature permission requirements. We discuss technical details of the Android-specific implementation, as well as the applicability of the Baton protocol to other decentralized environments.

We explore the robustness and usability of moving-image object recognition (video) CAPTCHAS, designing and implementing automated attacks based on computer vision techniques. Our approach is suitable for broad classes of moving-image CAPTCHAS involving rigid objects. We first present an attack that defeats instances of such a CAPTCHA (NuCaptcha) representing the state-of-the-art, involving dynamic text strings called codewords. We then consider design modifications to mitigate the attacks (e.g., overlapping characters more closely, randomly changing the font of individual characters, or even randomly varying the number of characters in the codeword). We implement the modified CAPTCHAS and test if designs modified for greater robustness maintain usability. Our lab-based studies show that the modified captchas fail to offer viable usability, even when the captcha strength is reduced below acceptable targets. Worse yet, our GPU-based implementation shows that our automated approach can decode these captchas faster than humans can, and we can do so at a relatively low cost of roughly 50 cents per 1,000 captchas solved based on Amazon EC2 rates circa 2012. To further demonstrate the challenges in designing usable captchas, we also implement and test another variant of moving text strings using the known emerging images concept. This variant is resilient to our attacks and also offers similar usability to commercially available approaches. We explain why fundamental elements of the emerging images idea resist our current attack where others fail.

A New Security Paradigms Workshop (2013) panel discussed the topic of ethical issues and implications related to markets for zero-day exploits, i.e., markets facilitating the sale of previously unknown details on how to exploit software vulnerabilities in target applications or systems. The related topic of vulnerability rewards programs ("bug bounties" offered by software vendors) was also discussed. This note provides selected background material submitted prior to the panel presentation, and summarizes discussion resulting from the input of both the panelists and NSPW participants.

Internet users today depend daily on HTTPS for secure communication with sites they intend to visit. Over the years, many attacks on HTTPS and the certificate trust model it uses have been hypothesized, executed, and/or evolved. Meanwhile the number of browser-trusted (and thus, de facto, user-trusted) certificate authorities has proliferated, while the due diligence in baseline certificate issuance has declined. We survey and categorize prominent security issues with HTTPS and provide a systematic treatment of the history and on-going challenges, intending to provide context for future directions. We also provide a comparative evaluation of current proposals for enhancing the certificate infrastructure used in practice.

Passwords continue to prevail on the web as the primary method for user authentication despite their well-known security and usability drawbacks. Password managers offer some improvement without requiring server-side changes. In this paper, we evaluate the security of dual-possession authentication, an authentication approach offering encrypted storage of passwords and theft-resistance without the use of a master password. We further introduce Tapas, a concrete implementation of dual-possession authentication leveraging a desktop computer and a smartphone. Tapas requires no server-side changes to websites, no master password, and protects all the stored passwords in the event either the primary or secondary device (e.g., computer or phone) is stolen. To evaluate the viability of Tapas as an alternative to traditional password managers, we perform a 30 participant user study comparing Tapas to two configurations of Firefox's built-in password manager. We found users significantly preferred Tapas. We then improve Tapas by incorporating feedback from this study, and reevaluate it with an additional 10 participants.

We evaluate two decades of proposals to replace text passwords for general-purpose user authentication on the web using a broad set of twenty-five usability, deployability and security benefits that an ideal scheme might provide. The scope of proposals we survey is also extensive, including password management software, federated login protocols, graphical password schemes, cognitive authentication schemes, one-time passwords, hardware tokens, phone-aided schemes and biometrics. Our comprehensive approach leads to key insights about the difficulty of replacing passwords. Not only does no known scheme come close to providing all desired benefits: none even retains the full set of benefits that legacy passwords already provide. In particular, there is a wide range from schemes offering minor security benefits beyond legacy passwords, to those offering significant security benefits in return for being more costly to deploy or more difficult to use. We conclude that many academic proposals have failed to gain traction because researchers rarely consider a sufficiently wide range of real-world constraints. Beyond our analysis of current schemes, our framework provides an evaluation methodology and benchmark for future web authentication proposals.

ABSTRACT Network scanning is a common, effective technique to search for vulnerable Internet hosts and to explore the topology and trust relationships between hosts in a target network. Given that the purpose of scanning is to search for responsive hosts and network services, behavior‐based scanning detection techniques based on the state of inbound connection attempts remain effective against evasion. Many of today's network environments, however, feature a dynamic and transient nature with several network hosts and services added or stopped (either permanently or temporarily) over time. In this paper, working with recent network traces from two different environments, we re‐examine the Threshold Random Walk (TRW) scan detection algorithm, and we show that the number of false positives is proportional to the transiency of the offered services. To address the limitations found, we present a modified algorithm (Stateful Threshold Random Walk (STRW) algorithm) that utilizes active mapping of network services to take into account benign causes of failed connection attempts. The STRW algorithm eliminates a significant portion of TRW false positives (e.g., 29% and 77% in two datasets studied). Copyright © 2012 John Wiley & Sons, Ltd.

Brute force and dictionary attacks on password-only remote login services are now widespread and ever increasing. Enabling convenient login for legitimate users while preventing such attacks is a difficult problem. Automated Turing Tests (ATTs) continue to be an effective, easy-to-deploy approach to identify automated malicious login attempts with reasonable cost of inconvenience to users. In this paper, we discuss the inadequacy of existing and proposed login protocols designed to address large-scale online dictionary attacks (e.g., from a botnet of hundreds of thousands of nodes). We propose a new Password Guessing Resistant Protocol (PGRP), derived upon revisiting prior proposals designed to restrict such attacks. While PGRP limits the total number of login attempts from unknown remote hosts to as low as a single attempt per username, legitimate users in most cases (e.g., when attempts are made from known, frequently-used machines) can make several failed login attempts before being challenged with an ATT. We analyze the performance of PGRP with two real-world data sets and find it more promising than existing proposals.

This paper presents an integrated evaluation of the Persuasive Cued Click-Points graphical password scheme, including usability and security evaluations, and implementation considerations. An important usability goal for knowledge-based authentication systems is to support users in selecting passwords of higher security, in the sense of being from an expanded effective security space. We use persuasion to influence user choice in click-based graphical passwords, encouraging users to select more random, and hence more difficult to guess, click-points.

We consider the problem of malicious modification of digital objects. We present a protection mechanism designed to protect against unauthorized replacement or modification of digital objects while still allowing authorized updates transparently. We use digital signatures without requiring any centralized public key infrastructure. To explore the viability of our proposal, we apply the approach to file-system binaries, implementing a prototype in Linux which protects operating system and application binaries on disk. To test the prototype and related kernel modifications, we show that it protects against various rootkits currently available while incurring minimal overhead costs. The general approach can be used to restrict updates to general digital objects.

Network scanning reveals valuable information of accessible hosts over the Internet and their offered network services, which allows significant narrowing of potential targets to attack. Addressing and balancing a set of sometimes competing desirable properties is required to make network scanning detection more appealing in practice: 1) fast detection of scanning activity to enable prompt response by intrusion detection and prevention systems; 2) acceptable rate of false alarms, keeping in mind that false alarms may lead to legitimate traffic being penalized; 3) high detection rate with the ability to detect stealthy scanners; 4) efficient use of monitoring system resources; and 5) immunity to evasion. In this paper, we present a scanning detection algorithm designed to accommodate all of these goals. LQS is a fast, accurate, and light-weight scan detection algorithm that leverages the key properties of the monitored network environment as variables that affect how the scanning detection algorithm operates. We also present what is, to our knowledge, the first automated way to estimate a reference baseline in the absence of ground truth, for use as an evaluation methodology for scan detection. Using network traces from two sites, we evaluate LQS and compare its scan detection results with those obtained by the state-of-the-art TRW algorithm. Our empirical analysis shows significant improvements over TRW in all of these properties.

Our agenda is two-fold. First, we introduce and give a technical description of gridWord, a novel knowledge-based authentication mechanism involving elements of both text and graphical passwords. It is intended to address a new research challenge arising from the evolution of Internet access devices, and which may arguably be viewed as motivating a new paradigm: remote access password schemes which accommodate users who alternately login from devices with, and without, full physical keyboards (e.g., users alternating between desktops with easy text input, and mobile devices with tiny or touch-screen virtual keyboards). While the core ideas behind gridWord are well-formed, and may be viewed as a new variation of old (text-based) ideas of building passwords from multiple words, many aspects including recommended parameterization and configuration details, preferred platforms, and primary targets of application remain to be explored in detail. We nonetheless solicit early feedback from the community for several reasons, related to our second agenda item: we use gridWord as a concrete target to focus exploration of a number of questions involving (a) the evaluation of usable security proposals, (b) the often conflicting objectives of various parties involved in the publication of academic research, and (c) the relationship between the design and publication of new security mechanisms and the pursuit of scientific knowledge through experimentation. We believe the second agenda item is important to pursue, given our observation that experts in usability and security have widely varying expectations, and lack consensus on what is important for the evaluation, comparison, and publication of usable security proposals.

Internet authentication for popular end-user transactions, such as online banking and e-commerce, continues to be dominated by passwords entered through end-user PCs. Most users continue to prefer (typically untrusted) PCs over smaller personal devices for actual transactions, due to usability features related to keyboard and screen size. However, most such transactions and their underlying protocols are vulnerable to attacks including keylogging, phishing and pharming. We propose Mobile Password Authentication (MP-Auth) to counter such attacks, which cryptographically separates a user's long-term secret input from the client PC, and offers transaction integrity. The PC continues to be used for most of the interaction but has access only to temporary secrets, while the user's long-term secret is input through an independent personal device, e.g., a cellphone which makes it available to the PC only after encryption under the intended far-end recipient's public key. MP-Auth expects users to input passwords only to a personal device, and be vigilant while confirming transactions from the device. To facilitate a comparison to MP-Auth, we also provide a comprehensive survey of web authentication techniques that use an additional factor of authentication; this survey may be of independent interest.

We provide an in-depth study of the security of click-based graphical password schemes like PassPoints (Weidenbeck et al., 2005), by exploring popular points (hot-spots), and examining strategies to predict and exploit them in guessing attacks. We report on both short- and long-term user studies: one lab-controlled, involving 43 users and 17 diverse images, the other a field test of 223 user accounts. We provide empirical evidence that hot-spots do exist for many images, some more so than others. We explore the use of “human-computation” (in this context, harvesting click-points from a small set of users) to predict these hot-spots. We generate two “human-seeded” attacks based on this method: one based on a first-order Markov model, another based on an independent probability model. Within 100 guesses, our first-order Markov model-based attack finds 4% of passwords in one image's data set, and 10% of passwords in a second image's data set. Our independent model-based attack finds 20% within 2 33 guesses in one image's data set and 36% within 2 31 guesses in a second image's data set. These are all for a system whose full password space has cardinality 2 43 . We evaluate our first-order Markov model-based attack with cross-validation of the field study data, which finds an average of 7–10% of user passwords within 3 guesses. We also begin to explore some click-order pattern attacks, which we found improve on our independent model-based attacks. Our results suggest that these graphical password schemes (with parameters as originally proposed) are vulnerable to offline and online attacks, even on systems that implement conservative lock-out policies.

Despite all efforts, password schemes intended to deploy or encourage the use of strong passwords have largely failed. As an alternative to enable users to create, maintain, and use high-quality passwords willingly, we propose Object-based Password (ObPwd), leveraging the universe of personal or personally meaningful digital content that many users now own or have access to. ObPwd converts user-selected digital objects to high-entropy text passwords. Memorization of exact passwords is replaced by remembering password objects. We present the design details, variants, and usability and security analysis of ObPwd, and report on the results of a hybrid in-lab/at-home user study on 32 participants. The results suggest the scheme has good usability, with excellent memorability, acceptable login times, and very positive user perception, achieved while providing strong security for the threat context explored. We believe this work lays the foundation for a promising password selection paradigm.

Graphical passwords have been proposed to address known problems with traditional text passwords. For example, memorable user-chosen text passwords are predictable, but random system-assigned passwords are difficult to remember. We explore the usability effects of modifying system parameters to increase the security of a click-based graphical password system. Generally, usability tests for graphical passwords have used configurations resulting in password spaces smaller than that of common text passwords. Our two-part lab study compares the effects of varying the number of click-points and the image size, including when different configurations provide comparable password spaces. For comparable spaces, no usability advantage was evident between more click-points, or a larger image. This is contrary to our expectation that larger image size (with fewer click-points) might offer usability advantages over more click-points (with correspondingly smaller images). The results suggest promising opportunities for better matching graphical password system configurations to device constraints, or capabilities of individual users, without degrading usability. For example, more click-points could be used on smart-phone displays where larger image sizes are not possible.

Permission-based security models provide controlled access to various system resources. The expressiveness of the permission set plays an important role in providing the right level of granularity in access control. In this work, we present a methodology for the empirical analysis of permission-based security models which makes novel use of the Self-Organizing Map (SOM) algorithm of Kohonen (2001). While the proposed methodology may be applicable to a wide range of architectures, we analyze 1,100 Android applications as a case study. Our methodology is of independent interest for visualization of permission-based systems beyond our present Android-specific empirical analysis. We offer some discussion identifying potential points of improvement for the Android permission model attempting to increase expressiveness where needed without increasing the total number of permissions or overall complexity.

We address the problem of restricting root's ability to change arbitrary files on disk, in order to prevent abuse on most current desktop operating systems. The approach first involves recognizing and separating out the ability to configure a system from the ability to use the system to perform tasks. The permission to modify configuration of the system is then further subdivided in order to restrict applications from modifying the file-system objects of other applications. We explore the division of root's current ability to change arbitrary files on disk and discuss a prototype that proves out the viability of the approach for designated system-wide file-system objects. Our architecture exposes a control point available for use to enforce policies that prevent one application from modifying another's file-system objects. In addition, we review in detail the permissions given to current installers, and alternative approaches for secure software installation.

We introduce and evaluate various methods for purely automated attacks against PassPoints-style graphical passwords. For generating these attacks, we introduce a graph-based algorithm to efficiently create dictionaries based on heuristics such as click-order patterns (e.g., five points all along a line). Some of our methods combine click-order heuristics with focus-of-attention scan-paths generated from a computational model of visual attention, yielding significantly better automated attacks than previous work. One resulting automated attack finds 7%-16% of passwords for two representative images using dictionaries of approximately 226entries (where the full password space is 243). Relaxing click-order patterns substantially increased the attack efficacy albeit with larger dictionaries of approximately 235entries, allowing attacks that guessed 48%-54% of passwords (compared to previous results of 1% and 9% on the same dataset for two images with 235guesses). These latter attacks are independent of focus-of-attention models, and are based on image-independent guessing patterns. Our results show that automated attacks, which are easier to arrange than human-seeded attacks and are more scalable to systems that use multiple images, require serious consideration when deploying basic PassPoints-style graphical passwords.

The underlying issues relating to the usability and security of multiple passwords are largely unexplored. However, we know that people generally have difficulty remembering multiple passwords. This reduces security since users reuse the same password for different systems or reveal other passwords as they try to log in. We report on a laboratory study comparing recall of multiple text passwords with recall of multiple click-based graphical passwords. In a one-hour session (short-term), we found that participants in the graphical password condition coped significantly better than those in the text password condition. In particular, they made fewer errors when recalling their passwords, did not resort to creating passwords directly related to account names, and did not use similar passwords across multiple accounts. After two weeks, participants in the two conditions had recall success rates that were not statistically different from each other, but those with text passwords made more recall errors than participants with graphical passwords. In our study, click-based graphical passwords were significantly less susceptible to multiple password interference in the short-term, while having comparable usability to text passwords in most other respects.

Visualization is used by security analysts to help detect patterns and trends in large volumes of network traffic data. With IPv6 slowly being deployed around the world, network intruders are beginning to adapt their tools and techniques to work over IPv6 (vs. IPv4). Many tools for visualizing network activity, while useful for detecting large scale attacks and network behavior anomalies still only support IPv4. In this paper, we explore the current state of IPv6 support in some popular security visualization tools and identify the roadblocks preventing those tools from supporting the new protocol. We propose a filtering technique that helps reduce the occlusion of IPv6 sources on graphs. We also suggest using treemaps for visually representing the vast space of remote addresses in IPv6.

Graphical analysis of network traffic flows helps security analysts detect patterns or behaviors that would not be obvious in a text-based environment. The growing volume of network data generated and captured makes it increasingly difficult to detect increasingly sophisticated reconnaissance and stealthy network attacks. We propose a network flow filtering mechanism that leverages the exposure maps technique of Whyte et al. (2007), reducing the traffic for the visualization process according to the network services being offered. This allows focus to be limited to selected subsets of the network traffic, for example what might be categorized (correctly or otherwise) as the unexpected or potentially malicious portion. In particular, we use this technique to filter out traffic from sources that have not gained knowledge from the network in question. We evaluate the benefits of our technique on different visualizations of network flows. Our analysis shows a significant decrease in the volume of network traffic that is to be visualized, resulting in visible patterns and insights not previously apparent.

We present and evaluate various methods for purely automated attacks against click-based graphical passwords. Our purely automated methods combine click-order heuristics with focus-of-attention scan-paths generated from a computational model of visual attention. Our method results in a significantly better automated attack than previous work, guessing 8-15% of passwords for two representative images using dictionaries of less than 224.6entries, and about 16% of passwords on each of these images using dictionaries of less than 231.4entries (where the full password space is 243). Relaxing our click-order pattern substantially increased the efficacy of our attack albeit with larger dictionaries of 234.7entries, allowing attacks that guessed 48-54% of passwords (compared to previous results of 0.9% and 9.1% on the same two images with 235guesses). These latter automated attacks are independent of focus-of-attention models, and are based on image-independent guessing patterns. Our results show that automated attacks, which are easier to arrange than human-seeded attacks and are more scalable to systems that use multiple images, pose a significant threat.

Unrestricted information flows are a key security weakness of current web design. Cross-site scripting, cross-site request forgery, and other attacks typically require that information be sent or retrieved from arbitrary, often malicious, web servers. In this paper we propose Same Origin Mutual Approval (SOMA), a new policy for controlling information flows that prevents common web vulnerabilities. By requiring site operators to specify approved external domains for sending or receiving information, and by requiring those external domains to also approve interactions, we prevent page content from being retrieved from malicious servers and sensitive information from being communicated to an attacker. SOMA is compatible with current web applications and is incrementally deployable, providing immediate benefits for clients and servers that implement it. SOMA has an overhead of one additional HTTP request per domain accessed and can be implemented with minimal effort by application and web browser developers. To evaluate our proposal, we have developed a Firefox SOMA add-on.

The complexity of current Internet applications makes understanding network traffic a challenging task. By providing larger-scale aggregates for analysis, unsupervised clustering approaches can greatly aid in the identification of new applications, attacks, and other changes in network usage patterns. In this paper we introduce ADHIC, a new algorithm that clusters similar network traffic together without prior knowledge of protocol structures. Packet similarity is determined through comparisons of substrings within packets at distinguishing offsets. ADHIC is notable in that it 1) produces a hierarchical decomposition of network traffic in the form of a cluster-identifying decision tree, 2) needs only a small fraction of packets to generate the tree, and 3) clusters packets at wire speeds. We find that ADHIC appropriately segregates well-known protocols, clusters together traffic of the same protocol running on multiple ports, and segregates traffic from applications, such as p2p, that do not use standard ports. Potential applications include network performance analysis, real-time alerts of flash crowds or worm activity, and dynamic DoS-resistant bandwidth management. NetADHICT, our implementation of ADHIC, is available for download and is licensed under the GNU GPL license.

Large-scale data breaches exposing sensitive personal information are becoming commonplace. For numerous reasons, conventional personal (identification) information leaks from databases that store online and/or on-site user transaction data. Collected ID numbers and supporting personal information enable malicious parties to commit large-scale identity fraud. Gates and Slonim (NSPW 2003) proposed the owner-controlled information paradigm to address privacy violations of personal information where users are expected to maintain all their information using a personal device. Rubin and Wright (FC 2001), Molloy et al. (FC 2007), and others explored the use of one-time numbers to address credit card fraud (mostly for online use). However, several other types of ID number are at least as sensitive as credit card numbers. Our fundamental assumption is that collected personal information will eventually be breached. To combat identity fraud under this new environmental attack paradigm, we introduce a more general approach involving localized or customized ID numbers for both card-present and card-not-present transactions. We also explore four variants of the general idea to spark more discussion and further research in this area.

We argue that application developers, while often viewed as allies in the effort to create software with fewer security vulnerabilities, are not reliable allies. They have varying skill sets which often do not include security. Moreover, we argue that it is inefficient and unrealistic to expect to be able to successfully teach all of the world's population of software developers to be security experts. We suggest more efficient and effective alternatives, focusing on those developers who produce core functionality used by other developers (e.g. those who develop popular APIs -- Application Programming Interfaces). We discuss the benefits of designing APIs which can be easily used in a secure fashion to encourage security. We also introduce two straw-man proposals which integrate security into the work- ow of an application developer. Data tagging and unsuppressible warnings provide the basis for further work where the most natural use (path of least resistance) results in secure code. We believe there are benefits to co-opting developers into programming securely.

Password restriction policies and advice on creating secure passwords have limited effects on password strength. Influencing users to create more secure passwords remains an open problem. We have developed Persuasive Text Passwords (PTP), a text password creation system which leverages Persuasive Technology principles to influence users in creating more secure passwords without sacrificing usability. After users choose a password during creation, PTP improves its security by placing randomly-chosen characters at random positions into the password. Users may shuffle to be presented with randomly-chosen and positioned characters until they find a combination they feel is memorable. In this paper, we present an 83-participant user study testing four PTP variations. Our results show that the PTP variations significantly improved the security of users' passwords. We also found that those participants who had a high number of random characters placed into their passwords would deliberately choose weaker pre-improvement passwords to compensate for the memory load. As a consequence of this compensatory behaviour, there was a limit to the gain in password security achieved by PTP.

Publishing personal content on the web is gaining increased popularity with dramatic growth in social networking websites, and availability of cheap personal domain names and hosting services. Although the Internet enables easy publishing of any content intended to be generally accessible, restricting personal content to a selected group of contacts is more difficult. Social networking websites partially enable users to restrict access to a selected group of users of the same network by explicitly creating a "friends' list." While this limited restriction supports users' privacy on those (few) selected websites, personal websites must still largely be protected manually by sharing passwords or obscure links. Our focus is the general problem of privacy-enabled web content sharing from any user-chosen web server. By leveraging the existing "circle of trust" in popular Instant Messaging (IM) networks, we propose a scheme called IM-based Privacy-Enhanced Content Sharing (IMPECS) for personal web content sharing. IMPECS enables a publishing user's personal data to be accessible only to her IM contacts. A user can put her personal web page on any web server she wants (vs. being restricted to a specific social networking website), and maintain privacy of her content without requiring site-specific passwords. Our prototype of IMPECS required only minor modifications to an IM server, and PHP scripts on a web server. The general idea behind IMPECS extends beyond IM and IM circles of trust; any equivalent scheme, (ideally) containing pre-arranged groups, could similarly be leveraged.

In commonplace text-based password schemes, users typically choose passwords that are easy to recall, exhibit patterns, and are thus vulnerable to brute-force dictionary attacks. This leads us to ask whether other types of passwords (e.g., graphical) are also vulnerable to dictionary attack because of users tending to choose memorable passwords. We suggest a method to predict and model a number of such classes for systems where passwords are created solely from a user's memory. We hypothesize that these classes define weak password subspaces suitable for an attack dictionary. For user-drawn graphical passwords, we apply this method with cognitive studies on visual recall. These cognitive studies motivate us to define a set of password complexity factors (e.g., reflective symmetry and stroke count), which define a set of classes. To better understand the size of these classes and, thus, how weak the password subspaces they define might be, we use the “Draw-A-Secret” (DAS) graphical password scheme of Jermyn et al. [1999] as an example. We analyze the size of these classes for DAS under convenient parameter choices and show that they can be combined to define apparently popular subspaces that have bit sizes ranging from 31 to 41—a surprisingly small proportion of the full password space (58 bits). Our results quantitatively support suggestions that user-drawn graphical password systems employ measures, such as graphical password rules or guidelines and proactive password checking.

We exploit for defensive purposes the concept of darkports ­ the unused ports on active systems. We are particularly in- terested in such ports which transition to become active (i.e. become trans-darkports). Darkports are identified by pas- sively observing and characterizing the connectivity behav- ior of internal hosts in a network as they respond to both le- gitimate connection attempts and scanning attempts. Dark- ports can be used to detect sophisticated scanning activity, enable fine-grained automated defense against automated malware attacks, and detect real-time changes in a network that may indicate a successful compromise. We show, in a direct comparison with Snort, that darkports offer a better scanning detection capability with fewer false positives and negatives. Our results also show that the network awareness gained by the use of darkports enables active response op- tions to be safely focused exclusively on those systems that directly threaten the network.

Online banking is one of the most sensitive tasks performed by general Internet users. Most traditional banks now offer online banking services, and strongly encourage customers to do online banking with 'peace of mind.' Although banks heavily advertise an apparent '100% online security guarantee,' typically the fine print makes this conditional on users fulfilling certain security requirements. We examine some of these requirements as set by major Canadian banks, in terms of security and usability. We opened personal checking accounts at the five largest Canadian banks, and one online-only bank. We found that many security requirements are too difficult for regular users to follow, and believe that some marketing-related messages about safety and security actually mislead users. We are also interested in what kind of computer systems people really use for online banking, and whether users satisfy common online banking requirements. Our survey of 123 technically advanced users from a university environment strongly supports our view of an emerging gap between banks' expectations (or at least what their written customer policy agreements imply) and users' actions related to security requirements of online banking. Our participants, being more security-aware than the general population, arguably makes our results best-case regarding what can be expected from regular users. Yet most participants failed to satisfy common security requirements, implying most online banking customers do not (or cannot) follow banks' stated end-user security requirements and guidelines. The survey also sheds light on the security settings of systems used for sensitive online transactions. This work is intended to spur a discussion on real-world system security and user responsibilities, in a scenario where everyday users are heavily encouraged to perform critical tasks over the Internet, despite the continuing absence of appropriate tools to do so.

Identity fraud (IDF) may be defined informally as exploitation of credential information using some form of impersonation or misrepresentation of identity, in the context of transactions. Thus, IDF may be viewed as a combination of two old problems: user authentication and transaction authorization. We propose an innovative approach to detect IDF attempts, by combining av-certificates (digitally-signed audiovisual recordings in which users identify themselves) with av-signatures (audiovisual recordings showing users' explicit consent for unique transaction details). Av- certificates may be used in on-site transactions, to confirm user identity. In the case of remote (e.g. web-based) transactions, both av-certificates and av-signatures may be used to authenticate users and verify their consent for transaction details. Conventional impersonation attacks, whereby credentials (e.g. passwords, biometrics, or signing keys) are used without the consent of their legitimate users, fail against VideoTicket. The proposed solution assumes that identity thieves have access to such credentials.

Click-based graphical passwords, which involve clicking a set of user-selected points, have been proposed as a usable alternative to text passwords. We conducted two user studies: an initial lab study to revisit these usability claims, explore for the first time the impact on usability of a wide-range of images, and gather information about the points selected by users; and a large-scale field study to examine how click-based graphical passwords work in practice. No such prior field studies have been reported in the literature. We found significant differences in the usability results of the two studies, providing empirical evidence that relying solely on lab studies for security interfaces can be problematic. We also present a first look at whether interference from having multiple graphical passwords affects usability and whether more memorable passwords are necessarily weaker in terms of security.

Tor is a popular privacy tool designed to help achieve online anonymity by anonymising web traffic. Employing cognitive walkthrough as the primary method, this paper evaluates four competing methods of deploying Tor clients, and a number of software tools designed to be used in conjunction with Tor: Vidalia, Privoxy, Torbutton, and FoxyProxy. It also considers the standalone anonymous browser TorPark. Our results show that none of the deployment options are fully satisfactory from a usability perspective, but we offer suggestions on how to incorporate the best aspects of each tool. As a framework for our usability evaluation, we also provide a set of guidelines for Tor usability compiled and adapted from existing work on usable security and human-computer interaction.

It is well known that the Border Gateway Protocol (BGP), the IETF standard interdomain routing protocol, is vulnerable to a variety of attacks, and that a single misconfigured or malicious BGP speaker could result in large-scale service disruption. In this paper, we present Pretty Secure BGP (psBGP) ---a proposal for securing BGP, including an architectural overview, design details for significant aspects, and preliminary security and operational analysis. psBGP differs from other security proposals (e.g., S-BGP and soBGP) in that it makes use of a single-level PKI for AS number authentication, a decentralized trust model for verifying the propriety of IP prefix origin, and a rating-based stepwise approach for AS_PATH (integrity) verification. psBGP trades off the strong security guarantees of S-BGP for presumed-simpler operation, e.g., using a PKI with a simple structure, with a small number of certificate types, and of manageable size. psBGP is designed to successfully defend against various (nonmalicious and malicious) threats from uncoordinated BGP speakers, and to be incrementally deployed with incremental benefits.

Malicious mass-mailing activity on the Internet is a serious and continuing threat that includes mass-mailing worms, spam, and phishing. A mechanism commonly used to deliver such malicious mass mail is an SMTP-engine, which turns an infected system into a malicious mail server. We present a technique that enables, within a single mailing attempt in many popular network environments, detection and containment of (even zero-day) SMTP-engine based mass-mailing activity. Contrary to other mass-mailing detection techniques our approach is content independent and requires no attachment processing, network traffic correlation, statistical measures, or system behavioral analysis. It relies instead on the observation of DNS MX queries within the enterprise network. This stateless detection technique requires minimal computational resources making it ideally suited for real-time wire-speed deployment.

Google went down for 15 to 60 minutes around 22:10, May 07, 2005 UTC. This was explained by Google as having been caused by internal DNS misconfigurations. Another vulnerable protocol which could have caused such service outage is BGP. To pursue the latter possibility further, we explore how BGP was functioning during that period of time using the RouteViews BGP data set. Interestingly, our investigation reveals that one autonomous system (i.e., AS 174 operated by Cogent), which is apparently independent from Google, mysteriously originated routes for one of the IP prefixes assigned to Google (134.233.161.0/24) immediately prior to the service outage. As a result, 49.1% of ASes re-advertising routes for 64.233.161.0/24 switched to the incorrect path. Those poisoned ASes directly serve 1500 IP prefixes, and span a broad range of geographic locations. Since this erroneous prefix origination apparently has not occurred previously, or after this specific instance, we consider that it might have been the result of malicious activity (e.g., compromise of one or more BGP speakers) and contributed at least partially to Google's service outage.

Automated Turing Tests (ATTs), also known as human-in-the-loop techniques, were recently employed in a login protocol by Pinkas and Sander (2002) to protect against online password-guessing attacks. We present modifications providing a new history-based login protocol with ATTs, which uses failed-login counts. Analysis indicates that the new protocol offers opportunities for improved security and user friendliness (fewer ATTs to legitimate users) and greater flexibility (e.g., allowing protocol parameter customization for particular situations and users). We also note that the Pinkas--Sander and other protocols involving ATTs are susceptible to minor variations of well-known middle-person attacks. We discuss complementary techniques to address such attacks, and to augment the security of the original protocol.

This panel highlights a selection of the most interesting and provocative papers from the 2005 New Security Paradigms Workshop. This workshop was held September 2005 - the URL for more information is http://www.nspw.org. The panel consists of authors of the selected papers, and the session is moderated by the workshop's general chairs. We present selected papers focusing on exciting major themes that emerged from the workshop. These are the papers that will provoke the most interesting discussion at ACSAC.

Signature-based schemes for detecting Internet worms often fail on zero-day worms, and their ability to rapidly react to new threats is typically limited by the requirement of some form of human involvement to formulate updated attack signatures. We propose an anomaly-based detection technique detailing a method to detect propagation of scanning worms within individual network cells, thus protecting internal networks from infection by internal clients. Our software implementation indicates that this technique is both accurate and rapid enough to enable automatic containment and suppression of worm propagation within a network cell. Our approach relies on an aggregate anomaly score, derived from the correlation of address resolution protocol (ARP) activity from individual network attached devices. Our preliminary analysis and prototype indicate that this technique can be used to rapidly detect zero-day worms within a very small number of scans

One of the best-known security paradigms is to use authentication as the basis for accéss control decisions. We turn this around, and instead rely on access control (or more precisely, integrity) as the basis for authentication. We propose a simple, practical means by which data origin assurances for message authentication are based on corroboration, for example by cross-checking with information made available by a known source or at a specified location (e.g., web page). The security relies on the integrity of this corroborating information, and thus on access control on the hosting (or publishing) of this information. We do not explicitly require cryptographic keys for the corroboration step, or for the protection of corroborating information (e.g., it may be publicly posted), and thus our paradigm allows message authentication without direct dependence on private or secret keys. It may be characterized as security by integrity. Message authentication applications we discuss include email source authentication, and data origin authentication for digital signatures. Our work thus has application to problems including spam and phishing (e.g., where email with spoofed source addressing is involved), and addresses theft, extraction, or other illicit determination of digital signature private keys.

We present a novel idea for user authentication that we call pass-thoughts. Recent advances in Brain-Computer Interface (BCI) technology indicate that there is potential for a new type of human-computer interaction: a user thoughts directly to a computer. The goal of a pass-thought system would be to extract as much entropy as possible from a user's brain signals upon transmitting a thought. Provided that these brain signals can be recorded and processed in an accurate and repeatable way, a pass-thought system might provide a quasi two-factor, changeable, authentication method resistant to shoulder-surfing. The potential size of the space of a pass-thought system would seem to be unbounded in theory, although in practice it will be finite due to system constraints. In this paper, we discuss the motivation and potential of pass-thought authentication, the status quo of BCI technology, and outline the design of what we believe to be a currently feasible pass-thought system. We also briefly mention the need for general exploration and open debate regarding ethical considerations for such technologies.

Self-checking software tamper resistance mechanisms employing checksums, including advanced systems as recently proposed by Chang and Atallah (2002) and Horne et al. (2002) have been promoted as an alternative to other software integrity verification techniques. Appealing aspects include the promise of being able to verify the integrity of software independent of the external support environment, as well as the ability to automatically integrate checksumming code during program compilation or linking. In this paper we show that the rich functionality of many modern processors, including UltraSparc and x86-compatible processors, facilitates automated attacks which defeat such checksumming by self-checking programs.

Self-hashing has been proposed as a technique for verifying software integrity. Appealing aspects of this approach to software tamper resistance include the promise of being able to verify the integrity of software independent of the external support environment, as well as the ability to integrate code protection mechanisms automatically. In this paper, we show that the rich functionality of most modern general-purpose processors (including UltraSparc, x86, PowerPC, AMD64, Alpha, and ARM) facilitate an automated, generic attack which defeats such self-hashing. We present a general description of the attack strategy and multiple attack implementations that exploit different processor features. Each of these implementations is generic in that it can defeat self-hashing employed by any user-space program on a single platform. Together, these implementations defeat self-hashing on most modern general-purpose processors. The generality and efficiency of our attack suggests that self-hashing is not a viable strategy for high-security tamper resistance on modern computer systems.

We study the impact of selected parameters on the size of the password space for "Draw-A-Secret" (DAS) graphical passwords. We examine the role of and relationships between the number of composite strokes, grid dimensions, and password length in the DAS password space. We show that a very significant proportion of the DAS password space depends on the assumption that users will choose long passwords with many composite strokes. If users choose passwords having 4 or fewer strokes, with passwords of length 12 or less on a 5 /spl times/ 5 grid, instead of up to the maximum 12 possible strokes, the size of the DAS password space is reduced from 58 to 40 bits. Additionally, we found a similar reduction when users choose no strokes of length 1. To strengthen security, we propose a technique and describe a representative system that may gain up to 16 more bits of security with an expected negligible increase in input time. Our results can be directly applied to determine secure design choices, graphical password parameter guidelines, and in deciding which parameters deserve focus in graphical password user studies.

The security of iterated message authentication code (MAC) algorithms is considered, and in particular, those constructed from unkeyed hash functions. A new MAC forgery attack applicable to all deterministic iterated MAC algorithms is presented, which requires on the order of 2/sup n/2/ known text-MAC pairs for algorithms with n bits of internal memory, as compared to the best previous general attack which required exhaustive key search. A related key-recovery attack is also given which applies to a large class of MAC algorithms including a strengthened version of CBC-MAC found in ANSI X9.19 and ISO/IEC 9797, and envelope MAC techniques such as "keyed MD5". The security of several related existing MACs based directly on unkeyed hash functions, including the secret prefix and secret suffix methods, is also examined.

We consider true broadcast systems for the secure communication of session keys. These schemes provide for parallel rather than serial construction of broadcast messages, while avoiding selective broadcasting. We begin by introducing a conceptual framework for true broadcasting and illustrate its design with a secure key broadcast scheme based on probabilistic encryption. The framework provides for a system requiring user anonymity, as a result of the absence of addressing for the broadcast message. We also illustrate how Shamir's threshold scheme can be altered to allow for parallel broadcasting. We then present a formal model and use information theoretic techniques to establish a lower bound on the size of the broadcast message for a class of true broadcast schemes. Finally, we improve upon the aforementioned threshold scheme such that it achieves the lower bound.

Current techniques for collision search with feasible memory requirements involve pseudo-random walks through some space where one must wait for the result of the current step before the next step can begin. These techniques are serial in nature, and direct parallelization is inefficient. We present a simple new method of parallelizing collision searches that greatly extends the reach of practical attacks. The new method is illustrated with applications to hash functions and discrete logarithms in cyclic groups. In the case of hash functions, we begin with two messages; the first is a message that we want our target to digitally sign, and the second is a message that the target is willing to sign. Using collision search adapted for hashing collisions, one can find slightly altered versions of these messages such that the two new messages give the same hash result. As a particular example, a $10 million custom machine for applying parallel collision search to the MD5 hash function could complete an attack with an expected run time of 24 days. This machine would be specific to MD5, but could be used for any pair of messages. For discrete logarithms in cyclic groups, ideas from Pollard’s rho and lambda methods for index computation are combined to allow efficient parallel implementation using the new method. As a concrete example, we consider an elliptic curve cryptosystem over GF(2 155) with the order of the curve having largest prime factor of approximate size 10 36. A $10 million machine custom built for this finite field could compute a discrete logarithm with an expected run time of 36 days. 1.

We present a logic for analyzing cryptographic protocols. This logic encompasses a unification of four of its predecessors in the BAN family of logics, namely those given by Li Gong et al. (1990); M. Abadi, M. Tuttle (1991); P.C. van Oorschot (1993); and BAN itself (M. Burrows et al., 1989). We also present a model-theoretic semantics with respect to which the logic is sound. The logic presented captures all of the desirable features of its predecessors and more; nonetheless, it accomplishes this with no more axioms or rules than the simplest of its predecessors.>

Abstract. The authentication logic of Burrows, Abadi and Needham (BAN) provided an important step towards rigourous analysis of authentication protocols, and has motivated several subsequent refinements. We propose extensions to BAN-like logics which facilitate, for the first time, examination of public-key based authenticated key establishment protocols in which both parties contribute to the derived key (i.e. key agreement protocols). Attention is focussed on six distinct generic goals for authenticated key establishment protocols. The extended logic is used to analyze three Diffie-Hellman based key agreement protocols, facilitating direct comparison of these protocols with respect to formal goals reached and formal assumptions required. 1

This paper presents a generalization of Moenck’s root finding algorithm over $GF(q)$, for q a prime or prime power. The generalized algorithm, like its predecessor, is deterministic, given a primitive element $\omega $ for $GF(q)$. If $q - 1$ is b-smooth, where $b = (\log q)^{O(1)} $, then the algorithm runs in polynomial time. An analogue of this generalization which applies to extension fields $GF(q^m )$ is also considered. The analogue is a deterministic algorithm based on the recently introduced affine method for root finding in $GF(q^m )$, where $m > 1$; it is, however, less efficient that the affine method itself.

This paper is concerned with pair-splitting sets in $AG_k ( m,q )$, the design obtained from the points and k-flats in $AG (m,q)$. A pair-splitting set is a set of parallel classes $\{ R_1 ,R_2 , \cdots ,R_s \}$ such that there is no pair of distinct points $a,b$ such that $a,b$ are contained in a common k-flat of each of the s parallel classes. It is easy to prove that a lower bound on s is $\lceil m/( m - k ) \rceil $. The main result of this paper is to prove that this lower bound is always achievable for any choice of $m,q$, and k, where $0\leqq k\leqq m - 1$. The concept of pair-splitting sets arises naturally out of the problem of finding roots in $GF( q^m )$ of a polynomial over $GF ( q^m )$. The connection between the two concepts is briefly discussed.

The problem of finding roots in F of polynomials in F(x) for F=GF(q/sup m/), where q is a prime or prime power and m is a positive integer greater than 1 is considered. The problem is analyzed by making use of the finite affine geometry AG(m,q). A new method is proposed for finding roots of polynomials over finite extension fields. It is more efficient than previous algorithms when the degree of the polynomial whose roots are to be found is less than dimension m of the extension field. Implementation of the algorithm can be enhanced in cases in which optimal normal bases for the coefficient field are available.>