summaryrefslogtreecommitdiffstats
path: root/net/bluetooth
diff options
context:
space:
mode:
Diffstat (limited to 'net/bluetooth')
-rw-r--r--net/bluetooth/6lowpan.c192
-rw-r--r--net/bluetooth/Kconfig1
-rw-r--r--net/bluetooth/Makefile2
-rw-r--r--net/bluetooth/af_bluetooth.c26
-rw-r--r--net/bluetooth/amp.c10
-rw-r--r--net/bluetooth/ecc.c816
-rw-r--r--net/bluetooth/ecc.h54
-rw-r--r--net/bluetooth/ecdh_helper.c231
-rw-r--r--net/bluetooth/ecdh_helper.h27
-rw-r--r--net/bluetooth/hci_core.c4
-rw-r--r--net/bluetooth/hci_sock.c3
-rw-r--r--net/bluetooth/l2cap_core.c30
-rw-r--r--net/bluetooth/rfcomm/core.c4
-rw-r--r--net/bluetooth/selftest.c28
-rw-r--r--net/bluetooth/smp.c46
15 files changed, 427 insertions, 1047 deletions
diff --git a/net/bluetooth/6lowpan.c b/net/bluetooth/6lowpan.c
index d491529332f4..608959989f8e 100644
--- a/net/bluetooth/6lowpan.c
+++ b/net/bluetooth/6lowpan.c
@@ -20,6 +20,7 @@
#include <net/ipv6.h>
#include <net/ip6_route.h>
#include <net/addrconf.h>
+#include <net/pkt_sched.h>
#include <net/bluetooth/bluetooth.h>
#include <net/bluetooth/hci_core.h>
@@ -38,7 +39,6 @@ struct skb_cb {
struct in6_addr addr;
struct in6_addr gw;
struct l2cap_chan *chan;
- int status;
};
#define lowpan_cb(skb) ((struct skb_cb *)((skb)->cb))
@@ -64,7 +64,7 @@ struct lowpan_peer {
struct l2cap_chan *chan;
/* peer addresses in various formats */
- unsigned char eui64_addr[EUI64_ADDR_LEN];
+ unsigned char lladdr[ETH_ALEN];
struct in6_addr peer_addr;
};
@@ -270,28 +270,20 @@ static int give_skb_to_upper(struct sk_buff *skb, struct net_device *dev)
}
static int iphc_decompress(struct sk_buff *skb, struct net_device *netdev,
- struct l2cap_chan *chan)
+ struct lowpan_peer *peer)
{
- const u8 *saddr, *daddr;
+ const u8 *saddr;
struct lowpan_btle_dev *dev;
- struct lowpan_peer *peer;
dev = lowpan_btle_dev(netdev);
- rcu_read_lock();
- peer = __peer_lookup_chan(dev, chan);
- rcu_read_unlock();
- if (!peer)
- return -EINVAL;
-
- saddr = peer->eui64_addr;
- daddr = dev->netdev->dev_addr;
+ saddr = peer->lladdr;
- return lowpan_header_decompress(skb, netdev, daddr, saddr);
+ return lowpan_header_decompress(skb, netdev, netdev->dev_addr, saddr);
}
static int recv_pkt(struct sk_buff *skb, struct net_device *dev,
- struct l2cap_chan *chan)
+ struct lowpan_peer *peer)
{
struct sk_buff *local_skb;
int ret;
@@ -344,8 +336,9 @@ static int recv_pkt(struct sk_buff *skb, struct net_device *dev,
local_skb->dev = dev;
- ret = iphc_decompress(local_skb, dev, chan);
+ ret = iphc_decompress(local_skb, dev, peer);
if (ret < 0) {
+ BT_DBG("iphc_decompress failed: %d", ret);
kfree_skb(local_skb);
goto drop;
}
@@ -365,6 +358,7 @@ static int recv_pkt(struct sk_buff *skb, struct net_device *dev,
consume_skb(local_skb);
consume_skb(skb);
} else {
+ BT_DBG("unknown packet type");
goto drop;
}
@@ -390,7 +384,7 @@ static int chan_recv_cb(struct l2cap_chan *chan, struct sk_buff *skb)
if (!dev || !dev->netdev)
return -ENOENT;
- err = recv_pkt(skb, dev->netdev, chan);
+ err = recv_pkt(skb, dev->netdev, peer);
if (err) {
BT_DBG("recv pkt %d", err);
err = -EAGAIN;
@@ -399,37 +393,6 @@ static int chan_recv_cb(struct l2cap_chan *chan, struct sk_buff *skb)
return err;
}
-static u8 get_addr_type_from_eui64(u8 byte)
-{
- /* Is universal(0) or local(1) bit */
- return ((byte & 0x02) ? BDADDR_LE_RANDOM : BDADDR_LE_PUBLIC);
-}
-
-static void copy_to_bdaddr(struct in6_addr *ip6_daddr, bdaddr_t *addr)
-{
- u8 *eui64 = ip6_daddr->s6_addr + 8;
-
- addr->b[0] = eui64[7];
- addr->b[1] = eui64[6];
- addr->b[2] = eui64[5];
- addr->b[3] = eui64[2];
- addr->b[4] = eui64[1];
- addr->b[5] = eui64[0];
-}
-
-static void convert_dest_bdaddr(struct in6_addr *ip6_daddr,
- bdaddr_t *addr, u8 *addr_type)
-{
- copy_to_bdaddr(ip6_daddr, addr);
-
- /* We need to toggle the U/L bit that we got from IPv6 address
- * so that we get the proper address and type of the BD address.
- */
- addr->b[5] ^= 0x02;
-
- *addr_type = get_addr_type_from_eui64(addr->b[5]);
-}
-
static int setup_header(struct sk_buff *skb, struct net_device *netdev,
bdaddr_t *peer_addr, u8 *peer_addr_type)
{
@@ -437,8 +400,7 @@ static int setup_header(struct sk_buff *skb, struct net_device *netdev,
struct ipv6hdr *hdr;
struct lowpan_btle_dev *dev;
struct lowpan_peer *peer;
- bdaddr_t addr, *any = BDADDR_ANY;
- u8 *daddr = any->b;
+ u8 *daddr;
int err, status = 0;
hdr = ipv6_hdr(skb);
@@ -449,34 +411,24 @@ static int setup_header(struct sk_buff *skb, struct net_device *netdev,
if (ipv6_addr_is_multicast(&ipv6_daddr)) {
lowpan_cb(skb)->chan = NULL;
+ daddr = NULL;
} else {
- u8 addr_type;
+ BT_DBG("dest IP %pI6c", &ipv6_daddr);
- /* Get destination BT device from skb.
- * If there is no such peer then discard the packet.
+ /* The packet might be sent to 6lowpan interface
+ * because of routing (either via default route
+ * or user set route) so get peer according to
+ * the destination address.
*/
- convert_dest_bdaddr(&ipv6_daddr, &addr, &addr_type);
-
- BT_DBG("dest addr %pMR type %d IP %pI6c", &addr,
- addr_type, &ipv6_daddr);
-
- peer = peer_lookup_ba(dev, &addr, addr_type);
+ peer = peer_lookup_dst(dev, &ipv6_daddr, skb);
if (!peer) {
- /* The packet might be sent to 6lowpan interface
- * because of routing (either via default route
- * or user set route) so get peer according to
- * the destination address.
- */
- peer = peer_lookup_dst(dev, &ipv6_daddr, skb);
- if (!peer) {
- BT_DBG("no such peer %pMR found", &addr);
- return -ENOENT;
- }
+ BT_DBG("no such peer");
+ return -ENOENT;
}
- daddr = peer->eui64_addr;
- *peer_addr = addr;
- *peer_addr_type = addr_type;
+ daddr = peer->lladdr;
+ *peer_addr = peer->chan->dst;
+ *peer_addr_type = peer->chan->dst_type;
lowpan_cb(skb)->chan = peer->chan;
status = 1;
@@ -527,15 +479,8 @@ static int send_pkt(struct l2cap_chan *chan, struct sk_buff *skb,
return 0;
}
- if (!err)
- err = lowpan_cb(skb)->status;
-
- if (err < 0) {
- if (err == -EAGAIN)
- netdev->stats.tx_dropped++;
- else
- netdev->stats.tx_errors++;
- }
+ if (err < 0)
+ netdev->stats.tx_errors++;
return err;
}
@@ -647,9 +592,9 @@ static void netdev_setup(struct net_device *dev)
{
dev->hard_header_len = 0;
dev->needed_tailroom = 0;
- dev->flags = IFF_RUNNING | IFF_POINTOPOINT |
- IFF_MULTICAST;
+ dev->flags = IFF_RUNNING | IFF_MULTICAST;
dev->watchdog_timeo = 0;
+ dev->tx_queue_len = DEFAULT_TX_QUEUE_LEN;
dev->netdev_ops = &netdev_ops;
dev->header_ops = &header_ops;
@@ -660,34 +605,6 @@ static struct device_type bt_type = {
.name = "bluetooth",
};
-static void set_addr(u8 *eui, u8 *addr, u8 addr_type)
-{
- /* addr is the BT address in little-endian format */
- eui[0] = addr[5];
- eui[1] = addr[4];
- eui[2] = addr[3];
- eui[3] = 0xFF;
- eui[4] = 0xFE;
- eui[5] = addr[2];
- eui[6] = addr[1];
- eui[7] = addr[0];
-
- /* Universal/local bit set, BT 6lowpan draft ch. 3.2.1 */
- if (addr_type == BDADDR_LE_PUBLIC)
- eui[0] &= ~0x02;
- else
- eui[0] |= 0x02;
-
- BT_DBG("type %d addr %*phC", addr_type, 8, eui);
-}
-
-static void set_dev_addr(struct net_device *netdev, bdaddr_t *addr,
- u8 addr_type)
-{
- netdev->addr_assign_type = NET_ADDR_PERM;
- set_addr(netdev->dev_addr, addr->b, addr_type);
-}
-
static void ifup(struct net_device *netdev)
{
int err;
@@ -746,16 +663,9 @@ static struct l2cap_chan *chan_create(void)
return chan;
}
-static void set_ip_addr_bits(u8 addr_type, u8 *addr)
-{
- if (addr_type == BDADDR_LE_PUBLIC)
- *addr |= 0x02;
- else
- *addr &= ~0x02;
-}
-
static struct l2cap_chan *add_peer_chan(struct l2cap_chan *chan,
- struct lowpan_btle_dev *dev)
+ struct lowpan_btle_dev *dev,
+ bool new_netdev)
{
struct lowpan_peer *peer;
@@ -766,19 +676,9 @@ static struct l2cap_chan *add_peer_chan(struct l2cap_chan *chan,
peer->chan = chan;
memset(&peer->peer_addr, 0, sizeof(struct in6_addr));
- /* RFC 2464 ch. 5 */
- peer->peer_addr.s6_addr[0] = 0xFE;
- peer->peer_addr.s6_addr[1] = 0x80;
- set_addr((u8 *)&peer->peer_addr.s6_addr + 8, chan->dst.b,
- chan->dst_type);
-
- memcpy(&peer->eui64_addr, (u8 *)&peer->peer_addr.s6_addr + 8,
- EUI64_ADDR_LEN);
+ baswap((void *)peer->lladdr, &chan->dst);
- /* IPv6 address needs to have the U/L bit set properly so toggle
- * it back here.
- */
- set_ip_addr_bits(chan->dst_type, (u8 *)&peer->peer_addr.s6_addr + 8);
+ lowpan_iphc_uncompress_eui48_lladdr(&peer->peer_addr, peer->lladdr);
spin_lock(&devices_lock);
INIT_LIST_HEAD(&peer->list);
@@ -786,7 +686,8 @@ static struct l2cap_chan *add_peer_chan(struct l2cap_chan *chan,
spin_unlock(&devices_lock);
/* Notifying peers about us needs to be done without locks held */
- INIT_DELAYED_WORK(&dev->notify_peers, do_notify_peers);
+ if (new_netdev)
+ INIT_DELAYED_WORK(&dev->notify_peers, do_notify_peers);
schedule_delayed_work(&dev->notify_peers, msecs_to_jiffies(100));
return peer->chan;
@@ -803,7 +704,8 @@ static int setup_netdev(struct l2cap_chan *chan, struct lowpan_btle_dev **dev)
if (!netdev)
return -ENOMEM;
- set_dev_addr(netdev, &chan->src, chan->src_type);
+ netdev->addr_assign_type = NET_ADDR_PERM;
+ baswap((void *)netdev->dev_addr, &chan->src);
netdev->netdev_ops = &netdev_ops;
SET_NETDEV_DEV(netdev, &chan->conn->hcon->hdev->dev);
@@ -843,6 +745,7 @@ out:
static inline void chan_ready_cb(struct l2cap_chan *chan)
{
struct lowpan_btle_dev *dev;
+ bool new_netdev = false;
dev = lookup_dev(chan->conn);
@@ -853,12 +756,13 @@ static inline void chan_ready_cb(struct l2cap_chan *chan)
l2cap_chan_del(chan, -ENOENT);
return;
}
+ new_netdev = true;
}
if (!try_module_get(THIS_MODULE))
return;
- add_peer_chan(chan, dev);
+ add_peer_chan(chan, dev, new_netdev);
ifup(dev->netdev);
}
@@ -964,26 +868,28 @@ static struct sk_buff *chan_alloc_skb_cb(struct l2cap_chan *chan,
static void chan_suspend_cb(struct l2cap_chan *chan)
{
- struct sk_buff *skb = chan->data;
+ struct lowpan_btle_dev *dev;
- BT_DBG("chan %p conn %p skb %p", chan, chan->conn, skb);
+ BT_DBG("chan %p suspend", chan);
- if (!skb)
+ dev = lookup_dev(chan->conn);
+ if (!dev || !dev->netdev)
return;
- lowpan_cb(skb)->status = -EAGAIN;
+ netif_stop_queue(dev->netdev);
}
static void chan_resume_cb(struct l2cap_chan *chan)
{
- struct sk_buff *skb = chan->data;
+ struct lowpan_btle_dev *dev;
- BT_DBG("chan %p conn %p skb %p", chan, chan->conn, skb);
+ BT_DBG("chan %p resume", chan);
- if (!skb)
+ dev = lookup_dev(chan->conn);
+ if (!dev || !dev->netdev)
return;
- lowpan_cb(skb)->status = 0;
+ netif_wake_queue(dev->netdev);
}
static long chan_get_sndtimeo_cb(struct l2cap_chan *chan)
diff --git a/net/bluetooth/Kconfig b/net/bluetooth/Kconfig
index 06c31b9a68b0..68f951b3e85a 100644
--- a/net/bluetooth/Kconfig
+++ b/net/bluetooth/Kconfig
@@ -13,6 +13,7 @@ menuconfig BT
select CRYPTO_CMAC
select CRYPTO_ECB
select CRYPTO_SHA256
+ select CRYPTO_ECDH
help
Bluetooth is low-cost, low-power, short-range wireless technology.
It was designed as a replacement for cables and other short-range
diff --git a/net/bluetooth/Makefile b/net/bluetooth/Makefile
index 4bfaa19a5573..5d0a113e2e40 100644
--- a/net/bluetooth/Makefile
+++ b/net/bluetooth/Makefile
@@ -13,7 +13,7 @@ bluetooth_6lowpan-y := 6lowpan.o
bluetooth-y := af_bluetooth.o hci_core.o hci_conn.o hci_event.o mgmt.o \
hci_sock.o hci_sysfs.o l2cap_core.o l2cap_sock.o smp.o lib.o \
- ecc.o hci_request.o mgmt_util.o
+ ecdh_helper.o hci_request.o mgmt_util.o
bluetooth-$(CONFIG_BT_BREDR) += sco.o
bluetooth-$(CONFIG_BT_HS) += a2mp.o amp.o
diff --git a/net/bluetooth/af_bluetooth.c b/net/bluetooth/af_bluetooth.c
index 69e1f7d362a8..42d0997e2fbb 100644
--- a/net/bluetooth/af_bluetooth.c
+++ b/net/bluetooth/af_bluetooth.c
@@ -159,12 +159,17 @@ void bt_accept_enqueue(struct sock *parent, struct sock *sk)
BT_DBG("parent %p, sk %p", parent, sk);
sock_hold(sk);
+ lock_sock(sk);
list_add_tail(&bt_sk(sk)->accept_q, &bt_sk(parent)->accept_q);
bt_sk(sk)->parent = parent;
+ release_sock(sk);
parent->sk_ack_backlog++;
}
EXPORT_SYMBOL(bt_accept_enqueue);
+/* Calling function must hold the sk lock.
+ * bt_sk(sk)->parent must be non-NULL meaning sk is in the parent list.
+ */
void bt_accept_unlink(struct sock *sk)
{
BT_DBG("sk %p state %d", sk, sk->sk_state);
@@ -183,11 +188,32 @@ struct sock *bt_accept_dequeue(struct sock *parent, struct socket *newsock)
BT_DBG("parent %p", parent);
+restart:
list_for_each_entry_safe(s, n, &bt_sk(parent)->accept_q, accept_q) {
sk = (struct sock *)s;
+ /* Prevent early freeing of sk due to unlink and sock_kill */
+ sock_hold(sk);
lock_sock(sk);
+ /* Check sk has not already been unlinked via
+ * bt_accept_unlink() due to serialisation caused by sk locking
+ */
+ if (!bt_sk(sk)->parent) {
+ BT_DBG("sk %p, already unlinked", sk);
+ release_sock(sk);
+ sock_put(sk);
+
+ /* Restart the loop as sk is no longer in the list
+ * and also avoid a potential infinite loop because
+ * list_for_each_entry_safe() is not thread safe.
+ */
+ goto restart;
+ }
+
+ /* sk is safely in the parent list so reduce reference count */
+ sock_put(sk);
+
/* FIXME: Is this check still needed */
if (sk->sk_state == BT_CLOSED) {
bt_accept_unlink(sk);
diff --git a/net/bluetooth/amp.c b/net/bluetooth/amp.c
index 02a4ccc04e1e..ebcab5bbadd7 100644
--- a/net/bluetooth/amp.c
+++ b/net/bluetooth/amp.c
@@ -263,7 +263,7 @@ void amp_read_loc_assoc_frag(struct hci_dev *hdev, u8 phy_handle)
struct hci_cp_read_local_amp_assoc cp;
struct amp_assoc *loc_assoc = &hdev->loc_assoc;
struct hci_request req;
- int err = 0;
+ int err;
BT_DBG("%s handle %d", hdev->name, phy_handle);
@@ -282,7 +282,7 @@ void amp_read_loc_assoc(struct hci_dev *hdev, struct amp_mgr *mgr)
{
struct hci_cp_read_local_amp_assoc cp;
struct hci_request req;
- int err = 0;
+ int err;
memset(&hdev->loc_assoc, 0, sizeof(struct amp_assoc));
memset(&cp, 0, sizeof(cp));
@@ -292,7 +292,7 @@ void amp_read_loc_assoc(struct hci_dev *hdev, struct amp_mgr *mgr)
set_bit(READ_LOC_AMP_ASSOC, &mgr->state);
hci_req_init(&req, hdev);
hci_req_add(&req, HCI_OP_READ_LOCAL_AMP_ASSOC, sizeof(cp), &cp);
- hci_req_run_skb(&req, read_local_amp_assoc_complete);
+ err = hci_req_run_skb(&req, read_local_amp_assoc_complete);
if (err < 0)
a2mp_send_getampassoc_rsp(hdev, A2MP_STATUS_INVALID_CTRL_ID);
}
@@ -303,7 +303,7 @@ void amp_read_loc_assoc_final_data(struct hci_dev *hdev,
struct hci_cp_read_local_amp_assoc cp;
struct amp_mgr *mgr = hcon->amp_mgr;
struct hci_request req;
- int err = 0;
+ int err;
cp.phy_handle = hcon->handle;
cp.len_so_far = cpu_to_le16(0);
@@ -314,7 +314,7 @@ void amp_read_loc_assoc_final_data(struct hci_dev *hdev,
/* Read Local AMP Assoc final link information data */
hci_req_init(&req, hdev);
hci_req_add(&req, HCI_OP_READ_LOCAL_AMP_ASSOC, sizeof(cp), &cp);
- hci_req_run_skb(&req, read_local_amp_assoc_complete);
+ err = hci_req_run_skb(&req, read_local_amp_assoc_complete);
if (err < 0)
a2mp_send_getampassoc_rsp(hdev, A2MP_STATUS_INVALID_CTRL_ID);
}
diff --git a/net/bluetooth/ecc.c b/net/bluetooth/ecc.c
deleted file mode 100644
index e1709f8467ac..000000000000
--- a/net/bluetooth/ecc.c
+++ /dev/null
@@ -1,816 +0,0 @@
-/*
- * Copyright (c) 2013, Kenneth MacKay
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions are
- * met:
- * * Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
- * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#include <linux/random.h>
-
-#include "ecc.h"
-
-/* 256-bit curve */
-#define ECC_BYTES 32
-
-#define MAX_TRIES 16
-
-/* Number of u64's needed */
-#define NUM_ECC_DIGITS (ECC_BYTES / 8)
-
-struct ecc_point {
- u64 x[NUM_ECC_DIGITS];
- u64 y[NUM_ECC_DIGITS];
-};
-
-typedef struct {
- u64 m_low;
- u64 m_high;
-} uint128_t;
-
-#define CURVE_P_32 { 0xFFFFFFFFFFFFFFFFull, 0x00000000FFFFFFFFull, \
- 0x0000000000000000ull, 0xFFFFFFFF00000001ull }
-
-#define CURVE_G_32 { \
- { 0xF4A13945D898C296ull, 0x77037D812DEB33A0ull, \
- 0xF8BCE6E563A440F2ull, 0x6B17D1F2E12C4247ull }, \
- { 0xCBB6406837BF51F5ull, 0x2BCE33576B315ECEull, \
- 0x8EE7EB4A7C0F9E16ull, 0x4FE342E2FE1A7F9Bull } \
-}
-
-#define CURVE_N_32 { 0xF3B9CAC2FC632551ull, 0xBCE6FAADA7179E84ull, \
- 0xFFFFFFFFFFFFFFFFull, 0xFFFFFFFF00000000ull }
-
-static u64 curve_p[NUM_ECC_DIGITS] = CURVE_P_32;
-static struct ecc_point curve_g = CURVE_G_32;
-static u64 curve_n[NUM_ECC_DIGITS] = CURVE_N_32;
-
-static void vli_clear(u64 *vli)
-{
- int i;
-
- for (i = 0; i < NUM_ECC_DIGITS; i++)
- vli[i] = 0;
-}
-
-/* Returns true if vli == 0, false otherwise. */
-static bool vli_is_zero(const u64 *vli)
-{
- int i;
-
- for (i = 0; i < NUM_ECC_DIGITS; i++) {
- if (vli[i])
- return false;
- }
-
- return true;
-}
-
-/* Returns nonzero if bit bit of vli is set. */
-static u64 vli_test_bit(const u64 *vli, unsigned int bit)
-{
- return (vli[bit / 64] & ((u64) 1 << (bit % 64)));
-}
-
-/* Counts the number of 64-bit "digits" in vli. */
-static unsigned int vli_num_digits(const u64 *vli)
-{
- int i;
-
- /* Search from the end until we find a non-zero digit.
- * We do it in reverse because we expect that most digits will
- * be nonzero.
- */
- for (i = NUM_ECC_DIGITS - 1; i >= 0 && vli[i] == 0; i--);
-
- return (i + 1);
-}
-
-/* Counts the number of bits required for vli. */
-static unsigned int vli_num_bits(const u64 *vli)
-{
- unsigned int i, num_digits;
- u64 digit;
-
- num_digits = vli_num_digits(vli);
- if (num_digits == 0)
- return 0;
-
- digit = vli[num_digits - 1];
- for (i = 0; digit; i++)
- digit >>= 1;
-
- return ((num_digits - 1) * 64 + i);
-}
-
-/* Sets dest = src. */
-static void vli_set(u64 *dest, const u64 *src)
-{
- int i;
-
- for (i = 0; i < NUM_ECC_DIGITS; i++)
- dest[i] = src[i];
-}
-
-/* Returns sign of left - right. */
-static int vli_cmp(const u64 *left, const u64 *right)
-{
- int i;
-
- for (i = NUM_ECC_DIGITS - 1; i >= 0; i--) {
- if (left[i] > right[i])
- return 1;
- else if (left[i] < right[i])
- return -1;
- }
-
- return 0;
-}
-
-/* Computes result = in << c, returning carry. Can modify in place
- * (if result == in). 0 < shift < 64.
- */
-static u64 vli_lshift(u64 *result, const u64 *in,
- unsigned int shift)
-{
- u64 carry = 0;
- int i;
-
- for (i = 0; i < NUM_ECC_DIGITS; i++) {
- u64 temp = in[i];
-
- result[i] = (temp << shift) | carry;
- carry = temp >> (64 - shift);
- }
-
- return carry;
-}
-
-/* Computes vli = vli >> 1. */
-static void vli_rshift1(u64 *vli)
-{
- u64 *end = vli;
- u64 carry = 0;
-
- vli += NUM_ECC_DIGITS;
-
- while (vli-- > end) {
- u64 temp = *vli;
- *vli = (temp >> 1) | carry;
- carry = temp << 63;
- }
-}
-
-/* Computes result = left + right, returning carry. Can modify in place. */
-static u64 vli_add(u64 *result, const u64 *left,
- const u64 *right)
-{
- u64 carry = 0;
- int i;
-
- for (i = 0; i < NUM_ECC_DIGITS; i++) {
- u64 sum;
-
- sum = left[i] + right[i] + carry;
- if (sum != left[i])
- carry = (sum < left[i]);
-
- result[i] = sum;
- }
-
- return carry;
-}
-
-/* Computes result = left - right, returning borrow. Can modify in place. */
-static u64 vli_sub(u64 *result, const u64 *left, const u64 *right)
-{
- u64 borrow = 0;
- int i;
-
- for (i = 0; i < NUM_ECC_DIGITS; i++) {
- u64 diff;
-
- diff = left[i] - right[i] - borrow;
- if (diff != left[i])
- borrow = (diff > left[i]);
-
- result[i] = diff;
- }
-
- return borrow;
-}
-
-static uint128_t mul_64_64(u64 left, u64 right)
-{
- u64 a0 = left & 0xffffffffull;
- u64 a1 = left >> 32;
- u64 b0 = right & 0xffffffffull;
- u64 b1 = right >> 32;
- u64 m0 = a0 * b0;
- u64 m1 = a0 * b1;
- u64 m2 = a1 * b0;
- u64 m3 = a1 * b1;
- uint128_t result;
-
- m2 += (m0 >> 32);
- m2 += m1;
-
- /* Overflow */
- if (m2 < m1)
- m3 += 0x100000000ull;
-
- result.m_low = (m0 & 0xffffffffull) | (m2 << 32);
- result.m_high = m3 + (m2 >> 32);
-
- return result;
-}
-
-static uint128_t add_128_128(uint128_t a, uint128_t b)
-{
- uint128_t result;
-
- result.m_low = a.m_low + b.m_low;
- result.m_high = a.m_high + b.m_high + (result.m_low < a.m_low);
-
- return result;
-}
-
-static void vli_mult(u64 *result, const u64 *left, const u64 *right)
-{
- uint128_t r01 = { 0, 0 };
- u64 r2 = 0;
- unsigned int i, k;
-
- /* Compute each digit of result in sequence, maintaining the
- * carries.
- */
- for (k = 0; k < NUM_ECC_DIGITS * 2 - 1; k++) {
- unsigned int min;
-
- if (k < NUM_ECC_DIGITS)
- min = 0;
- else
- min = (k + 1) - NUM_ECC_DIGITS;
-
- for (i = min; i <= k && i < NUM_ECC_DIGITS; i++) {
- uint128_t product;
-
- product = mul_64_64(left[i], right[k - i]);
-
- r01 = add_128_128(r01, product);
- r2 += (r01.m_high < product.m_high);
- }
-
- result[k] = r01.m_low;
- r01.m_low = r01.m_high;
- r01.m_high = r2;
- r2 = 0;
- }
-
- result[NUM_ECC_DIGITS * 2 - 1] = r01.m_low;
-}
-
-static void vli_square(u64 *result, const u64 *left)
-{
- uint128_t r01 = { 0, 0 };
- u64 r2 = 0;
- int i, k;
-
- for (k = 0; k < NUM_ECC_DIGITS * 2 - 1; k++) {
- unsigned int min;
-
- if (k < NUM_ECC_DIGITS)
- min = 0;
- else
- min = (k + 1) - NUM_ECC_DIGITS;
-
- for (i = min; i <= k && i <= k - i; i++) {
- uint128_t product;
-
- product = mul_64_64(left[i], left[k - i]);
-
- if (i < k - i) {
- r2 += product.m_high >> 63;
- product.m_high = (product.m_high << 1) |
- (product.m_low >> 63);
- product.m_low <<= 1;
- }
-
- r01 = add_128_128(r01, product);
- r2 += (r01.m_high < product.m_high);
- }
-
- result[k] = r01.m_low;
- r01.m_low = r01.m_high;
- r01.m_high = r2;
- r2 = 0;
- }
-
- result[NUM_ECC_DIGITS * 2 - 1] = r01.m_low;
-}
-
-/* Computes result = (left + right) % mod.
- * Assumes that left < mod and right < mod, result != mod.
- */
-static void vli_mod_add(u64 *result, const u64 *left, const u64 *right,
- const u64 *mod)
-{
- u64 carry;
-
- carry = vli_add(result, left, right);
-
- /* result > mod (result = mod + remainder), so subtract mod to
- * get remainder.
- */
- if (carry || vli_cmp(result, mod) >= 0)
- vli_sub(result, result, mod);
-}
-
-/* Computes result = (left - right) % mod.
- * Assumes that left < mod and right < mod, result != mod.
- */
-static void vli_mod_sub(u64 *result, const u64 *left, const u64 *right,
- const u64 *mod)
-{
- u64 borrow = vli_sub(result, left, right);
-
- /* In this case, p_result == -diff == (max int) - diff.
- * Since -x % d == d - x, we can get the correct result from
- * result + mod (with overflow).
- */
- if (borrow)
- vli_add(result, result, mod);
-}
-
-/* Computes result = product % curve_p
- from http://www.nsa.gov/ia/_files/nist-routines.pdf */
-static void vli_mmod_fast(u64 *result, const u64 *product)
-{
- u64 tmp[NUM_ECC_DIGITS];
- int carry;
-
- /* t */
- vli_set(result, product);
-
- /* s1 */
- tmp[0] = 0;
- tmp[1] = product[5] & 0xffffffff00000000ull;
- tmp[2] = product[6];
- tmp[3] = product[7];
- carry = vli_lshift(tmp, tmp, 1);
- carry += vli_add(result, result, tmp);
-
- /* s2 */
- tmp[1] = product[6] << 32;
- tmp[2] = (product[6] >> 32) | (product[7] << 32);
- tmp[3] = product[7] >> 32;
- carry += vli_lshift(tmp, tmp, 1);
- carry += vli_add(result, result, tmp);
-
- /* s3 */
- tmp[0] = product[4];
- tmp[1] = product[5] & 0xffffffff;
- tmp[2] = 0;
- tmp[3] = product[7];
- carry += vli_add(result, result, tmp);
-
- /* s4 */
- tmp[0] = (product[4] >> 32) | (product[5] << 32);
- tmp[1] = (product[5] >> 32) | (product[6] & 0xffffffff00000000ull);
- tmp[2] = product[7];
- tmp[3] = (product[6] >> 32) | (product[4] << 32);
- carry += vli_add(result, result, tmp);
-
- /* d1 */
- tmp[0] = (product[5] >> 32) | (product[6] << 32);
- tmp[1] = (product[6] >> 32);
- tmp[2] = 0;
- tmp[3] = (product[4] & 0xffffffff) | (product[5] << 32);
- carry -= vli_sub(result, result, tmp);
-
- /* d2 */
- tmp[0] = product[6];
- tmp[1] = product[7];
- tmp[2] = 0;
- tmp[3] = (product[4] >> 32) | (product[5] & 0xffffffff00000000ull);
- carry -= vli_sub(result, result, tmp);
-
- /* d3 */
- tmp[0] = (product[6] >> 32) | (product[7] << 32);
- tmp[1] = (product[7] >> 32) | (product[4] << 32);
- tmp[2] = (product[4] >> 32) | (product[5] << 32);
- tmp[3] = (product[6] << 32);
- carry -= vli_sub(result, result, tmp);
-
- /* d4 */
- tmp[0] = product[7];
- tmp[1] = product[4] & 0xffffffff00000000ull;
- tmp[2] = product[5];
- tmp[3] = product[6] & 0xffffffff00000000ull;
- carry -= vli_sub(result, result, tmp);
-
- if (carry < 0) {
- do {
- carry += vli_add(result, result, curve_p);
- } while (carry < 0);
- } else {
- while (carry || vli_cmp(curve_p, result) != 1)
- carry -= vli_sub(result, result, curve_p);
- }
-}
-
-/* Computes result = (left * right) % curve_p. */
-static void vli_mod_mult_fast(u64 *result, const u64 *left, const u64 *right)
-{
- u64 product[2 * NUM_ECC_DIGITS];
-
- vli_mult(product, left, right);
- vli_mmod_fast(result, product);
-}
-
-/* Computes result = left^2 % curve_p. */
-static void vli_mod_square_fast(u64 *result, const u64 *left)
-{
- u64 product[2 * NUM_ECC_DIGITS];
-
- vli_square(product, left);
- vli_mmod_fast(result, product);
-}
-
-#define EVEN(vli) (!(vli[0] & 1))
-/* Computes result = (1 / p_input) % mod. All VLIs are the same size.
- * See "From Euclid's GCD to Montgomery Multiplication to the Great Divide"
- * https://labs.oracle.com/techrep/2001/smli_tr-2001-95.pdf
- */
-static void vli_mod_inv(u64 *result, const u64 *input, const u64 *mod)
-{
- u64 a[NUM_ECC_DIGITS], b[NUM_ECC_DIGITS];
- u64 u[NUM_ECC_DIGITS], v[NUM_ECC_DIGITS];
- u64 carry;
- int cmp_result;
-
- if (vli_is_zero(input)) {
- vli_clear(result);
- return;
- }
-
- vli_set(a, input);
- vli_set(b, mod);
- vli_clear(u);
- u[0] = 1;
- vli_clear(v);
-
- while ((cmp_result = vli_cmp(a, b)) != 0) {
- carry = 0;
-
- if (EVEN(a)) {
- vli_rshift1(a);
-
- if (!EVEN(u))
- carry = vli_add(u, u, mod);
-
- vli_rshift1(u);
- if (carry)
- u[NUM_ECC_DIGITS - 1] |= 0x8000000000000000ull;
- } else if (EVEN(b)) {
- vli_rshift1(b);
-
- if (!EVEN(v))
- carry = vli_add(v, v, mod);
-
- vli_rshift1(v);
- if (carry)
- v[NUM_ECC_DIGITS - 1] |= 0x8000000000000000ull;
- } else if (cmp_result > 0) {
- vli_sub(a, a, b);
- vli_rshift1(a);
-
- if (vli_cmp(u, v) < 0)
- vli_add(u, u, mod);
-
- vli_sub(u, u, v);
- if (!EVEN(u))
- carry = vli_add(u, u, mod);
-
- vli_rshift1(u);
- if (carry)
- u[NUM_ECC_DIGITS - 1] |= 0x8000000000000000ull;
- } else {
- vli_sub(b, b, a);
- vli_rshift1(b);
-
- if (vli_cmp(v, u) < 0)
- vli_add(v, v, mod);
-
- vli_sub(v, v, u);
- if (!EVEN(v))
- carry = vli_add(v, v, mod);
-
- vli_rshift1(v);
- if (carry)
- v[NUM_ECC_DIGITS - 1] |= 0x8000000000000000ull;
- }
- }
-
- vli_set(result, u);
-}
-
-/* ------ Point operations ------ */
-
-/* Returns true if p_point is the point at infinity, false otherwise. */
-static bool ecc_point_is_zero(const struct ecc_point *point)
-{
- return (vli_is_zero(point->x) && vli_is_zero(point->y));
-}
-
-/* Point multiplication algorithm using Montgomery's ladder with co-Z
- * coordinates. From http://eprint.iacr.org/2011/338.pdf
- */
-
-/* Double in place */
-static void ecc_point_double_jacobian(u64 *x1, u64 *y1, u64 *z1)
-{
- /* t1 = x, t2 = y, t3 = z */
- u64 t4[NUM_ECC_DIGITS];
- u64 t5[NUM_ECC_DIGITS];
-
- if (vli_is_zero(z1))
- return;
-
- vli_mod_square_fast(t4, y1); /* t4 = y1^2 */
- vli_mod_mult_fast(t5, x1, t4); /* t5 = x1*y1^2 = A */
- vli_mod_square_fast(t4, t4); /* t4 = y1^4 */
- vli_mod_mult_fast(y1, y1, z1); /* t2 = y1*z1 = z3 */
- vli_mod_square_fast(z1, z1); /* t3 = z1^2 */
-
- vli_mod_add(x1, x1, z1, curve_p); /* t1 = x1 + z1^2 */