The agency appears to be the first to report that it is the victim of an attack exploiting a flaw in software known as OpenSSL, which is used on about two-thirds of websites to secure data as it travels across the Internet.
Later on Monday, British parenting website Mumsnet, which claims more than 60 million monthly page views, said it had required all users to reset their passwords after a Heartbleed-related breach. It didn't say whether any information had been taken.
Internet companies, technology providers, businesses and government agencies have been scrambling to figure out whether their systems are vulnerable to attack since the flaw was disclosed a week ago. When researchers disclosed that they discovered the bug, they said they did not know whether anybody had exploited it to launch attacks, though it had been present in OpenSSL software for several years.
Andy Ellis, chief technology officer with Akamai Technologies Inc, said he was not surprised to hear about the attack on the Canadian agency because there are already several "tool kits" publicly available over the Internet that hackers can use to launch attacks on vulnerable websites.
"You should expect to start seeing the attacks this week," said Ellis.
Akamai learned over the weekend that customers may have had digital keys for encrypting data exposed to attack. "I've had a crypto team working on it all through the night," Ellis said.
News of the attack in Canada came after authorities in Washington warned banks and other businesses on Friday to be on alert for hackers seeking to steal data exposed by the bug.
Lior Div, chief executive of the cybersecurity firm Cybereason, said that "even non-sophisticated hackers" will attempt to launch attacks that exploit the vulnerability with the tools that are publicly available.
"We are in a race," Div said. "People who hadn't thought about using this type of attack will use it now."
To be sure, some experts said that hackers already have plenty of easy-to-use tools for attacking networks at their disposal, so that it is hard to say for sure that "Heartbleed" will lead to a significant increase in attacks.
The Pew Research Center released a report on Monday saying that 18 percent of adults surveyed in January reported having had important personal data stolen, such as Social Security numbers or credit card or bank account information. That was up from 11 percent when the center conducted a similar poll of online adults in July 2013.
A new toy
Dan Kaminsky, a well-known expert in Internet security, said that while disclosure of the new bug means that some hackers will certainly rush to exploit it, many attackers will stick with old tools that are extremely effective in stealing data, such as compromising accounts of system administrators or accessing databases using a technique known as "SQL injection."
"It's not like every hacker in the world has said 'We have this new toy and it gets us in everywhere,'" said Kaminsky. "They still have their old toys. Their old toys work a heck of a lot better."
The Canada Revenue Agency said that police are investigating the attack, which occurred over a six-hour period. Forensic experts try to ascertain whether other data had been taken, a task that will be complicated because security experts say they believe that the Heartbleed bug allows attackers to steal data without leaving a trace.
"We are currently going through the painstaking process of analyzing other fragments of data, some that may relate to businesses, that were also removed," it said.
The agency shut down access to its online services on Wednesday, in the heart of the annual tax season, because of the bug.
Canadian authorities said that all government websites, including that of the Canada Revenue Agency, were back up as of Monday, with an updated and tested version of the OpenSSL software.
Lisa McCormack, a 36-year-old corporate secretary from Acton, Ontario, said she was surprised to learn of the attack on the government agency."The fact that it got compromised that quickly, with that many people affected, is concerning," she said. That's our national databank of identity."